# Final Review

The exam will be cumulative, this page only lists material since the midterm.

### Queues

- Definition.
- Enqueue and Dequeue.
- Array and List Implementations.

### Hash Tables

- Definition.
- Keys and values.
- Hash functions.
- Collision resolution.

### Recursion

- Definition.
- Be able to understand recursive functions.
- Be able to write recursive functions.

### Searching & Sorting

- Linear Search.
- Binary Search.
- At least one of the sorting algorithms (we have learned 4).

### Binary Search Trees

- Definition.
- Terms: root, child, parent, leaf, subtree, height.
- Tree traversals.
- Algorithm to insert.
- Algorithm to search.
- Algorithm to remove.

### Graphs

- Definition.
- Types of graphs: directed, weighted, connected complete, acyclic.
- Adjacency matrix.
- Incidence list.
- Dijkstra's algorithm.
- Prim's algorithm.

### Heaps

- Definition.
- Insertion algorithm.
- Removal algorithm.

### Huffman Codes

- Basic Idea.
- Algorithm to build the tree from a set of symbols.
- Be able to encode/decode given a tree and a sentence.

### Algorithm Analysis

- Big-O notation.
- Be able to analyze the performance of algorithms given this semester.
- Be able to analyze new algorithms.

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.