All Homework

Homework 1

IDAA 1.1 #7
IDAA 1.3 #5 (You may photocopy that page in the book if you wish)
IDAA 1.4 #10 (It is probably easiest to give an informal, but clear and complete, description of an algorithm instead of using pseudocode.)
AIDMA Problem 1024.

Read the section and problem numbers carefully!

IDAA 2.2 #12. Give a clear description of your algorithm and prove that it requires at most O(n) steps.
IDAA 2.3 #6
IDAA 2.3 #11 (Hint: For part b, it is possible to improve the algorithm by decreasing the constant factors involved in the computation, but you won't be able to change the complexity class.)

Important Reminders:

Give a clear description of your algorithms. You may give code/pseudocode, but you must also include a short description of the algorithm since it is usually very difficult to determine what an algorithm is doing from code alone.
Don't forget to give and justify the complexity of your algorithms.
Remember to give the most efficient algorithm possible—if there is a more efficient algorithm, you will likely lose some points.

Tip: Always make sure you test your algorithms on several reasonable inputs to convince yourself they are correct.

IDAA 4.1 #5 (page 137).
IDAA 4.2 #1 (page 142). Make sure you show all of the necessary work and don't forget to give the topological sort in each case.
IDAA 4.4 #2 (page 156).
IDAA 4.4 #4 (page 156). Make sure you clearly explain your calculation(s). Your final answer should be something like "binary search is X times faster than sequential search", NOT something like "it takes X more steps". If you don't understand the difference between these statement, please ask me for clarification.
IDAA 4.5 #13 (page 167).

Important Reminders:

Give a clear description of your algorithms. You may give code/pseudocode, but you must also include a short description of the algorithm since it is usually very difficult to determine what an algorithm is doing from code alone.
Don't forget to give and justify the complexity of your algorithms.
Remember to give the most efficient algorithm possible—if there is a more efficient algorithm, you will likely lose some points.

Tip: Always make sure you test your algorithms on several reasonable inputs to convince yourself they are correct.

IDAA 5.1 #9 or #11 (page 175).

IDAA 5.2 #11 (page 182). Read the problem description carefully to make sure you understand what you can and cannot do!

IDAA 5.3 #5 (page 185).

IDAA 5.4 #7 (page 192). Also compute the product of the 4x4 matrices using the standard matrix multiplication algorithm.

IDAA 6.1 #2 (page 205) 10 points
IDAA 6.2 #2 (page 216) 5 points
IDAA 6.4 #6 (page 233) 15 points
This problem: Compute
11¹³²⁹ mod 100
by hand (That is, you are not allowed to use a calculator, computer, abacus, or any other computational device besides your brain). Use whatever algorithm you wish, but show all of your work. You are permitted to verify that your answer is correct with the use of a computer or calculator. 10 points

IDAA 7.2 #2 (page 267) 6 points. Show all of your work!
IDAA 8.1 #2 (page 290) 5 points. Use the algorithm given in the book and show your work.
IDAA 8.2 #1 (page 296) 6 points. As with the rest, show all of your work!
IDAA 8.2 #6 (page 297) 5 points. Do I need to remind you to show your work?
IDAA 8.4 #7 (page 312) 5 points. Show all of the intermediate matrices.
This problem: You can compute C(n,k) using the recursive formula C(n,k)=C(n-1,k-1)+C(n-1,k) with base cases C(n,0)=1 and C(n,n)=1 for all values of n.
1. For each of the following, specify how much time and space is required (in the worst case) to compute C(n,k) using this formula with the following types of algorithms. (6 points)
  1. A straightforward recursive algorithm based on the formula.
  2. A recursive algorithm that uses a memory function (or what I call memoization).
  3. A bottom-up approach (i.e. Compute C(1,k) for all valid values of k, then do the same for C(2,k), C(3,k), until you get to C(n,k)).
2. Which of the options above is the best and why? (2 points)
3. Is there a better algorithm than the one based on the formula given above? If so, give it and explain why it is better. (In other words, give the best algorithm you can think of to compute C(n,k)). Be specific and complete with your reasoning. (2 points)

IDAA 9.1 #9 (page 324). Assume the adjacency lists are stored in alphabetical order and start from vertex a. Give the value in the priority queue at every step of the algorithm. Draw the graph and darken the edges of the minimum spanning tree. (you may photocopy that page from the book if you wish). Finally, give the weight of the minimum spanning tree. (10 points)
IDAA 9.2 #1b (page 331-332). Show the sets for every step of the algorithm. Draw the graph and darken the edges of the minimum spanning tree (you may photocopy that page from the book if you wish). Finally, give the weight of the minimum spanning tree. (10 points)
IDAA 9.4 #1 (page 342). (15 points)