COT 3100 Sect. #7094X (Fall 1999)
Homework Assignment #4:
Algorithms and Computational Complexity
Assigned Fri. 10/1, due at the start of class Wed. 10/6

All problems are taken from the textbook (Rosen), §2.1-2.2. You should also practice the odd-numbered problems in those sections, whose solutions you can check in the back of the book, or review in more detail in the student solutions guide. Practicing other even-numbered problems may also help you. Each assigned book exercise is worth 10 points out of a total of 100.

We are still using the same optional collaborative homework policy that we used in the previous assignments. (Group work is permitted, if you turn in a joint assignment.)

Unless otherwise indicated, the listed extra credit exercises are each worth 10 extra points out of the 100, up to a maximum score of 100%.

Exercises from §2.1, pp. 104-105. (Algorithms)

Ex. 4 - Devise an algorithm that computes xⁿ (for any given real number x and integer n). See hint in book.
Ex. 12 - Find an algorithm to determine the index of the last occurrence of the smallest element in a list.
Ex. 18 - Find an algorithm to test a given function for one-to-one-ness. Assume that the inputs to your algorithm are the function f(), which your algorithm may utilize, and a listing (a₁, a₂, ... ,a_n) of all n elements of f's domain A.
Exs. 24, 26 - Write a couple more algorithms.
Extra credit:
Do computer project #5 on p. 164 (20 point bonus).
Do writing project #2 on p. 164 (20 point bonus). Your essay should be at least 2 pages long and should cite at least 2 different sources.

Exercises from §2.2, pp. 111-112. (Complexity of Algorithms)

Ex. 2 - Show that a certain simple task has time complexity O(1).
Ex. 4 - Compare the complexity of two different methods of computing a double exponential.
Ex. 8 - Try out Horner's method & analyze its complexity.
Ex. 10 - See just how terrible exponentials really are.
Ex. 18 - Analyze the worst-case time complexity of your answer to Ex. 24 from §2.1.
Extra credit:
Ex. *6 - Prove that a certain weird algorithm for counting 1 bits actually works.
Do writing project #3 on p. 164 (20 point bonus). Your essay should be at least 2 pages long and should cite at least 2 different sources.

COT 3100 Sect. #7094X (Fall 1999) Homework Assignment #4: Algorithms and Computational Complexity Assigned Fri. 10/1, due at the start of class Wed. 10/6

Exercises from §2.1, pp. 104-105. (Algorithms)

Exercises from §2.2, pp. 111-112. (Complexity of Algorithms)

COT 3100 Sect. #7094X (Fall 1999)
Homework Assignment #4:
Algorithms and Computational Complexity
Assigned Fri. 10/1, due at the start of class Wed. 10/6