These questions are provided for students who have completed COMP125 and are following-on into COMP225.

COMP125 is a prerequisite for COMP225; but of course COMP255 introduces a great deal of new material, and we will have very little time available to 'take out' of the COMP225 schedule for revision of COMP125 topics. That is, we will be making the very reasonable assumption that you have a good grasp of COMP125.

In order to help make sure that's true, and as a helpful tool for your own revision in any case, the following 'quiz' is provided to test your knowledge of the prerequisites for COMP225. If you have any difficulties answering the quiz questions then it is very important that you take the time to re-familiarise yourself with the material, using the text book. In addition, you are of course always welcome to come and see me, during my consultation times, to discuss any difficulties that you may have (whether to do with revision or otherwise).

Questions marked with an asterisk (*) might indicate a higher level of difficulty, and they might be covered in tutorials.

Testing and debugging programs

The following programs will compile correctly, but there is still something qrong with them. What tests could you use to discover the bugs? (ie what is the input and what is the correct expected output? What does the program actually produce? If it's not the same as the output you expect, then the program is buggy.) How would you correct the bugs? If you do not know what is wrong with them just by inspecting the code, try compiling and running the programs.

1. This program is supposed to classify a stream of pairs of input numbers.

          
     int c, k;
     while (cin >> c) {
       cin >> k; 
       if (c > k) cout << c << " is greater than " << k << endl;
       else cout << c << " is smaller than " << k << endl;
     }  
   

2. This program is supposed to calculate factorials.

     int factorial (int n); {
     // PRE:  n >= 0
     // POST: if (n == 0) returns 1
     //       if (n >  0) returns n! = 1*2*...*(n-1)*n
     
       int fac;
       fac= 1;
       while (n--) {
         fac*= n;
       } 
       return fac;   
     }
   

3. This program is supposed to print-out a null-terminated string, one character per line.

     int i= 0;
     do {
       cout << ss[i++] << endl;
     } while (ss[i] != '\0');   
   

4. This program is intended to examine an input number and print some information about it.

     int a;
     string s;
   
     cin >> a;     
     switch (a) {   
       case '0':  s= "Zero.";
       case '1':  s= "One.";
       case '2':  s= "Two.";
       default:   s= "Greater than two.";
     }
     cout << s;
   

5. (*) This function is supposed to compute the length of its array argument (at run-time).

     int calcLen (int A[]) {
       return sizeOf(A)/sizeOf(int);
     };
   

Pointers

1. What happens in memory when the pointer

       int *p;
     

   is declared? How does that compare with the declaration

     int x;
     

2. What happens in memory with the execution of

      p= new int;
    

3. What happens in memory with the execution of

      delete p;
    

   Is the value of p destroyed immediately?
4. What does

      p= NULL;
    

   mean?
5. Why is it more efficient to pass a pointer to a struct (as a function argument, say) rather than the struct itself?
6. Write the code for inserting a node at the front of a linked list. Write the code for inserting an item at the end of a linked list.
7. How is the last item in a linked list identified?
8. Write code for traversing a linked list, printing out the items at each node, as they are encountered.
9. Is it possible to implement binary search efficiently on a linked list? Explain your answer.

Dynamic data structures

1. How does a queue differ from a stack (in terms of adding and removing items)?
2. In a pointer-based implementation of a queue, what pointer information is needed to
   1. Push an item onto the queue efficiently?
   2. Pop an item from the queue efficiently?
3. In a pointer-based implementation of a stack, what pointer information is needed to
   1. Push an item onto the stack efficiently?
   2. Pop an item from the stack efficiently?

Recursion

• The recursion must stop at some point i.e. there must be a base case (sometimes more than one!)
• The smaller problems must actually approach the base case;
• The solutions to the smaller problems must really be used somehow to reconstruct a solution to the original problem.

1.  
             int fact1(int n) {
               return n * fact1(n-1);         
              }       
           

2.  
             int fact2(int n) {
               if (n == 0 ) return 1;
               else return n*fact2(n);         
              }       
           

3.           bool isPalindrome(string s) {
             // Returns true iff s is a palindrome
             
             if (s.length() <= 1) return true;
             else return isPalindrome(s.substr(1, s.length()-2);
             }
          

4.           int silly (int n) {
               if (n=0) return 1;
               else return n + silly (n-2);
             }
     
         

(*) General problem-solving.

While the exercises above have covered some of the details of C++ specifically, its syntax and the meaning of some of its constructs, that is not really what programming is about. (Consider the difference between knowing what words mean in a spoken language, and being able to speak or write well in it.)

Real and durable programming skills are programming-language independent; and people who have them can easily carry their expertise from one language to another. (Usually they can absorb the details of a new language over a couple of weekends, since they already know what to look for.)

Thus the following exercises are the important ones, and they are not so much to do with C++ as to do with algorithms in general. When thinking about them, remember that your aim is to make the program as simple and as obviously correct as possible. This may mean that the first approach you might think of is not necessarily the best.

1. Now suppose that you want to compare two strings to see whether they are the same, ignoring case. For example, if s = "helLo", u= "Hello" and t= "HELLO", they would now all be considered to be the same. Can you find a strategy that examines each letter in each string no more than once? How would you implement that recursively? How many recursive calls are required (in terms of the lengths of the input strings)?

2. Suppose you have two (long!) lists, each containing integers (although the type is unimportant), and that neither list has any repetitions. How would you discover (that is, what kind of algorithm would you use in a program that discovers) whether one of the lists can be rotated until it is the same as the other? (Recall that rotating a list means that position n becomes position n+1, and that the last element is "rotated" to the first position.) For example [1,2,3] should be considered the same as [3,1,2] (up to rotation) but not the same as [2,1,3].

   A brute-force technique might involve comparing all possible rotations of one list agains the other: it would take time proportional to the square of the length of the lists. But (of course) there's no point unless the lists are the same length, since otherwise they cannot be simple rotations of each other. Thus the first step is to scan through the lists and find the length of each. If those lengths differ, then answer "false" straight away. Otherwise, carry on... In any case, only linear time has been used so far (that is, time proportional to the list length).

   See whether you can complete this algorithm still using only linear time. (Hint: Find the lists' minimum elements.)