Due Date 
Reading and Practice Exercises 
Handin Exercises 
Thursday, Jan. 20

Read Sections 1.1  1.3;
Problems #5, 7, 8, 11 on pages 89; #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

 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)
 Page 8, #9 (do not look solutions up on the Internet!).
 For #9a write your algorithm in a pseudocode. Start by thinking
about how you can compute a remainder using subtraction.
 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.
 Page 1718, #2, 9.
 Page 18, #5b.
 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 5051, #14
 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 bigtheta 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

 Redo problems (if you did not receive 5 points credit already):
p. 60 #3(d) (prove both ways  using definition of bigtheta and using limits)
and #6(a)
 Redo (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 7677, #1(d), 5(a) & (b), 9
 Click here for second order
recurrence relation problems.
 Redo 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 170171, #1, 2, 3

Thursday, Mar. 24
 Page 171, #4, 6; Page 176, #2, #3
 Redo 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 inplace 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 pseudocode 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 181182, #1, 2, 6, 7; Page 187 #3


Tuesday, Apr. 12


 Written Homework: Page 264, #1., 2, 3, 4, 6
 Programming  Constructing a Graph. Click here
for details.

Thursday, Apr. 14

 Lab 5 Due

Tuesday, Apr. 19


 Redo Problems: Page 264, #3 (show how you get your answer),
#4 (give your example and give the number of comparisons as a function of
m and n; for the best case obviously the best is if the pattern is found
at the beginning of the text so only m comparisons are needed  give
an example of best case when the pattern does not appear in the text)
 Page 292, #1, 2, 6, 7, 8; Page 303 #1, 2, 3

Thursday, Apr. 21 by 11:59 pm

 Completed Topological Sorting Program 
Click here for details. NOTE:
You will get a grade on the program plus a second grade on documentation.
