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.

Instructor:

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

Administrivia:

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

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.

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, subset sum(?) Erickson 3.6–3.7; CLRS 15.4 Homework 3 due
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 (tentative)
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 (tentative)
Mon, Nov. 25th No class; enjoy your Fall break!
Wed, Nov. 27th No class; enjoy your Fall break!
Wed, Dec. 11th Final Exam: 2:00pm to 4:45pm in ECSS 2.201 (tentative)