CS 4349.003.19F — Advanced Algorithm Design and Analysis

Fall 2019
Mondays and Wednesdays 1:00pm–2:15pm
Location: ECSS 2.201

Jump to Schedule and Homework.


Kyle Fox
Office: ECSS 4.224
Phone: (972) 883-4168
Email: kyle.fox@utdallas.edu
Office Hours: Mondays 2:30pm–3:30pm and Tuesdays 10:00am–11:00am
Homepage: https://personal.utdallas.edu/~kyle.fox/

Teaching Assistant:

Zhou(Joe) Fang
Office: ECSS 2.103B1
Email: Zhou.Fang@UTDallas.edu
Office Hours: Mondays 10:00am–12:00pm and Fridays 2:00pm–4:00pm


Electronic Text and Assorted Notes: Jeff Erickson: Algorithms
Required Textbook for all CS 4349 Sections: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, 3rd Edition. MIT Press 2009 (CLRS)

About this course
Writing policies and advice
Course syllabus


Schedule and Homework

The schedule below will be updated with new subjects and recommended readings throughout the semester. Exact topics discussed in each lecture may change.

Shortly before or after each lecture, I will update the readings with my own notes/script. Use at your own risk! I make improvements every semester, but my notes likely have typos or maybe even a few bugs!
Date Subject/Event Reading Notes
Mon, Aug. 19th Administrivia, what is an algorithm?, designing and analyzing algorithms, reductions Erickson 0; CLRS 2–2.2; lecture notes
Wed, Aug. 21st Induction, recursion Erickson I (through Section 2 plus however many examples you think would be helpful), Erickson 1–1.3; lecture notes
Mon, Aug. 26th Asymptotic notation, important functions typeset(!) lecture notes (newly overhauled for Fall 2019); CLRS 3 Prerequesite form due (instructions)
Wed, Aug. 28th Divide-and-conquer, mergesort, quicksort Erickson 1.4–1.6; CLRS 2.3, 4.0, 4.3, 7–7.1; lecture notes
Mon, Sep. 2nd No class; university closed for Labor Day
Wed, Sep. 4th Solving divide-and-conquer running time recurrences, Karatsuba multiplication Erickson 1.7, 1.9; CLRS 4.4–4.5; lecture notes Homework 1 due (LaTeX solution template) (actual solutions)
Mon, Sep. 9th Quicksort analysis, median selection Erickson 1.5, 1.8; CLRS 7–7.2, 7.4.1; 9.0, 9.3; lecture notes
Wed, Sep. 11th Backtracking, n queens, string segmentation, index notation, subset sum Erickson 2–2.1, 2.3–2.5; lecture notes Homework 2 due (solutions)
Mon, Sep. 16th Dynamic programming, Fibonacci numbers, faster string segmentation Erickson 3.1, 3.3–3.5; CLRS 15–15.1, 15.3–15.4; lecture notes
Wed, Sep. 11th More dynamic programming, edit distance Erickson 3.7; CLRS 15.4; lecture notes Homework 3 due (solutions)
Mon, Sep. 23rd Greedy algorithms, file sorting, class scheduling Erickson 4–4.3; CLRS 16–16.2; lecture notes
Wed, Sep. 25th More greedy algorithms, Huffman codes Erickson 4.4; CLRS 16.3; lecture notes Homework 4 due (solutions)
Mon, Sep. 30th Midterm 1 review featuring your questions about past homeworks, concepts, or any textbook exercises you wish to discuss
Wed, Oct. 2nd Midterm Exam 1: 1:00pm to 2:15pm in ECSS 2.201 Midterm 1 questions and solutions
Mon, Oct. 7th Graph representations, graph searching Erickson 5–5.6; CLRS 22–22.2; lecture notes
Wed, Oct. 9th Counting graphs components, graph reductions, flood fill Erickson 5.6–5.7; CLRS 22–22.2; lecture notes Homework 5 due (no penalty for late submissions up to 1:00pm Friday) (solutions)
Mon, Oct. 14th Depth-first search, detecting cycles, midterm course feedback Erickson 6–6.2; CLRS 22.3–22.4; lecture notes
Wed, Oct. 16th Topological sort, minimum spanning tree properties, Bor˚uvka's algorithm Erickson 6.3, 7–7.3; CLRS 22.4, 23–23.1; lecture notes Homework 6 due (solutions)
Mon, Oct. 21st More minimum spanning trees, Kruskal, Prim–Jarník Erickson 7.4–7.5; CLRS 23.2; lecture notes
Wed, Oct. 23rd Single source shortest paths, breadth-first search, directed acyclic graphs(???) Erickson 8–8.5; CLRS 24, 22.4, 24.2; lecture notes Homework 7 due (solutions)
Mon, Oct. 28th More single source shortest paths, Dijkstra, Bellman-Ford Erickson 8.6–8.7 (page 292); CLRS 24.1, 24.3; lecture notes
Wed, Oct. 30th Shortest paths in directed acyclic graphs, all pairs shortest paths Erickson 8.5, 9–9.5, 9.8; CLRS 24.2, 25, 25.2–25.3; lecture notes Homework 8 due (solutions)
Mon, Nov. 4th Maximum flows and minimum cuts Erickson 10–10.3; CLRS Chapter 26–Theorem 26.6; lecture notes
Wed, Nov. 6th Maximum flow/minimum cut algorithms, Ford-Fulkerson, Edmonds-Karp, matchings, exam scheduling Erickson 10.4–10.7 , 11.3–11.4 ; CLRS 26.2–26.3; lecture notes Homework 9 due (solutions)
Mon, Nov. 11th Midterm 2 review featuring your questions about past homeworks, concepts, or any textbook exercises you wish to discuss
Wed, Nov. 13th Midterm Exam 2: 1:00pm to 2:15pm in ECSS 2.201 Midterm 2 questions and solutions
Mon, Nov. 18th NP-hardness, CircuitSAT, SAT Erickson 12.1–12.5; CLRS 34–34.4; lecture notes
Wed, Nov. 6th NP-hardness proofs, 3SAT, MaxIndSet, MaxClique, MaxVertexCover, 3Color Erickson 12.6–12.10; CLRS 34.4–34.5.3; lecture notes Homework 10 due (solutions)
Mon, Nov. 25th No class; enjoy your Fall break!
Wed, Nov. 27th No class; enjoy your Fall break!
Mon, Dec. 2nd Semester overview, midterm solutions, course evaluations Midterm 1 questions and solutions, Midterm 2 questions and solutions
Wed, Dec. 4th Final exam review featuring your questions about past homeworks, concepts, or any textbook exercises you wish to discuss
Wed, Dec. 11th Final Exam: 2:00pm to 4:45pm in ECSS 2.201 Final Exam questions