CSC 344
Homework 1

Assigned Jan. 26, due Feb. 5.

1. Problems 1.5, 1.6, and 1.7 on root-finding algorithms. Note that the formula at the bottom of page 7 does not agree with the one in the algorithm on page 8; the latter is right. The former should be

   x_i = (x_i-1 + (a/x_i-1)) / 2 You may want to write a little program to help with this, but that's not required.

2. Problems 1.11 and 1.15 on conversion algorithms. For 1.15, you'll presumably need a ConvertToDigit function, the inverse of the ConvertDigit function provided for 1.11.

3. Problem 1.12 on polynomial evaluation. There's a slight error in the book: it should take n+1 multiplications and n+1 additions. (At least, I haven't figured out how to do it with n multiplications and n+1 additions, and when I contacted the authors, they agreed.)

4. Problem 1.23 on recurrence relations.

5. Problem 2.1 on linked lists. Problem 2.1 seems to be missing the words "Give pseudocode...". You are to write pseudocode for a reverse function which takes a pointer to the first element of a linked list, modifies the list so that its elements are in reverse order, and returns a pointer to the first element of the new list (which used to be the last element of the old list).
   You can do this in an inefficient, O(n²)-time way, or an efficient, O(n)-time way. I prefer the latter, naturally.

6. Problem 2.3 on circular queues.

7. Problem 2.4 on linked lists using two parallel arrays instead of pointers and dynamic allocation.

8. Problem 2.9 on expression trees.