CPS 100, Spring 2004, Test 1 Bonus

You may use your books and notes in solving these problems. You may not use the Internet, you may not use a compiler, and you may not talk to anyone. For questions, please use the bulletin board for clarifications/issues.

You must turn in your work electronically using the command below. Put all your work in the README. Indicate how many hours you worked on the problem and what resources (book, notes) you consulted in doing the problems. Your submission of the work indicates your adherence to the Duke community standard/honor code.

   submit_cps100 test1 README

You may also turn in hard-copy rather than submitting your work. No submissions, hard-copy or electronic, will be counted if received after 5:00 pm on Monday, February 16.

Big-Oh

First, you might want to look at the big-Oh and recurrence questions and answers from the first test. Then do the following questions.
1. (3 points) The function reverse below returns its list parameter reversed, e.g., if list is ("ant", "bear", "dog") then the call

     list = reverse(list);
   

   makes list be ("dog", "bear", "ant")

   Node * reverse(Node * list)
   {
       if (list == 0) return 0;
       Node * tail = reverse(list->next);
       Node * first = tail;
       if (tail == 0) return list;
       
       while (tail->next != 0){
           tail = tail->next;
       }
       tail->next = list;
       list->next = 0;
       return first;
   }
   
   

   What is the big-Oh complexity of reverse? Write a recurrence and explain your answer.

2. (3 points) Another version of a reversing-function, reverse2 is given below. Write a recurrence and determine this version's big-Oh complexity.

   
   Node * reverse2(Node * list)
   {
       if (list == 0 || list->next == 0) return list;
       // list has at least two nodes
       
       Node * tail = reverse2(list->next);
       list->next->next = list;
       list->next = 0;
       return tail;
   }
   
   

3. (1 point) Explain, in words and pictures, how reverse2 works. Don't write more than a few sentences.

4. (3 points) Consider the functions below. Let T(n,m) be the time for hasSomething to execute when list has n nodes and s has m characters.

   
   bool find(Node * list, const string& s)
   {
       if (list == 0) return false;
       return list->info == s || find(list->next,s);
   }
   
   bool hasSomething(Node * list, const string& s)
   {
       if (list == 0) return false;
       if (s.length() == 0) return false;
       
       if (find(list, s)) return true;
       if (hasSomething(list->next,s)) return true;
       return hasSomething(list, s.substr(1, s.length()-1));     
   }
   
   

   Write a recurrence for hasSomething. Your recurrence may have terms with n in them, terms with m in them, and terms with both n and m in them (and, of course, O(1) as needed). The recurrences are started for you. Explain your reasoning.

      T(0,m) = O(1)
      T(n,0) = O(1)
   
      T(n,m) =
   
   

5. (3 points,may not be worth it) Extra credit, solve the recurrence you wrote showing your algebraic and logical reasoning steps.

Swapping

(6 points) Write a function that swaps pairs of nodes in a linked list. The list

   ("apple", "cherry", "dog", "cat", "orange", "blue")

should be changed to

   ("cherry", "apple", "cat", "dog", "blue", "orange")

by the call list = swapchange(list). If there are an odd number of nodes in list, then the last node isn't swapped with anything, e.g.,

  ("dog", "cat", "fish")

is changed to

  ("cat", "dog", "fish")

In writing swapchange you cannot call new and you must swap/change pointers, not info fields.

  Node * swapchange(Node * list)
  // post: pairs of nodes are swapped in list, changed list returned
  {












  }