Fall 2017

Here is this semester's tentative schedule; I will update it as the semester progresses. The listed sections refer to the course textbook; all notes come from Jeff Erickson's algorithms notes.

Please note that all lectures notes are provided as a resource, not a substitution for attending class! In particular, my tablet will inevitably lose notes at least a few times this semester, and you should be prepared to do extra reading and/or meet with a friend to get notes that you missed if you are gone.

DateTopicReadingLecture NotesProblem session (if any)Monday, Aug. 28 Syllabus, big-O review Intro to algorithms Lecture Notes Wednesday, Aug. 30 Big-o and induction Induction

Recurrences

RecursionLecture Notes Friday, Sept. 1 Recurrences and Recursion Recurrences

RecursionLecture Notes Friday, Sept. 8 Recursion Recursion

BacktrackingLecture Notes Monday, Sept. 11 Recursion

Dynamic ProgrammingBacktracking

Dynamic ProgrammingLecture Notes Wednesday, Sept. 13 Dynamic Programming Dynamic Programming Lecture Notes Friday, Sept. 15 Dynamic Programming Dynamic Programming Lecture Notes Monday, Sept. 18 Dynamic Programming problem session Worksheet Wednesday, Sept. 20 Greedy algorithms Greedy Algorithms Lecture Notes Friday, Sept. 22 Greedy algorithms Greedy Algorithms Lecture Notes Monday, Sept. 25 Greedy algorithms Greedy Algorithms Lecture Notes Wednesday, Sept. 27 Greedy problem session Worksheet Friday, Sept. 29 Graph algorithms: BFS and DFS Graph representations and traversals Lecture Notes Monday, Oct. 2 Graph algorithms: BFS, MST Graph representations and traversals

Minimum Spanning TreesLecture Notes Wednesday, Oct. 4 Graph algorithms: MST, SPSS Minimum Spanning Trees Lecture Notes Friday, Oct. 6 Graph algorithms: SPSS Shortest path trees Lecture Notes Monday, Oct. 9 Graphs problem session Worksheet Wednesday, Oct. 11 Flows and cuts Max flow notes Lecture Notes Friday, Oct. 13 Computing max flows Max flow notes Lecture Notes Monday, Oct. 16 Review for midterm Wednesday, Oct. 18 Midterm exam Friday, Oct. 20 Applications of flows Flow applications Lecture Notes Wednesday, Oct. 25 Recap of midterm

More applications of flowsFlow applications On board Friday, Oct. 27 Flows problem session Worksheet Monday, Oct. 30 Hardness and undecidability Reading on NP-Hardness

The Halting Problem

Layman's explanation of the halting problem

A P versus NP fairytale: the llamas of compuitingLecture Notes Wednesday, Nov. 1 NP-Hardness Reading on NP-Hardness Lecture Notes Friday, Nov. 3 NP-Hardness: Graph problems Reading on NP-Hardness Lecture Notes Monday, Nov. 6 NP-Hardness: Numeric problems Reading on NP-Hardness Lecture Notes Wednesday, Nov. 8 NP-Hardness: problem session Problems Friday, Nov. 10 Intro to approxmiation Reading on approximation Lecture Notes Monday, Nov. 13 Approxmiation algorithms Reading on approximation Lecture Notes Wednesday, Nov. 15 More approximatrion Reading on approximation Lecture Notes Friday, Nov. 17 Problem session day: approximation Problems Monday, Nov. 20 Intro to Linear Programming Intro to LP section Lecture Notes Wednesday, Nov. 29 Linear Programming Intro to LP Lecture Notes Friday, Dec. 1 Linear Programming: Simplex Simplex algorithms Lecture Notes Monday, Dec. 4 Cryptography: Intro and AES Lecture Notes Wednesday, Dec. 6 Diffie Hellman key exchange Lecture Notes Friday, Dec. 8 RSA and primality testing Nice introduction Lecture Notes