January 13: Homework and exam solutions have been removed in case we want to reuse any problems in later semesters.
December 13: The final exam has been graded, and your final grades have been submitted to Galaxy. We'll make final grades visible on eLearning tomorrow after the course evaluation period has ended.
Speaking of which, you have until 11:55pm this evening (December 13th) to submit a course evaluation if you have not yet done so. Your feedback is really appreciated! It helps us know how to improve the course for future semesters, and it helps deans and others evaluate instructor performance.
Thank you all for a great semester! Have a wonderful break, and best of luck to those of you graduating this semester!
December 6: The Final Exam will be held Wednesday, December 11th in the normal classroom from 2:00pm to 4:45pm. It will cover everything we've worked on this semester including network flows, BUT it will not cover P vs. NP or NP-hardness. The exam will have six or seven questions. They may be a bit more open ended than the midterm questions, but you should still have more time to think about each question than you did for the midterms. Good luck on the exam!
November 24: Homework 10 solutions are now available.
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.
| 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 | 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 | Midterm 2 questions and solutions | |
| Mon, Nov. 18th | NP-hardness, CircuitSAT, SAT | Erickson 12.1–12.5; CLRS 34–34.4; lecture notes | |
| Wed, Nov. 6th | NP-hardness proofs, 3SAT, MaxIndSet, MaxClique, MaxVertexCover, 3Color | Erickson 12.6–12.10; CLRS 34.4–34.5.3; lecture notes | Homework 10 due (solutions) |
| Mon, Nov. 25th | No class; enjoy your Fall break! | ||
| Wed, Nov. 27th | No class; enjoy your Fall break! | ||
| Mon, Dec. 2nd | Semester overview, midterm solutions, course evaluations | Midterm 1 questions and solutions, Midterm 2 questions and solutions | |
| Wed, Dec. 4th | Final exam review featuring your questions about past homeworks, concepts, or any textbook exercises you wish to discuss | ||
| Wed, Dec. 11th | Final Exam: 2:00pm to 4:45pm in ECSS 2.201 | Final Exam questions | |