DSC 30 Midterm 2 Review

Source: https://docs.google.com/document/d/19YB4NZvstWpodns5EjOvDzwxOy56F8nSmbLTvvdyLO0/edit

Midterm 2 Review

1. Singly Linked Lists and Doubly Linked Lists (with/without tails):
   1. Complexity of adding, removing, searching (depending on the location and the type of the list)
   2. How to implement these methods
   3. Implementing stack/queues using SLL or DLL, how to map top/front/rear with linked lists head/tail to achieve O(1) complexity.
2. Adapter Pattern Design.
3. Inner classes
4. Inheritance and interface, idea of the polymorphism.
5. What is the purpose of the iterator?
6. 6 types of sorts: check, insertion, selection, merge, quick, counting sort. You should be able to:
   1. Understand how each of them works (invariants, algorithms for merge, insertion and quick sorts) 
   2. Trace each sort given different input arrays (Similar to the PA5 Part 1). 
   3. Know and understand the implementation of at least insertion, selection and quick sorts. 
   4. Understand running times for best, average and worst cases for all 6 algorithms.  You should be able to infer the running time of the checksort after working with it in PA05.
7. Binary trees, tree traversals. Binary search trees operations and their running times (worst and average).
   1. Insert
   2. Delete
   3. Search
   4. Find max/min
   5. Find height
8. Know the implementations of:
   1. Insert
   2. Search
   3. Find max/min
   4. Find height