# COM1100 Final Exam Program

The Final Examination for COM1100 will cover the following topics. For a few topics I supply questions which should be perfectly clear once the relevant material is understood. On the exam, you will be expected to write short programs that answer similar questions.

Chapters 2 (all), 4 (4.1--4.9), 5 (5.1--5.4, 5.6), 6 (6.1--6.3, 6.8), 7 (7.1--7.3), 10 (10.1--10.4)
Also, be sure to look through the "Points to Remember" sections of these chapters.

Topics:

• ### Basic arithmetic (+, -, *, /, %). Integer division, remainder.

• Given the duration of a period of time in minutes, express it in weeks, days, hours and minutes.

• ### Basic algorithmic constructs: If, For, While.

• Print the first 500 prime numbers.

The following code segment assumes that a function bool is_prime( int x ) that returns true if its argument is a prime number and false otherwise, is available.

```      int primes_found = 0, x=2;
while( primes_found <= 500 ){
if( is_prime(x) ){
cout << x << endl;
primes_found++;
}
x++;
}
```
• Compute the greatest common divisor of two positive integers.

The following code implements Euclid's Algorithm, which is based on the observation that for any positive integers a, b such that a > b GCD(a,b) = GCD(a-b,b). The subtraction eventually gets the numbers down to their GDC.

```      int c;
if( a <=0 || b<= 0 ){
cout << "Bad input: exiting. ";
exit(-1);
}
while( a> 0 && b> 0 ){
// swap a,b if a < b
if( a < b ){ c=a; a=b; b=c; }
// we have ensured a <= b
a = a-b;
}
cout << b ;  //this is the result -- why?
```
Step through Euclid's algorithm for a few pairs of numbers, and then step through the code to see how this implementation works.

• Input a positive integer N and draw a chessboard of N x N squares.

Instead of drawing squares we are going to print a pattern of '-' and '*' (for black and white squares). The main idea of the solution is the two nested loops. The following solution takes advantage of the fact that black and white squares of a chessboard alternate.

```        int N;
cout << "Enter Board Size: ";
cin >> N;
bool white = false;       // is this square white?
for( int i=0; i < N; i++){
for( int j=0; j < N; j++){
if( white ) {
cout << "-";
white = false;      // change the value to its opposite
}
else {                // black
cout << "*";
white = true;
}
}
cout << endl;       // go to the next row
}
```
• ### Functions: passing parameters by value and by reference, returning a value from a function. Local and global variables.

• Suppose a function foo performs a mathematical computation. How is printing the result different from returning it?

Printing only results in the value being displayed (on the screen). It cannot be used in subsequent computations. On the other hand, the return operator allows for reuse of the returned value, say, in an assigment or an arithmetic expression. Standard mathematical functions like abs and sqrt do not print anything, but return their results, which makes possible statements like
x = 1.0 + sqrt(5);

• What happens to the local variables when a function completes execution? How can several functions share a variable?

Local variables get destroyed, together with the rest of the activation record of the function. The only value that survives is the value return-ed from the function.

• A computation may produce several answers (e.g. a quadratic equation most often has two different solutions), but a function can return only one value. How can a function communicate several values back to its caller?

A call by reference can be used to assign the results to some variables from the caller function. The following example explains the quadratic equation formula.

```        // this program solves quadratic equations
int main(){
double a, b, c, x1, x2;
while( true ){       // forever
cout << "Enter a, b, c of a quadratic equation : ";
cin >> a, b, c;
bool ok;
ok = solve_quadratic( a, b, c, x1, x2 );
if( ok )    // equation had solutions, print them
cout << "The solutions are " << x1 << ", " << x2 << endl;
else        // there were no solutions, x1, x2 were not set
cout << "Sorry, no solutions for this equation\n";
}
}

// this function returns true if solutions were found, and
// false if there were none. This is done to let the
// calling program know if sol1 and sol2 were changed
bool solve_quadratic( double a, double b, double c,     // coeffs
double& sol1, double& sol2 ){
double D = b*b - 4*a*c;   // the discriminant
if( D < 0 )
return false;           // no solutions exist, indicate failure
else {
double sq = sqrt(D);
sol1 = (-b + sq)/(2*a);
sol1 = (-b - sq)/(2*a);
return true;            // indicate success
}
}
```

• Write the function that returns the nearest perfect square to a given positive integer. (Example: 9 for 10, 64 for 60.)

Left as an exercise.

• Write a function that swaps the values of its arguments (which it takes by reference).
```      void swap( int& x, int& y ){
int z = x;
x = y;
y = z;
}
```
• If each task in these questions had to be implemented as a function, what arguments would it take and what values would these functions return?

Left as an exercise.

• ### Arrays.

Assume the following declarations:

```      const int N = 10;
double a[N];
// then a gets initialized
```

• Find the sum and the average of an array of numbers.
```      double sum = 0;
for( int i=0; i < N; i++ )
sum += a[i];
cout << "Sum = " << sum << ", Average = " << sum/N << endl;
```
• Find the largest and the smallest number in an array of numbers.

The idea is to traverse the array (same as in all other such problems), keeping track of the largest and smallest array element seen so far:

```      double min = a[0], max = a[0];
for( int i=0; i < N; i++ ){
if( max < a[i] ) max = a[i];
if( min > a[i] ) min = a[i];
}
cout << "Max = " << max << ", Min = " << min << endl;
```
• Count the number of times a given character occurs in an array of characters.

I will assume here that the character array is in fact an old "C-style" zero-terminated string, declared somewhere above as char str[ ] .

```      int k=0;             // current character position
int counter = 0;     // the counter
while( str[k] != '\0' ){
if( ch == str[k] ) counter++;
}
cout << "Character " << ch << " occurs in "
<< str << counter << " times.\n";
```
• Sort an array of numbers (any method).

What follows is called BubbleSort. Find another method in your text.

```      bool any_swaps = true;
while( any_swaps ){  // while there were swaps on the previous
// pass, make another pass.
for( int i=0; i < N-1 ; i++ ){    // note N-1 -- why?
any_swaps = false;                // reset swap flag
if( a[i] > a[i+1] ){              // disorder, so swap
double aux = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
any_swaps = true;
}
}
}
// there were no swaps on the last pass, i.e. the array is
// now ordered
```

Notice that the body of the while loop can be used to check if the array is ordered.

• Given an array of integers (positive or negative), count how many different numbers occur in it (Hint: first solve this problem for a sorted array).

Left as an exercise -- highly recommended!

• ### Passing arrays as arguments to functions.

• Do the above array tasks as functions.

All such functions require at least two arguments -- the name of the array (actually, the pointer to the first element of the array in the memory), and the length of the array (required for the loop that traverses the array)

```      double array_sum( double x[ ], int len ){
double sum;
for( int i=0; i < len; i++ )
sum += x[i];
return sum;
}
```
• Write a function that compares two arrays (of the same given length) and decides if they are equal entry-wise.
```      bool array_compare( double x[ ], double y[ ], int len ){
for( int i=0; i < len; i++ ){
if( x[i] != y[i] ) return false; // return immediately
}
return true; // if the loop finished, then all elements were equal
}
```
• ### Characters. Strings. Old style zero-terminated character arrays and the new C++ string class library.

Like with an array, you can access individual characters in a string by using the subscript operator [ ]. Unlike an array, the C++ string allows many operations such as concatenation ("+"). A string also knows it length, returned for the particular string by the member function .length().

• Write a function that counts the number of vowels in a string.
```      int CountVowels( string s ){
int count = 0;
char ch;
for( int k=0; k < s.length(); k++){
ch = s[k];     // extract k-th character
if( ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
count++;
}
return count;
}
```
• Write a function that takes a string and returns the inverted string (the original string read backwards).
```      string InvertString( string s ){
string res = "";                 // result
for( int k = s.length()-1 ; k >=0 ; k--) res += s[k];
return res;
}
```
• Write a function that removes all spaces from a given string and returns the resulting squashed string (without spaces).
```      string SquashString( string s ){
string res = "";                     // result
for( int k=0 ; k < s.length(); k++ ){
if( s[k] != ' ' ) res += s[k];
}
return res;
}
```
• Write a function that takes a string and converts all character in it to lowercase. Make this function change its actual argument.
```      string ToLowerCase( string& s ){       // pass by reference
for( int k=0 ; k < s.length(); k++ ){
if( s[k] >= 'A' && s[k] <='Z' )    // s[k] is uppercase
s[k] = s[k] - 'A' + 'a';         // s gets changed here
}
}
```
• Check if a string is a palindrome (i.e. reads the same way from left to right and from right to left).

Left as an exercise -- highly recommended!

• ### Binary numbers, negative numbers, signed an unsigned.

• Write 97 as a binary number. Write '1011010' as a decimal number.

97 dec. = 1100001 bin. , 1011010 bin. = 90 dec.

• Assuming that an integer is stored in 4 bytes of memory, write the "two's complement" representation of -11.

The representation of -N (for a positive integer N) can be obtained as follows:

• write the binary representation of N-1
• invert it bit-wise and pad with 1's on the left
Hence: -11 is 11111111 11111111 11111111 11110101 (since 10 dec. = 1010 bin.)

• What is the integer value of '10110101' if understood as a signed char? As an unsigned char?

As unsigned, the leftmost bit stands for 128's, so 10110101 = 128 + 32 + 16 + 4 + 1 = 181 dec.

As signed, the leftmost bit stands for the sign, and the rest for the two's complement. Inverting the right 7 bits 0110101 we get 1001010 bin. = 74 dec. So '10110101' stands for -75 .

• ### Files.

• Write a program that prompts for the name of a file, attempts to open it and, if successful, prints the number of lines, words and characters in it. (This program is called wc under UNIX.)

See my tutorial on files.

• Write a program that counts how many times a given word occurs in a given file.

• Write a "censor" program that inputs a list of "bad" words and a filename, and writes another file that contains the original text with those words removed. (Assume that there is a firm limit on the number of different "bad" words your censor can cover).

Sergey Bratus