Final Study Guide

• Make sure you can do all of the previous homework and quiz/midterm questions
• Look at all of the previous study guides
• Run time, run time, run time! Make sure you can give the run time for EVERYTHING we have studied. Also make sure that you understand what it is so that you can give the run time of an algorithm that you have not seen before
• In homeworks, I have shown both informal and formal way to prove tree properties (hw3 11 and 12). Be prepared to show similar proofs. A C level answer will consist of an informal picture and an A level answer will consist of a formal proof.
• Red-black trees as covered in lecture (I covered red-black trees quite differently than the book did). Be able to do a RB tree insert (no code writing just be able to do the operation).
• Heaps - operations, building, applications, etc.
• 2-3 trees - operations, building, removing, etc. (No code writing, just be able to do the operations)
• Sorting - be able to do any sorting algorithm
• Hash tables - seperate chaining, direct addressing (how to deal with collions - linear probing, quadratic probing, and double hashing), good hash functions and table sizes, rehashing, load factor, etc
• Recursion - hopefully not something you have to study at this point
• Coding - there will be coding and it will be for something you haven't done before.