Day 23: Final Project Workday

Announcements

Oral Quiz 2

Please remember to sign up for a slot for your oral quiz (link is in the Canvas assignment page). This assignment may not be done late unless you are seriously ill or have a specific accommodation.

Reminder: final project deliverables

If you haven’t already, please turn in your final project check-in 1 assignment. If we spoke in class, but you didn’t turn in the written part, please indicate that as a comment on the Canvas assignment (I will waive the late penalty if this was the case).

Oral Quiz 2 Topic List (and some time for review)

As a reminder, this is the scope of the quiz.

This quiz covers the material in the class post assignment 4 (Divide and Conquer, Associative Arrays and Hashing, and KD-Trees / Binary Search Trees). If something was marked as optional, it will not be part of the quiz.

To help you in your studying, here are a list of things we covered in this part of the class.

  • We continued to explore the idea of divide and conquer algorithms. We saw some problems on day 10 that used this idea.
  • You implemented Strassen’s algorithm and compared its performance to the typical, $\Theta(n^3)$ approach. We also can understand its runtime by using the master theorem.
  • We learned about dynamic programming as a systematic way to solve problems (see day 10). We did some practice problems involving changemaking as well as stairclimbing. On day 11 we did some more practice problems. There are also some problems on day 12.
  • You learned about the problem of DNA sequence alignment and implemented either Needleman-Wunsch or Smith-Waterman.
  • We learned about the notion of an associative array and saw two strawman methods of implementing one (association lists and array maps). We learned about the concept of a hashing function and showed how it could be used to create an associative array (either with separate chaining or direct addressing).
  • We learned about the computational complexity of various operations on a hash map.
  • We learned about the Lempel-Ziv algorithm and how it can be used as a lossless compression algorithm.
  • You implemented an associative array using a hash table. You also either implemented Markov text analysis or Lempel-Ziv encoding.
  • You learned about the concept of a binary search tree, the notion of balance in a binary search tree, and how balance relates to runtime of looking for an element in the tree.
  • You learned about red-black trees, tree rotations, and how the properties of a red-black tree can be maintained by performing recoloring and rotation.
  • You learned about the nearest neighbor search and k-d trees. You implemented your own k-d tree and explored how the runtime of k-d trees compared to brute-force search as the number of points and the dimensionality of the data change.

Worktime

Let’s use today to keep momentum on final projects.