## Weekly outline

### 23 June - 29 June

# 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

**Reading:**Textbook Chapter 1### 30 June - 6 July

# 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
- Radix sort

**Reading:**Textbook 2.1, 2.4, 7### 7 July - 13 July

# Week 3: Recursion and ADTs

## Tuesday: Recursion On Arrays

- Binary search
- Binary search as tail recursion
- Quicksort

### Reading:

## Thursday: ADTs Reviewed

- Structure of an ADT

*(short class due to HVAC issues)*### 14 July - 20 July

# Week 4: More Recursion

## Tuesday: The PQ and The Heap

- Tree Traversal
- The PQ ADT
- 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

### Reading:

- Priority Queue
- Heap
- Textbook 4.1, 4.2, 8.3.1
- Master Theorem

### 21 July - 27 July

# 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**

### 28 July - 3 August

# Week 6: Selected Topics

## Tuesday: Optimized Shortest-Path

- A
^{*} All-Pairs Shortest Path

- All-Pairs

## 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 Function
- RNG
- PRNG

- A
### 4 August - 10 August

# 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

- Problem examples
### 11 August - 17 August

# Week 8: Review and Exam