CSE326
Summer 2004
"Assignment" 7 and Final Exam study guide
8/12/2004
This assignment will not be collected or graded. It is
specifically designed to give practice with concepts in chapters 5 and
later to help you prepare for the final exam. Some of these
problems have already been recommended as practice problems.
If there is interest, we will have a review session in the middle of
next week, specifically to go over these problems and similar problems
you might have questions about. Thus, the "due" date for this
assignment is the date of that review session.
Chapter 5 (for the most part, Hashing was covered by Midterm #2 and
Assignment #6, but there still could be some final exam questions on
it).
5.1 (especially d)
5.2 remind yourself what "rehashing" is
5.7
5.9
5.10-5.11 (There is a misprint on 5.11 in some copies of the
textbook. table[hash(word)] = false true.)
Chapter 6 (for the most part, ordinary heaps
and binomial heaps were covered on Midterm #2, but there could be some
final exam questions. Also remember that we did not cover
sections 6.5-5.7 of the textbook).
6.1-6.3
6.4
6.18 a, b
6.32
6.37 a, b (don't actually program). Why is this problem in
Chapter 6?
Chapter 7. We will have to see what
actually gets covered in class, but here is a tentative list:
7.1
7.2
7.3
7.4
7.9
7.11
7.12
7.15
7.19
7.23
7.31
7.32
[8/19/2004] Finally, to think about the issues around external sorting,
take a look at 7.52. The problem is pretty underspecified, so you
need to define what constraints you solution operates under. The
following might be
reasonable: assume that "only two tape drives" also implies there are
no disk drives (at least, none available for output or work files), and
that memory is large enough to hold a number of records (but not the
whole file). Caution: this problem could drive you crazy.
Chapter 8. Although we didn't
explicitly cover union strategies ("by height", "by size") in lecture,
please review them in the textbook. Also look at the Java code
for union and find operations. It is generally quite
straightforward.
8.1
8.2
8.7 (look ahead to 8.8 as one possible clue, only if you are stuck)
8.8 a,b
Chapter 9. We had some graph problems on
midterm #2, but there is still plenty left to cover. We still may
take up another graph topic or two.
9.1
9.2
9.5
9.10a
9.11
9.12
9.15
9.21 (read the definition of "articulation points")