| 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
|
- 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 17-18, #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 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
- Click here for second order
recurrence relation problems.
- 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
- Programming - Constructing a Graph. Click here
for details.
|
| Thursday, Apr. 14
|
| Lab 5 Due
|
| Tuesday, Apr. 19
|
|
- Re-do 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.
|