CS 4349 — Advanced Algorithm Design and Analysis

Section 501
Fall 2017
Mondays and Wednesdays 7:00pm–8:15pm
Location: AD 2.232

Jump to Schedule and Homework.

Instructor:

Kyle Fox
Office: ECSS 2.701
Phone: (972) 883-4168
Email: kyle.fox@utdallas.edu
Office Hours: Tuesdays 2:00pm–3:00pm and by appointment (enter through the ECS Student Services suite ECSS 2.502, walk all the way to the back, and turn right into the hallway just before exiting the suite)
Homepage: https://utdallas.edu/~kyle.fox/

Teaching Assistant:

Jon Crain
Office: ECSS 2.103B1 or ECSS 2.104A1 (check both)
Email: jon dot crain at utdallas dot edu
Office Hours: Mondays 4:00pm–6:00pm

TAs for other sections of 4349 are available in ECSS 2.103B1 or ECSS 2.104A1 Tuesdays 12:00pm–4:00pm, Wednesdays 2:00pm–4:00pm, and Thursdays 2:00pm–4:00pm and 6:00pm–8:00pm.

Administrivia:

Required Textbook: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition. MIT Press 2009 (CLRS)
Recommended Lecture Notes: Jeff Erickson: Algorithms, Etc.
(Please see the note about the textbook and lecture notes here.)

About this course
Course syllabus

Announcements

January 5: Homework and exam solutions have been taken offline in case any problems are used again in future semesters. Thanks for a great semester, everybody!
December 15: Solutions for the Final Exam are now available. Grades for the Final Exam are up on eLearning as well. The average score was a 38.4 out of 60. You can also view your final grade for the course on eLearning.
December 7: Solutions for Homework 11 are now available. Solutions for Homework 10 are available as well.
December 5: The Final Exam is Monday, December 11th from 8pm to 10:45pm in our normal classroom. As a reminder, you may bring one 8.5 inch by 11 inch cheat sheet of paper with notes written or printed on front and back, but no other material. Feel free to write anything you want on the cheat sheet. We will have to take the cheat sheet when you turn in your exam.

To help you prepare, Kyle is holding additional office hours: Thursday, Dec. 7th from 2–3pm; Friday, Dec. 8th from 11–12pm; and Monday, Dec. 11th from 3–4pm.

The lecture for Wednesday, December 6th will be Q/A. Please come prepared to ask about specific homework problems or problems from the readings. Thanks!
November 27: Homework 11 is now available. It is due Wednesday, December 6th, at the beginning of class.
November 8: Homework 10 is now available. It is due Wednesday, November 15th, in class. Solutions for Homework 9 are available as well.
November 1: Homework 9 is now available. It is due Wednesday, November 8th, in class. Solutions for Homework 8 are available as well.
October 25: Homework 8 is now available. It is due Wednesday, November 1st, in class. Solutions for Homework 7 are available as well.
October 18: Homework 7 is now available. As a response to the exam, it contains two extra credit problems that are easier than normal. See the homework for details. It is due Wednesday, October 25th, in class. Solutions for Homework 6 are available as well.
October 14: Midterm exam and overall midterm grades are now available on eLearning. Your overall midterm grade was calculated by dropping your lowest homework score from the first four assignments and then weighting homework and the midterm equally. Homework will count for only 30% of your grade at the end of the semester. As you might suspect, the midterm was much more difficult than anticipated. We will discuss the midterm exam and the class as a whole on Monday.
October 11: Homework 6 is now available. It is due Wednesday, October 16th, in class. Solutions for Homework 5 are available as well.
October 10: A reminder in case you missed lecture yesterday: Homework 5 is due tomorrow, October 11th, in class. Homework makes up a significant proportion of your final grade, so please be sure to turn it in!
October 9: Midterm questions and solutions are now available. Scores will be posted to eLearning by this Saturday.
October 4: The Midterm Exam is today from 7pm to 9pm in our normal classroom. As a reminder, you may bring one 8.5 inch by 11 inch cheat sheet of paper with notes written or printed on front and back, but no other material. Feel free to write anything you want on the cheat sheet. We will have to take the cheat sheet when you turn in your exam.

Good luck!
September 27: Homework 5 is now available. It is due Wednesday, October 11th, in class. Solutions for Homework 4 are available as well.
September 25: Homework 2 has been graded. You can pick it up in Kyle's office hours or Wednesday, September 27th.

Two things to note for future assignments: First, must prove your algorithm is correct to receive full credit on a homework problem; it is very unlikely that the assigned problems will have simple algorithms that are self-evidently correct. That said, proofs are not necessary on exam questions unless we explicitly specify otherwise. Second, the citation policy is there because we would prefer you figure out and attempt to understand the problems by some means rather than just giving up and leaving the answer blank. But you should not give up too quickly or you will not be prepared to use the material on the exams or after the semester ends.
September 22: The Midterm Exam will be held Wednesday, October 4th in the normal classroom from 7:00pm to 9:00pm. If you have a known conflict, tell Kyle as soon as possible and before Wednesday, September 27th at the latest.

Also, while you have seen enough in class to tackle Homework 4 Problem 1, you may want to look at the bottom of Erickson 5, page 5 for inspiration on how to obtain a slightly simpler solution than what you may think of otherwise. Regardless of how you tackle the problem, any complete O(n^2) time algorithm is worth full credit.
September 20: Homework 4 is now available. It is due Wednesday, September 27th, in class. Solutions for Homework 3 are available as well.
September 18: Grades for Homework 1 are available on eLearning. For the assignments turned in, the median score was 23.75. The minimum and maximum were 5 and 34.5, respectively. We highly recommend you pick up your graded homework to receive feedback. All graded assignments will be available during Kyle's office hours, and the latest one will be available immediately before or after lecture.
September 16: The department has scheduled pooled office hours for the CS 4349 TAs. Jon's take place in either ECSS 2.103B1 or ECSS 2.104A1 (check both) Mondays 4:00pm–6:00pm. TAs for other sections of 4349 are available in ECSS 2.103B1 or ECSS 2.104A1 Tuesdays 12:00pm–4:00pm, Wednesdays 2:00pm–4:00pm, and Thursdays 2:00pm–4:00pm and 6:00pm–8:00pm.

Kyle is changing his own office hours to Tuesdays 2:00pm–3:00pm. Feel free to email for special appointments if those times don't work. This week, he will hold office hours Monday 3:00pm–4:00pm and Tuesday 2:00pm–3:00pm to make up for the short notice on this change.
September 13: Homework 3 is now available. It is due Wednesday, September 20th, in class. Solutions for Homework 2 are available as well.
September 6: Homework 2 is now available. It is due Wednesday, September 13th, in class. Solutions for Homework 1 are available as well. We highly recommend you look over the official solutions, even if you felt comfortable doing the assignment.

Also, we have a new teaching assistant! Jon Crain will be in charge of grading homework, and he will hold office hours Tuesdays from 2:00pm to 3:00pm in ECSS 2.104A ECSS 2.103B1 some time in some place.
September 5: Homework 1 is due tomorrow in class. Please note that question 4 has been clarified since its initial release; the procedure Same takes two elements from X and returns true if they are equivalent and false otherwise. We will release solutions shortly after class if over, so late work cannot be accepted. As a reminder, we will drop the lowest homework score of the semester.

Also, we have some clarifications to course policy. To start, typesetting your homework using LaTeX, Word, etc. is not required, but it is highly recommended so that we can more easily read your solutions. Handwriting is fine if yours is neat enough. Remember, if we cannot read your solutions, then we cannot mark them correct!

Also, we will release Homework 2 tomorrow. It includes an extra credit problem. The normal policy for homework problems is that you may use any source, as long as you cite it, and still receive full credit. This policy does not extend to extra credit; you must discover and write extra credit solutions independently to receive credit.
August 30: The course syllabus has been updated with the following changes.

First, CS 3305 — Discrete Mathematics for Computing II has been added to the list of prerequisites to match the undergraduate course catalog. If you have not taken CS 3305, please contact Kyle as soon as possible. This class is likely to be very difficult without the material and practice it provides.

Second, the final exam has been scheduled. It will take place Monday, December 11th from 8:00pm to 10:45pm in AD 2.232. We are sorry you have to take the exam so late in the day.

Kyle will pass out Pre-Requisite Verification Forms again today to anybody that missed them Monday. Please fill them out by the end of lecture so he does not have to individually track you down. See you this evening!
August 28: Homework 1 is now available. It is due Wednesday, September 6th, in class. We strongly recommend you use LaTeX to typeset your work so it is easy to read. You may find this template useful.

The university of closed for Labor Day next Monday, September 4th, so Kyle will hold makeup office hours this Friday, September 1st at the usual time, 3:00pm to 4:00pm. Feel free to email Kyle for an appointment if that time or the usual Monday time do not work.

Finally, by popular demand, we are now uploading lecture notes to the course website. The first two are available in the schedule next to the recommended readings, and more will be added shortly after each lecture. Caveat emptor! These notes are essentially detailed scripts for Kyle. They may be buggy or incomplete, and unlike in lecture, nobody else will be around to ask questions or offer corrections if there are issues.
August 22: I have tentatively set my office hours to be on Mondays from 3:00pm to 4:00pm or by appointment. They should stay at that time unless the time is bad for most of the class. Getting to my office is tricky, though! You need to enter through the ECS Student Services suite at ECSS 2.502 and walk all the way to the back of the suite. Just before reaching the exit, turn right down a hallway. My office is at the end of the hallway. Sorry for the inconvenience!

The Midterm Exam is now set for Wednesday, October 4th from 7:00pm to 9:00pm.

Finally, I updated the schedule with recommended reading for Wednesday. See you then.
August 17: Welcome to CS 4349 — Advanced Algorithm Design and Analysis! All announcements, homework assignments, etc. will be done through this website. Please stay tuned!

Schedule and Homework

Lectures take place Mondays and Wednesday from 7:00pm to 8:15pm in AD 2.232.

The schedule below will be updated with new subjects and recommended readings throughout the semester. Exact topics discussed in each lecture may change. CLRS refers to Cormen et al. Erickson refers to Jeff Erickson's online lecture notes. Numbers refer to the relevant chapters or sections.

I am also linking to my notes for lecture in case you find them useful. Caveat emptor! These are basically scripts I wrote for myself, so they may be buggy or incomplete.

Date	Subject/Event	Reading	Notes
Mon, Aug. 21st	Introduction and administrivia, what is an algorithm, induction review, growth of functions and asymptotic notation	CLRS 1, 2.1–2.2, and 3.1; Erickson Appendix I; notes
Wed, Aug. 23rd	More induction, asymptotic notation continued	CLRS 3; Erickson Appendix I; notes
Mon, Aug. 28th	Recursion, divide-and-conquer, Tower of Hanoi, merge sort, recurrences	CLRS 2.3, 4–4.1, 4.3; Erickson 1–1.6; notes	Homework 1 assigned
Wed, Aug. 30th	Solving recurrences via transformations, recursion trees, and the master theorem	CLRS 4.3–4.5; Erickson Appendix II; notes
Mon, Sept. 4th	No class; university closed for Labor Day
Wed, Sept. 6th	More divide-and-conquer, quicksort, quickselect, linear time selection	CLRS 7–7.2; Erickson 1.5–1.7; notes	Homework 1 due (solutions); Homework 2 assigned
Mon, Sept. 11th	HW 1 review, linear time selection, Fibonacci numbers, dynamic programming	CLRS 9.3; Erickson 1.7, 5.1; notes
Wed, Sept. 13th	Dynamic programming, Fibonacci numbers, rod cutting	CLRS 15-15.1; Erickson 5.1, 5.3; notes	Homework 2 due (solutions); Homework 3 assigned
Mon, Sept. 18th	More dynamic programming, longest increasing subsequence, edit distance introduction	CLRS 15.3; Erickson 5.2–5.5; notes
Wed, Sept. 20th	More dynamic programming, edit distance, finding solutions and saving space	Erickson 5.1.4, 5.5; notes	Homework 3 due (solutions); Homework 4 assigned
Mon, Sept. 25th	Greedy algorithms, tape storage, class scheduling	CLRS 16–16.2; Erickson 7.1–7.3; notes
Wed, Sept. 27th	More greedy algorithms, Huffman codes	CLRS 16.3; Erickson 7.4; notes	Homework 4 due (solutions); Homework 5 assigned
Mon, Oct. 2nd	Midterm Review: Bring questions about homework or other problems!
Wed, Oct. 4th	Midterm Exam: 7:00pm to 9:00pm in AD 2.232; questions, solutions
Mon, Oct. 9th	Graph representations, graph traversal	CLRS 22–22.1; Erickson 18; notes
Wed, Oct. 11th	More graph traversal, depth-first search, DAGs	CLRS 22.2–22.4; Erickson 19–19.5; notes	Homework 5 due (solutions); Homework 6 assigned
Mon, Oct. 16th	Topological sort, midterm review	CLRS 22.4; Erickson 19.5–19.6; notes
Wed, Oct. 18th	Minimum spanning trees, Kruskal's algorithm, Borvka's algorithm	CLRS 23; Erickson 20; notes	Homework 6 due (solutions); Homework 7 assigned
Mon, Oct. 23rd	More minimum spanning trees, Jarník's (Prim's) algorithm, single source shortest paths, Dijkstra's algorithm	CLRS 24.0, 24.3, 24.5; Erickson 21.1–21.4; notes
Wed, Oct. 25th	More single source shortest paths, Shimbel's algorithm (Bellman-Ford), shortest and longest paths in DAGs	CLRS 24.1–24.2; Erickson 21.6–21.7; notes	Homework 7 due (solutions); Homework 8 assigned
Mon, Oct. 30th	All pairs shortest paths, Johnson's algorithm, dynamic programming, the Floyd-Warshall algorithm	CLRS 25.0, 25.2–25.3; Erickson 22–22.5, 22.7; notes
Wed, Nov. 1st	Maximum flows, minimum cuts, the maxflow mincut theorem	CLRS 26–proof of Theorem 26.6 (in Section 26.2); Erickson 23–23.3; notes	Homework 8 due (solutions); Homework 9 assigned
Mon, Nov. 6th	Maximum flow and minimum cut algorithms, Ford-Fulkerson, Edmonds-Karp fat pipes, Edmonds-Karp short pipes	CLRS 26.2; Erickson 23.4–23.6; notes
Wed, Nov. 8th	Applications of maximum flow and minimum cut, edge and vertex disjoint paths, maximum bipartite matching, the assignment problem, baseball elimination	CLRS 26.3; Erickson 24.1–24.5; notes	Homework 9 due (solutions); Homework 10 assigned
Mon, Nov. 13th	P vs NP, NP-hardness and NP-completeness, CircuitSAT, SAT	CLRS 34–34.4.'Formula satisfiability'; Erickson 30.1–30.3, 30.5; notes
Wed, Nov. 15th	More NP-hardness, 3SAT, MaxIndSet, MaxClique, MinVertexCover, 3Coloring, problem survey	CLRS 34.4.'3-CNF satisfiability'–34.5.2; Erickson 30.6–30.12, 30.14; notes	Homework 10 due (solutions)
Mon, Nov. 20th	No class; university closed for Fall Break
Wed, Nov. 22nd	No class; university closed for Fall Break
Mon, Nov. 27th	Amortized analysis, binary counters	CLRS 17–17.3; Erickson 15; notes	Homework 11 assigned
Wed, Nov. 29th	More amortized analysis, dynamic arrays, splay trees	CLRS 17.4; Erickson 16.5–16.8; notes
Mon, Dec. 4th	Review	notes
Wed, Dec. 6th	Review	Bring questions from homework or readings!	Homework 11 due (solutions)
Mon, Dec. 11th	Final Exam: 8:00pm to 10:45pm in AD 2.232; questions, solutions