# Week 1: Describing and Analyzing Algorithms

## Tuesday: Fundamentals

• Problem Descriptions
• Algorithm Descriptions: Pseudocode
• Time and Space Performance
• Algorithms and Engineering
• (Short class: Instructor leaves early for talk)

## Thursday: Analysis

• Abstracting performance
• Abstractions of big-O analysis
• The big-O notation
• Correctness of algorithms
• Partial correctness
• Total correctness

# Week 2: Iteration and Recursion

## Tuesday: Looping Over Arrays

• Scanning for array elements
• Organizing array elements
• Basic sorting: selection

## Tuesday: Looping Over Arrays

• Basic sorting: insertion
• Recursive efficient sorting: mergesort
• Counting sort

# Week 3: Recursion and ADTs

## Tuesday: Recursion On Arrays

• Binary search
• Binary search as tail recursion
• Quicksort

(short class due to HVAC issues)

# Week 4: More Recursion

## Tuesday: The PQ and The Heap

• Tree Traversal
• Inefficient PQ implementations
• Binary Heap
• Heapsort
• Trees and Graphs: Definition and Representation

## Thursday: Recurrences

• A proof of the Master Theorem
• Applying the Master Theorem
• Solving recurrences without the Master Theorem

# Week 5: Algorithms on Trees and Graphs

## Tuesday: Spanning Trees

• Depth-First Spanning Trees
• Prim's Algorithm
• Kruskal's Algorithm
• Euclidean Planar Free-Space

## Thursday: Shortest Paths; Quiz

• Dijkstra's Algorithm
• Quiz

# Week 6: Selected Topics

## Thursday: Hashing; Randomness

• Hashing
• Hash functions
• Hash tables
• Bucket hashing
• Open hashing
• Hash table grow / shrink
• Randomness

• RNGs and PRNGs
• Random distributions; shuffling
• Finding large random pseudoprimes: Miller-Rabin
• Hash Table

• Hash Function
• RNG
• PRNG

# Week 7: Selected Topics

## Tuesday: Memoization and Dynamic Programming

• Problem examples
• All-Pairs Shortest Paths as remembering
• Fibonacci and Fibonacci-time
• Let's pack a knapsack!
• Memoization
• How it works
• What it does: complexity
• Dynamic Programming
• How it works
• What it does: complexity
• Comparing memoization and dynamic programming
• When this all fails

## Thursday: NP-completeness

• Polynomial, exponential, undecidable
• Nondeterministic Computation
• Two views of NP
• super-parallel
• super-guesser
• Completeness for a class
• in the class
• hard for the class
• NP-hard and NP-complete
• The reduction method for proving hardness
• An NP-completeness proof
• The Tents problem
• Tents is in NP
• Tents is NP-hard
• Reduction from max-clique
• Why it all matters so much
• Important existing problems are NPC
• You need to watch for NPH problems