# CS 4349.003.19F — Advanced Algorithm Design and Analysis

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

## 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

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)

Course syllabus

## Announcements

• November 15: Midterm 2 has been graded. Your grade is available on eLearning. The average score was just under 30 out of 40, and the standard deviation was about 5.8 points. The questions and solutions are now available as well.

• November 13: Homework 10 is now available. It is due Wednesday, November 20th by 1:00pm on eLearning. To give everybody a bit a breather, there will be no late penalty for submissions made before 1:00pm on Friday, November 22nd. As usual, submissions after 1:00pm on Friday may not be accepted so we can release solutions.

• November 8: Homework 9 solutions are now available.

• November 1: Homework 8 solutions are now available.

Midterm 2 will be held Wednesday, November 13th in the normal classroom at the normal class time. It will focus on greedy algorithms, graph data structures and searching, DFS and applications, minimum spanning trees, and shortest paths. If you have a conflict with the exam time and have not emailed Kyle about it yet, please do so as soon as possible so he can find space for the conflict exams.

Monday, November 11th will be a review day. Please come prepared to ask any questions you have about the exam subjects, about past homework problems, or even about related exercises and problems from the texts.

• October 30: Homework 9 is now available. It is due Wednesday, November 6th by 1:00pm on eLearning.

• October 25: Homework 7 solutions are now available.

• October 23: Homework 8 is now available. It is due Wednesday, October 30th by 1:00pm on eLearning.

• October 18: Homework 6 solutions are now available.

• October 16: Homework 7 is now available. It is due Wednesday, October 23rd by 1:00pm on eLearning.

• October 12: Homework 5 solutions are now available.

• October 11: Mid-term course grades are now available on eLearning and Orion. Your best three homework assignments contributed to 30% of your grade and the midterm contributed the rest.

• October 9: Homework 6 is now available. It is due Wednesday, October 16th by 1:00pm on eLearning. The normal late submission penalties apply for this homework.

• October 8: Midterm 1 has been graded. Your grade and statistics for the exam are available on eLearning. The questions and solutions are now available as well.

After Homework 4 is graded, we will figure out your midterm course grades. Tomorrow, October 9th, we'll also give you a chance to provide us some feedback on how the class is going by filling out a very short survey at the end of class.

• October 6: Kyle is almost done grading Midterm 1. He'll post everybody's Midterm 1 scores after he gives and grades a few conflict exams. He'll also post midterm course grades after the Midterm 1 and Homework 4 scores are in.

Also, you may have noticed that a couple grade columns "Total" and "Weighted Total" that were previously visible in eLearning are no longer visible. Thanks to the limited control we have over how eLearning calculates these values, keeping them visible seems worse than useless. If you are still wondering how you're doing in the class after we post midterm course grades, feel free to send Kyle an email.

• October 2: Homework 5 is now available. It is due Wednesday, October 9th by 1:00pm on eLearning. To give everybody a bit a breather, there will be no late penalty for submissions made before 1:00pm on Friday, October 11th. As usual, submissions after 1:00pm on Friday may not be accepted so we can release solutions. The normal penalties will be applied for other homework assignments after this one.

• September 27: Homework 3 and Homework 4 solutions are now available. Please look them over to get more comfortable with backtracking and dynamic programming.

• September 24: Midterm 1 will be held Wednesday, October 2nd in the normal classroom at the normal class time. It will cover algorithm analysis, solving divide-and-conquer style recurrences, and designing divide-and-conquer and dynamic programming algorithms. If you have a conflict with the exam time and have not emailed Kyle about it yet, please do so as soon as possible so he can find space for the conflict exams.

Monday, September 30th will be a review day. Please come prepared to ask any questions you have about the exam subjects, about past homework problems, or even about related exercises and problems from the texts.

• September 18: Homework 4 is now available. It is due Wednesday, September 25th by 1:00pm on eLearning.

Joe will be out of town Friday and Monday for a conference. Kyle will hold an extra office hour Friday from 2:00pm to 3:00pm in Joe's place. And don't forget that TAs for other sections of CS 4349 also hold office hours throughout the week in ECSS 2.103B1.

• September 13: Homework 2 solutions are now available. We highly recommend you look them over, especially if you're still unsure what is involved in describing and analyzing an algorithm.

• September 11: Homework 3 is now available. It is due Wednesday, September 18th by 1:00pm on eLearning.

• September 10: The LaTeX solutions template has been updated to include some pseudocode to help you describe your own algorithms.

• September 9: We have a TA! Joe Fang will grade your homework and hold office hours Mondays from 10:00am to 12:00pm and Fridays from 2:00pm to 4:00pm in ECSS 2.103B1.

And as a reminder, Homework 2 is due this Wednesday, September 11th by 1:00pm.

• September 6: Homework 1 solutions are now available.

• September 4: Homework 2 is now available. It is due Wednesday, September 11th by 1:00pm on eLearning.

Also, if you are still working to improve on proofs by induction, you may wish to look at the many examples available in Erickson I .

• August 28: Kyle will hold an extra office hour Thursday, August 29th from 1:00pm to 2:00pm to make up for next Monday being a school closure. As always, feel free to email him if you need to schedule a separate meeting.

Also, a clarification on Homework 1 Problem 1: For parts (b) and (c), you should express the watching time as $$\Theta$$ of some simple function of $$n$$. Reasonable looking (but incorrect) answers include $$\Theta(n^{500})$$, $$\Theta(\log^2 n)$$, or $$\Theta(40^n)$$. Don't forget the brief justification of your bound.

• August 26: Homework 1 is now available. It is due Wednesday, September 4th by 1:00pm on eLearning. If you wish to typeset your solutions using LaTeX, you may want to start with the solutions template.

• August 23: My own typeset lecture notes for Monday, August 23rd are now available. They contain a lot of useful information about asymptotic analysis (big-oh notation) of algorithms, so please look over them. These updated notes contain a few additions over the ones that were previously available, including a new example of analyzing a non-trivial algorithm. They have also been re-organized slightly.

The first homework will be due Wednesay, September 4th. I will release it next Monday, August 26th. You get a little more than a week thanks to the Labor Day break.

• August 20: The CS department requires everybody to fill out forms verifying they have taken the necessary prerequisites for their individual classes. Please fill out the prerequisite form using a digital signature (instructions) and submit it in the Prerequesite Form assignment on eLearning. If you're unable to do a digital signature for any reason, then please print the form, complete and sign it, scan it, and upload it to the assignment. Please do this by next Monday, August 26th. The prerequesite courses are CS 3305 with a grade of C or better, and (CE 3345 or CS 3345 or SE 3345 or TE 3345).

Also, the lecture notes for Wednesday's class have been uploaded. They will generally be uploaded the day before a class and updated the afternoon after a class to include any last minute changes. To spare your inboxes, I won't announce any more lecture note uploads after today.

Finally, we ended Monday's lecture by talking about reductions. You may want to look at Section 0.3 of Erickson for another good example of an algorithm using reductions.

• August 19: Hi all, and welcome to CS 4349, Advanced Algorithm Design and Analysis! I sincerely hope you all enjoy and get a lot out of this semester.

We'll be using eLearning for homework submissions, grade reporting, and announcements. Everything else, including the lecture schedule, reading recommendations, notes, and course policies can be found on the course website.

## 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!
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 (tentative) Midterm 2 questions and solutions
Mon, Nov. 18th NP-hardness, CircuitSAT, SAT, 3SAT Erickson 12.1–12.6; CLRS 34–34.4; lecture notes
Wed, Nov. 6th NP-hardness proofs, MaxIndSet, MaxClique, MaxVertexCover, 3Color Erickson 12.7–12.10; CLRS 34.4–34.5.3 Homework 10 due
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