CS 4349.004.18F — Advanced Algorithm Design and Analysis

Fall 2018
Mondays and Wednesdays 1:00pm–2:15pm
Location: ECSS 2.306

Jump to Schedule and Homework.


Kyle Fox
Office: ECSS 4.224
Phone: (972) 883-4168
Email: [email protected]
Office Hours: Mondays 2:30pm–3:30pm and Tuesdays 2:00pm–3:00pm
Homepage: https://utdallas.edu/~kyle.fox/

Teaching Assistant:

Somayeh Mohammadpour
Office: ECSS 2.103B1
Email: [email protected]
Office Hours: Thursdays 4:00pm–6:00pm


Highly Recommended Lecture Notes: Jeff Erickson: Algorithms, Etc.
"Required" Textbook: 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.
Date Subject/Event Reading Notes
Mon, Aug. 20th What is/is not an algorithm, describing algorithms, administrivia Erickson 0; CLRS 2–2.2
Wed, Aug. 22nd Proof by induction Erickson I
Mon, Aug. 27th Analyzing running time, asymptotic analysis, important functions Lecture notes; CLRS 3 Prerequisite form due; Homework 1 assigned (LaTeX solutions template)
Wed, Aug. 29th Recursion, Tower of Hanoi, Mergesort, divide-and-conquer Erickson 1–1.6 ; CLRS 2.3, 4.0
Mon, Sept. 3rd No class; university closed for Labor Day
Wed, Sept. 5th Solving divide-and-conquer recurrences using recursion trees, Karastuba multiplication Erickson 1.7, 1.9 ; CLRS 4 Homework 1 due (solutions); Homework 2 assigned
Mon, Sept. 10th More divide-and-conquer, Quicksort, linear time selection Erickson 1.5, 1.8 ; CLRS 7–7.2, 7.4.1; 9.0, 9.3
Wed, Sept. 12th Backtracking, n queens, game trees, string segmentation Erickson 2 Homework 2 due (solutions); Homework 3 assigned
Mon, Sept. 17th Dynamic programming, Fibonacci numbers, faster string segmentation Erickson 3.1–3.5 ; CLRS 15–15.1, 15.3–15.4
Wed, Sept. 19th Sequence dynamic programming, edit distance, greed is bad Erickson 3.5–3.9 ; CLRS 15.4 Homework 3 due (solutions); Homework 4 assigned
Mon, Sept. 24th Dynamic programming with more interesting memoization, longest increasing subsequence, maximum independent set in trees Erickson 3.6–3.10 ; CLRS 15.2, 15.5
Wed, Sept. 26th Greedy algorithms, class scheduling, Huffman codes Erickson 7 ; CLRS 16–16.3 Homework 4 due (solutions)
Mon, Oct. 1st Midterm review Problems from previous homework assignments, lecture notes, or the textbook
Wed, Oct. 3rd Midterm Exam: 1:00pm to 2:15pm in ECSS 2.306; questions, solutions
Mon, Oct. 8th Graph basics, representations, data structures, whatever-first-search Erickson 5 ; CLRS 22–22.2
Wed, Oct. 10th Whatever-first-search analysis, counting and labeling components, graph reductions, flood fill Erickson 5 ; CLRS 22–22.2 Homework 5 assigned
Mon, Oct. 15th Midterm debrief, midterm instructor feedback Midterm questions and solutions
Wed, Oct. 17th Depth-first search, detecting cycles, topological sort Erickson 6 ; CLRS 22.3–22.4 Homework 5 due (solutions); Homework R assigned
Mon, Oct. 22nd Topological sort, minimum spanning trees, Borůvka's algorithm Erickson 6 , 7 ; CLRS 22.4, 23
Wed, Oct. 24th minimum spanning trees continued, the Prim–Jarník algorithm, Kruskal's algorithm, single source shortest path properties (algorithms next week) Erickson 7 , 8 ; CLRS 23, 24 Homework R due (solutions); Homework 6 assigned
Mon, Oct. 29th Shortest paths, Dijkstra's algorithm, Bellman-Ford-Moore-Shimbel Erickson 8 ; CLRS 24
Wed, Oct. 31st Single source shortest paths via Bellman-Ford-Moore-Shimbel, all-pairs shortest paths, Floyd-Warshall Erickson 8 , 9 ; CLRS 24, 25 Homework 6 due (solutions); Homework 7 assigned
Mon, Nov. 5th Floyd-Warshall all-pairs shortest paths, maximum flow, minimum cut Erickson 9 , 10–10.3 ; CLRS 25, 26–26.2
Wed, Nov. 7th Maxflow-mincut theorem, maximum flow and minimum cut algorithms Erickson 10.3–10.8 ; CLRS 26.2 Homework 7 due (solutions); Homework 8 assigned
Mon, Nov. 12th Edmonds-Karp shortest augmenting paths, flow and cut applications, edge-disjoint paths, maximum matching, exam scheduling Erickson 10.7–10.8 , 11 ; CLRS 26.2–26.3
Wed, Nov. 14th NP-hardness, CircuitSAT, P versus NP, Cook-Levin theorem, SAT, 3-SAT Erickson 15.1–15.3, 15.5–15.6 ; CLRS 34–34.4.'Formula satisfiability' Homework 8 due (solutions)
Mon, Nov. 19th No class; university closed for Fall break
Wed, Nov. 21st No class; university closed for Fall break
Mon, Nov. 26 NP-hardness, MaxIndSet, MaxClique, MinVertexCover, 3Color Erickson 15.6–15.9 ; CLRS 34.4–34.5.3 Homework 9 assigned
Wed, Nov. 28th Approximation algorithms, load balancing, vertex cover Erickson 31.1–31.5 ; CLRS 35–35.1
Mon, Dec. 3rd Review Everything(?)
Wed, Dec. 5th More review Problems from past homeworks, the lecture notes, and the textbook. Homework 9 due by 1:15pm (solutions)
Wed, Dec. 12th Final Exam: 2:00pm to 4:45pm in ECSS 2.306