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, 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) |