CS250 ASSIGNMENT    --    Part I DUE September 2, 1997
 
PART I

 
 

READING ASSIGNMENT

Pages 1 - 35 from Weiss.
 

WRITTEN ASSIGNMENT

1.

Prove that $\sum_{i=0}^{i=n}(2i+1)~=~n^2$ by induction on n starting at n = 0.

2.

Prove by induction that n² - n is even for all $n \geq 0$. Can you prove this without induction? How?

3.

Do exercise (1.1) from Weiss page 12. You only need to write code for a function that returns the value of the kth largest element given an array of integers and the value of n.

4.

Do exercise (1.5) from Weiss page 12. (Hint: you can use derivatives for part a.)

5.

Prove that the statement in exercise (1.10), page 13 from Weiss is true.

PROGRAMMING ASSIGNMENT (program 1)
You only need to turn in a listing of this program and sample output.

Write a C++ program to find ${N \choose M}$ for non-negative integer values of M and N. Remember these are the binomial coefficients or the number of ways of choosing M items out of a set of N items without replacement. Your program must use a recursive function to do its calculations. Use the recurrence relation

$${N \choose M} = \left\{ \begin{array} {ll} 1 & \mbox{\rm if... ...-1} + {N-1 \choose M} & \mbox{\rm otherwise}\end{array} \right.$$

Your program should prompt the user for the two integers. If either value is negative or if M > N, the program should print an appropriate error message. Otherwise it should print the correct value.

Your program will be graded on style and readability as well as correct operation. Turn in a listing of your program on 8 1/2 by 11 sheets. Be sure to burst the pages and staple them together if your listing is more than one page long. You are responsible for testing your program and making sure that it works correctly.

For extra credit: in addition to printing the result, have your program print the number of additions performed to get the correct answer.

Do you think that this algorithm is efficient? Do you have any ideas for making the algorithm more efficient?
 

PART II (Due September 9 -- Program 2)


Turn in a listing of the code for the member functions of sorted_array.

Actually this is not actually a true programming assignment. Instead you will just write the code for a C++ class that will be used in the next programming assignment.

Implement a data structure that maintains integers in a sorted array. This class is described by the header file below. Your job is to implement the member functions for the class sorted_array.

 //Header File stdinc.h
  
#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <stdlib.h>
#include <stdio.h>
 
#ifndef TRUE
   #define TRUE 1
#endif
 
#ifndef FALSE
   #define FALSE 0
#endif

 

 // Header file for sorted.h 
 
#include "stdinc.h"
#define Max_Items 100
 
class sorted_array {  
   int data[Max_Item]; 
   int num_items;  
public:  
   sorted_array( ) {num_items  =  0;};
   int find(int key, int& position);
   int insert(int key); 
   int delete(int key); 
};     // sorted_array

Your programs will be graded on style and readability as well as correct code. Turn in a listing of your programs on 8 1/2 by 11 sheets. Be sure to burst the pages and staple them together if your listing is more than one page long. Of course good style is not enough, your code must also be correct to receive full credit for this assignment