CS 4349 — Advanced Algorithm Design and Analysis

Section 501
Fall 2017
Mondays and Wednesdays 7:00pm–8:15pm
Location: AD 2.232

Jump to Schedule and Homework.

Instructor:

Kyle Fox
Office: ECSS 2.701
Phone: (972) 883-4168
Email: [email protected]
Office Hours: Tuesdays 2:00pm–3:00pm and by appointment (enter through the ECS Student Services suite ECSS 2.502, walk all the way to the back, and turn right into the hallway just before exiting the suite)
Homepage: https://utdallas.edu/~kyle.fox/

Teaching Assistant:

Jon Crain
Office: ECSS 2.103B1 or ECSS 2.104A1 (check both)
Email: jon dot crain at utdallas dot edu
Office Hours: Mondays 4:00pm–6:00pm

TAs for other sections of 4349 are available in ECSS 2.103B1 or ECSS 2.104A1 Tuesdays 12:00pm–4:00pm, Wednesdays 2:00pm–4:00pm, and Thursdays 2:00pm–4:00pm and 6:00pm–8:00pm.

Administrivia:

Required Textbook: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition. MIT Press 2009 (CLRS)
Recommended Lecture Notes: Jeff Erickson: Algorithms, Etc.
(Please see the note about the textbook and lecture notes here.)

About this course
Course syllabus

Announcements


Schedule and Homework

Lectures take place Mondays and Wednesday from 7:00pm to 8:15pm in AD 2.232.

The schedule below will be updated with new subjects and recommended readings throughout the semester. Exact topics discussed in each lecture may change. CLRS refers to Cormen et al. Erickson refers to Jeff Erickson's online lecture notes. Numbers refer to the relevant chapters or sections.

I am also linking to my notes for lecture in case you find them useful. Caveat emptor! These are basically scripts I wrote for myself, so they may be buggy or incomplete.
Date Subject/Event Reading Notes
Mon, Aug. 21st Introduction and administrivia, what is an algorithm, induction review, growth of functions and asymptotic notation CLRS 1, 2.1–2.2, and 3.1; Erickson Appendix I; notes
Wed, Aug. 23rd More induction, asymptotic notation continued CLRS 3; Erickson Appendix I; notes
Mon, Aug. 28th Recursion, divide-and-conquer, Tower of Hanoi, merge sort, recurrences CLRS 2.3, 4–4.1, 4.3; Erickson 1–1.6; notes Homework 1 assigned
Wed, Aug. 30th Solving recurrences via transformations, recursion trees, and the master theorem CLRS 4.3–4.5; Erickson Appendix II; notes
Mon, Sept. 4th No class; university closed for Labor Day
Wed, Sept. 6th More divide-and-conquer, quicksort, quickselect, linear time selection CLRS 7–7.2; Erickson 1.5–1.7; notes Homework 1 due (solutions); Homework 2 assigned
Mon, Sept. 11th HW 1 review, linear time selection, Fibonacci numbers, dynamic programming CLRS 9.3; Erickson 1.7, 5.1; notes
Wed, Sept. 13th Dynamic programming, Fibonacci numbers, rod cutting CLRS 15-15.1; Erickson 5.1, 5.3; notes Homework 2 due (solutions); Homework 3 assigned
Mon, Sept. 18th More dynamic programming, longest increasing subsequence, edit distance introduction CLRS 15.3; Erickson 5.2–5.5; notes
Wed, Sept. 20th More dynamic programming, edit distance, finding solutions and saving space Erickson 5.1.4, 5.5; notes Homework 3 due (solutions); Homework 4 assigned
Mon, Sept. 25th Greedy algorithms, tape storage, class scheduling CLRS 16–16.2; Erickson 7.1–7.3; notes
Wed, Sept. 27th More greedy algorithms, Huffman codes CLRS 16.3; Erickson 7.4; notes Homework 4 due (solutions); Homework 5 assigned
Mon, Oct. 2nd Midterm Review: Bring questions about homework or other problems!
Wed, Oct. 4th Midterm Exam: 7:00pm to 9:00pm in AD 2.232; questions, solutions
Mon, Oct. 9th Graph representations, graph traversal CLRS 22–22.1; Erickson 18; notes
Wed, Oct. 11th More graph traversal, depth-first search, DAGs CLRS 22.2–22.4; Erickson 19–19.5; notes Homework 5 due (solutions); Homework 6 assigned
Mon, Oct. 16th Topological sort, midterm review CLRS 22.4; Erickson 19.5–19.6; notes
Wed, Oct. 18th Minimum spanning trees, Kruskal's algorithm, Borvka's algorithm CLRS 23; Erickson 20; notes Homework 6 due (solutions); Homework 7 assigned
Mon, Oct. 23rd More minimum spanning trees, Jarník's (Prim's) algorithm, single source shortest paths, Dijkstra's algorithm CLRS 24.0, 24.3, 24.5; Erickson 21.1–21.4; notes
Wed, Oct. 25th More single source shortest paths, Shimbel's algorithm (Bellman-Ford), shortest and longest paths in DAGs CLRS 24.1–24.2; Erickson 21.6–21.7; notes Homework 7 due (solutions); Homework 8 assigned
Mon, Oct. 30th All pairs shortest paths, Johnson's algorithm, dynamic programming, the Floyd-Warshall algorithm CLRS 25.0, 25.2–25.3; Erickson 22–22.5, 22.7; notes
Wed, Nov. 1st Maximum flows, minimum cuts, the maxflow mincut theorem CLRS 26–proof of Theorem 26.6 (in Section 26.2); Erickson 23–23.3; notes Homework 8 due (solutions); Homework 9 assigned
Mon, Nov. 6th Maximum flow and minimum cut algorithms, Ford-Fulkerson, Edmonds-Karp fat pipes, Edmonds-Karp short pipes CLRS 26.2; Erickson 23.4–23.6; notes
Wed, Nov. 8th Applications of maximum flow and minimum cut, edge and vertex disjoint paths, maximum bipartite matching, the assignment problem, baseball elimination CLRS 26.3; Erickson 24.1–24.5; notes Homework 9 due (solutions); Homework 10 assigned
Mon, Nov. 13th P vs NP, NP-hardness and NP-completeness, CircuitSAT, SAT CLRS 34–34.4.'Formula satisfiability'; Erickson 30.1–30.3, 30.5; notes
Wed, Nov. 15th More NP-hardness, 3SAT, MaxIndSet, MaxClique, MinVertexCover, 3Coloring, problem survey CLRS 34.4.'3-CNF satisfiability'–34.5.2; Erickson 30.6–30.12, 30.14; notes Homework 10 due (solutions)
Mon, Nov. 20th No class; university closed for Fall Break
Wed, Nov. 22nd No class; university closed for Fall Break
Mon, Nov. 27th Amortized analysis, binary counters CLRS 17–17.3; Erickson 15; notes Homework 11 assigned
Wed, Nov. 29th More amortized analysis, dynamic arrays, splay trees CLRS 17.4; Erickson 16.5–16.8; notes
Mon, Dec. 4th Review notes
Wed, Dec. 6th Review Bring questions from homework or readings! Homework 11 due (solutions)
Mon, Dec. 11th Final Exam: 8:00pm to 10:45pm in AD 2.232; questions, solutions