Description
An introduction to standard patterns and techniques in algorithm design and tools for analyzing algorithmic performance. Students learn to evaluate algorithms, design new algorithmic solutions, and communicate the correctness and usefulness of their solutions. Prerequisite: MATH 241 or (MATH 240 and MATH 280) and CSCI 204.
Schedule
Section | Time | Location |
---|---|---|
01: Lecture | MWF 1-1:50PM | Dana 132 |
R40: Recitation | Th 10-10:50AM | Dana 134 |
02: Lecture (Prof. Gutekunst) | MWF 3-3:50PM | BRKI 165 |
R41: Recitation (Prof. Gutekunst | Th 3-3:50PM | Dana 134 |
Syllabus
Lecture Notes
- Set 1 – Intro
- Set 2 – Example Algorithm
- Set 3 – Proof Techniques
- Set 4 – Asymptotic Analysis
- Set 5 – Recurrences
- Exam 1 Study Guide
- Set 6 – Divide & Conquer, Square Matrix Multiplication
- Set 7 – Dynamic Programming Intro
- Set 8 – Dynamic Programming Formalism
- Set 9 – Matrix Chain Multiplication
- Set 10 – Longest Common Subsequence
- Set 11 – Greedy Algorithms Intro
- Set 12 – Huffman Encoding
- Exam 2 Study Guide
- Set 13 – Data Structures
- Set 14 – B-Trees
- Set 15 – Amortized Analysis
- Exam 3 Study Guide
- Set 16 – Graph Intro
- Set 17 – Minimum Spanning Trees
- Set 18 – Shortest Paths
- Set 19 – Flows & Cuts
- Set 20 – P/NP & Undecidability
- Final Exam Study Guide
These notes closely follow CLRS (Cormen et al.’s Introduction to Algorithms), and also rely on other sources such as Kleinberg & Tardos’ Algorithm Design, and Kenneth H. Rosen’s Discrete Mathematics and its Applications. I was also influenced by my notes from taking Prasad Jayanti’s course at Dartmouth College and notes from Jennifer L. Welch at Texas A&M University.
If you want to use these notes for your own course, please just let me know! I’m also happy to share LaTeX source if that would be helpful.