CS 6363.005.19S — Design and Analysis of Computer Algorithms

Spring 2019
Tuesdays and Thursdays 10:00am–11:15am
Location: ECSS 2.410

Jump to Schedule and Homework.

Instructor:

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

Teaching Assistant:

Jiashuai Lu
Office: ECSS 2.104A1
Email: [email protected]
Office Hours: Wednesdays 3:00pm–5:00pm

Administrivia:

Electronic Text and Assorted Notes: Jeff Erickson: Algorithms
Required Textbook for all 6363 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

Announcements


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.

Included in the readings are the scripts I used for each lecture. Use at your own risk! They are very rough and likely have typos or maybe even bugs!
Date Subject/Event Reading Notes
Tue, Jan. 15th Administrivia, what is an algorithm?, designing and analyzing algorithms Erickson 0; CLRS 2–2.2; lecture notes
Thur, Jan. 17th Asymptotic analysis, induction Erickson I, Erickson 1, Lemma 1.1; CLRS 3; lecture notes; Polished notes on asymptotics
Tue, Jan. 22nd Reduction and recursion, merge sort, divide-and-conquer, runtime recurrences Erickson 1.1–1.6; CLRS 2.3, 4.0; lecture notes
Thur, Jan. 24th Runtime recurrences, recursion trees, Karastuba multiplication Erickson 1.4–1.7, 1.9; CLRS 4; lecture notes
Tue, Jan. 29th Fast Fourier transforms Erickson A; CLRS 30; lecture notes
Thur, Jan. 29th Finishing fast Fourier transforms, selection Erickson A; Erickson 1.5, 1.8; CLRS 30; CLRS 7–7.2, 7.4.1; 9.0, 9.3; lecture notes
Tue, Feb. 5th Dynamic programming, Fibonacci numbers, rod cutting Erickson 3.1–3.5 (see Erickson 2 for more on backtracking); CLRS 15–15.1, 15.3; lecture notes Homework 1 due (LaTeX solution template) (actual solutions)
Thur, Feb. 7th Sequence dynamic programming, edit distance (see also longest common subsequence in CLRS 15.4) Erickson 3.5–3.7; CLRS 15.4; lecture notes
Tue, Feb. 12th Dynamic programming and trees, optimal binary search trees, maximum independent set in trees Erickson 2.8; Erickson 3.9–3.10; CLRS 15.5; lecture notes
Thur, Feb. 14th Finish maximum independent set in trees, greedy algorithms, class scheduling, start Huffman codes Erickson 3.10; Erickson 4.2–4.4; CLRS 16–16.3; lecture notes
Tue, Feb. 19th Finish basic greedy algorithms, Huffman codes Erickson 4.4; Erickson 5.1–5.4; CLRS 16.3; CLRS 22–22.1; lecture notes Homework 2 due (solutions)
Thur, Feb. 21st Midterm 1 review; your questions about past homeworks, concepts, or any textbook exercises you want to know more about
Tue, Feb. 26th Midterm Exam 1: 10:00am to 11:15am in ECSS 2.410 Midterm 1 problems and solutions
Thur, Feb. 28th Graph basics review, breadth-first search, depth-first search Erickson 5–5.6; Erickson 6–6.2; CLRS 22–22.3; lecture notes
Tue, Mar. 5th Depth-first search, topological sort, dynamic programming and DAGs Erickson 6–6.4; CLRS 22.3–22.4; (CLRS 24.2 for shortest paths in DAGs); lecture notes
Thur, Mar. 7th Minimum spanning trees, Kruskal's algorithm, the Prim–Jarník algorithm Erickson 7; CLRS 23; lecture notes
Tue, Mar. 12th Single source shortest paths, Dijkstra's algorithm, Bellman-Ford Erickson 8; CLRS 24; lecture notes
Thur, Mar. 14th Matroids (guest lecture by Jiashuai Lu) Erickson E; CLRS 16.4–16.5; slides Homework 3 due (solutions)
Tue, Mar. 19th No class; university closed for Spring break
Thur, Mar. 21st No class; university closed for Spring break
Tue, Mar. 26th Finish Dijkstra's algorithm, Bellman-Ford, slow all-pairs shortest paths Erickson 8; Erickson 9–9.2, 9.5; CLRS 24; CLRS 25.0 lecture notes
Thur, Mar. 28th All-pairs shortest paths with Floyd-Warshall, maximum flows, minimum cuts Erickson 9.8; Erickson 10–10.3; CLRS 25.2; CLRS 26–26.2, basic algorithm; lecture notes
Tue, Apr. 2nd Maxflow mincut theorem, Ford-Fulkerson augmenting paths, Edmonds-Karp improvements Erickson 10–10.4, 10.6–10.7; CLRS 26–26.2 lecture notes
Thur, Apr. 4th Applications of maximum flows, edge/vertex-disjoint paths, maximum bipartite matching, exam scheduling Erickson 11; CLRS 26.3 lecture notes
Tue, Apr. 9th Introduction to NP-hardness, CircuitSAT, SAT, 3SAT Erickson 12–12.6; CLRS 34–34.4 lecture notes Homework 4 due (solutions)
Thur, Apr. 11th Midterm 2 review; your questions about past homeworks, concepts, or any textbook exercises you want to know more about
Tue, Apr. 16th Midterm Exam 2: 10:00am to 11:15am in ECSS 2.410 Midterm 2 problems and solutions
Thur, Apr. 18th NP-hardness proofs, 3SAT, MaxIndSet, MaxClique, MaxVertexCover Erickson 12.6–12.10; CLRS 34.4–34.5.2 lecture notes
Tue, Apr. 23rd More NP-hardness proofs, MaxVertexCover, 3Color, HamiltonianCycle, SubsetSum Erickson 12.9–12.12; CLRS 34.5.2–34.5.5 lecture notes
Thur, Apr. 25th Semester review; your questions about anything (except Homework 5)
Tue, Apr. 30th Half a QE practice exam Exercises from Erickson and Problems from CLRS Homework 5 due (solutions)
Thur, May 2nd More QE practice exam More exercises from Erickson and Problems from CLRS
Thur, May 9th Final Exam: 11:00am to 1:45pm in ECSS 2.410 Final Exam problems and solutions