### Algorithms Homework Assignments

Due Date Reading and Practice Exercises Hand-in Exercises
Thursday, Jan. 20 Read Sections 1.1 - 1.3; Problems #5, 7, 8, 11 on pages 8-9; #1 page 17; #5a page 18 (this is the standard algorithm using division by 2)
Tuesday, Jan. 25 Pages 24 - 26 #3, 4, 8 (represent as a graph then answer the question), 9
1. No need to do this! You are writing this algorithm in C++ for Thursday! Page 8, #4 (write your algorithm in pseudocode form similar to that used in the text)
2. Page 8, #9 (do not look solutions up on the Internet!).
1. For #9a write your algorithm in a pseudocode. Start by thinking about how you can compute a remainder using subtraction.
2. For #9b, find a formula for the number of moves possible (the formula should be in terms of m and n, the starting numbers - it also involves the gcd), explain why your formula is correct (how you got it), then base your answer to the question on the formula.
3. Page 17-18, #2, 9.
4. Page 18, #5b.
5. Page 23, #1 (Show your work in part (a), justify your answer in part (b) with reasoning if the answer is "yes" or a counterexample if the answer is "no".
Thursday, Jan. 27
• Complete the practice problems for Tuesday, Jan. 25.
• Page 50-51, #1-4
• Page 52, #9
• Page 60, #2
C++ Lab 1 due
Tuesday, Feb. 1
• Page 52, #8
• Page 60, #3b, d (prove two ways: #1 using the definition of big-theta and #2: using limits)
• Page 60, #6a.
Thursday, Feb. 3 page 67, #1(a), (b), (g), #2(b), #5 Lab #2 is due.
Tuesday, Feb. 8 Read Section 2.4, especially the description of Towers of Hanoi
• Page 67, #1 (c), 2(d), 3 (write out the algorithm for each method and count the operations), 6 (for part (c) write the summation formula and simplify it)
• Page 76, #1 (a), (b), (c), 4
Thursday, Feb. 10 Page 76, #1(e), #8
• Re-do problems (if you did not receive 5 points credit already): p. 60 #3(d) (prove both ways - using definition of big-theta and using limits) and #6(a)
• Re-do (or complete) Lab 2.
Tuesday, Feb. 15
• For each of the three string matching algorithms on the sheet handed out in class, find input for which the output is incorrect. Show where in the algorithm the problem is (that is, where the algorithm breaks down).
• Pages 76-77, #1(d), 5(a) & (b), 9
• Re-do Problems: page 67 #3 (be sure to write out the algorithm and count the individual operations as instructed), page 68 #6 (do all but for part (c) actually write the sum and solve it), page 76 #4).
Thursday, Feb. 17 Page 106, #4, 5, 6; Page 112, #1 - 3, 7
Tuesday, Feb. 22 Test #1 Lab 3 due
Tuesday, Mar. 1   page 128, #1 - 3. Note: For #2 you can have your algorithm return a pair of numbers - the largest and smallest.
Thursday, Mar. 3 page 134 #2, 5, 6 Lab 4 Due
Tuesday, Mar. 15   pages 128 - 129, #5 (use the Master Theorem), 9; pages 134 - 135, # 3, 8 (use the partition idea)
Tuesday, Mar. 22 Page 163, #3, 6 Page 164 #10 (a) (Show your work), 10(b) (give reasons if the answer is yes, a counterexample if the answer is no); Page 170-171, #1, 2, 3
Thursday, Mar. 24 Page 171, #4, 6; Page 176, #2, #3 Re-do Problems: Page 128 #2; Page 129 #9 (Modify Merge Sort to count the inversions - your modification should still sort but, in addition, count inversions), Page 134 #3 (Either prove it is stable or find a concrete counterexample and verify it works to show the algorithm is not stable); Page 135 # 8 (Find an order n algorithm that works in-place with no extra arrays).
Friday, Mar. 25 by 11:59 p.m.   C++ Implementation of QuickHull
Tuesday, Mar. 29   Page 171 #8 (write your solutions in pseudo-code similar to that used in the book); Page 176 #1, 2(a) [Prove the direction that was not done in class: If a directed graph is not a dag, then it does not have a topological sorting. Or, equivalently, if it has a topological sorting then it is a dag.], 3, 4, 5, 6, 7 (describe your method!).
Thursday, Mar. 31 Pages 181-182, #1, 2, 6, 7; Page 187 #3
Tuesday, Apr. 12
• Written Homework: Page 264, #1., 2, 3, 4, 6