Readings
| Week | Read By | Reading | Quiz Prompts |
|---|---|---|---|
| 1 | Monday, 2/4 | Bailey, Chapter 0 | Problem 0.1 |
| 1 | Wednesday, 2/6 | Bailey, Chapters 1 and 7 | What is "state"? |
| 1 | Friday, 2/8 | no reading | |
| 2 | Monday, 2/11 | Bailey, Chapters 2 and 3.1-3.5 |
What is the purpose of a Vector?
|
| 2 | Wednesday, 2/13 | Bailey, Chapter 4 | What is the problem with specialization? |
| 2 | Friday, 2/15 | Bailey, Chapter 5.2.1 |
Why does sum2 work? How about sum3? (try simulating on paper)
|
| 3 | Monday, 2/18 | Bailey, Chapter 5.2.2 | What is the purpose of an inductive proof? |
| 3 | Wednesday, 2/20 | mathematical induction up to (but not including) the section on variants | Prove 1 2 + 2 2 + 3 2 + ... + m 2 = m (m + 1) (2m + 1)/ 6 |
| 3 | Friday, 2/22 | no reading | |
| 4 | Monday, 2/25 | Bailey, Chapters 5.1 and 9.1-9.3 | Self-check problem 5.4 |
| 4 | Wednesday, 2/27 | Bailey, Chapter 9.4-9.5 | What can the list on p. 180 of Bailey store? |
| 4 | Friday, 2/29 | Bailey, Chapter 6.1-6.3 | Which is asymptotically faster, selection sort or insertion sort? |
| 5 | Monday, 3/4 | Bailey, Chapter 6.4, 6.7-6.8 | Merge sort is often referred to as a "divide and conquer" algorithm. Why? (you may need to do some extra digging) |
| 5 | Wednesday, 3/6 | Bailey, Chapter 6.5, 6.9 | Quicksort is frequently chosen over mergesort even though quicksort's worst-case performance is worse. Why? Note that your answer should have two parts. |
| 5 | Friday, 3/8 | Bailey, Chapter 6.6 | Think of an example input that radix sort is incapable of sorting. |
| 7 | Monday, 4/1 | no reading | (but note that Wednesday's reading is long) |
| 7 | Wednesday, 4/3 | Bailey, Chapter 10 | What feature of Java most closely models the idea of an abstract data type (ADT)? Can you think of an ADT? |
| 7 | Friday, 4/5 | Bailey, Chapter 8 | Come up with an example of an Iterator whose hasNext method never returns true. Why might this be useful? |
| 8 | Monday, 4/8 | Bailey, Chapter 11 | Are we likely to find two objects that are equal (using their equals method) to be _stored_ close together in an OrderedStructure? |
| 8 | Wednesday, 4/10 | Bailey, Chapter 12 | Sometimes data is inserted into a tree such that the tree is "lop-sided." Explain why this produces worst-case lookups for trees. Does this worst case resemble another data structure that you already know? |
| 8 | Friday, 4/12 | Bailey, Chapter 12 | Prove that efficient computation of the height of a BinaryTree must take time proportional to the number of nodes in the tree. |
| 9 | Monday, 4/15 |
Why we care about balanced trees. Bailey, Chapter 14-14.4 |
What distinguishes a binary tree from a binary search tree? |
| 9 | Wednesday, 4/17 |
Using an IDE. |
What is a conditional breakpoint? |
| 9 | Friday, 4/19 |
Bailey, Chapter 13 |
What is a heap? (note that this question asks about the heap data structure, not the region of memory, which happens to have the same name) |
| 10 | Monday, 4/22 |
no reading |
What is the matrix? |
| 10 | Wednesday, 4/24 |
Bailey, Chapter 16-16.3.2 |
How does an adjacency matrix work? How might you implement one? |
| 10 | Friday, 4/26 |
Bailey, the rest of Chapter 16 |
What is the advantage of an adjacency list over an adjacency matrix? Disadvantages? |
| 11 | Monday, 4/29 |
Excerpt from The Art of UNIX Programming (just the linked page; but read on if you want) |
What does the phrase "premature optimization is the root of all evil" mean? |
| 11 | Wednesday, 5/1 |
Bailey, Chapter 15-15.4.1 |
Why does the "last two digits" trick on p. 375 of Bailey work? |
| 11 | Friday, 5/3 |
Bailey, Chapter 15.4.2-15.4.5 |
Is it possible for a hash table to have two entries with equal keys? What is a "hash collision"? |
| 12 | Monday, 5/6 | Self-review for exam | |
| 12 | Wednesday, 5/8 | Self-review for exam | |
| 12 | Friday, 5/10 | Self-review for exam |