Reminders
Upcoming Deadlines
Announcements
Wrap-Up
THANKS: I'm thrilled that so many of you found this course useful, fun, and intellectually challenging. Certainly I had a fantastic experience. Please accept my sincere thanks for being a part of it!
CERTIFICATES: Certificates of accomplishment have been released to the 1608 students that received at least 70 points (out of 100). My understanding is that you can download your certificate directly from Coursera.
FUTURE COURSES: While I don't have any immediate plans for new online courses, both parts of this algorithms course will re-run periodically, including later in 2013. If you didn't have time to complete the course, I really hope to see you next time around. If you did finish the course and found it useful, I hope you'll spread the word via friends, colleagues, MOOC review sites, etc. For news about future course offerings, you might keep your eye on the main Coursera page and my Google+ page.
CERTIFICATES: Certificates of accomplishment have been released to the 1608 students that received at least 70 points (out of 100). My understanding is that you can download your certificate directly from Coursera.
FUTURE COURSES: While I don't have any immediate plans for new online courses, both parts of this algorithms course will re-run periodically, including later in 2013. If you didn't have time to complete the course, I really hope to see you next time around. If you did finish the course and found it useful, I hope you'll spread the word via friends, colleagues, MOOC review sites, etc. For news about future course offerings, you might keep your eye on the main Coursera page and my Google+ page.
Mon 18 Feb 2013 6:01 PM CET
Final Set of (Optional) Lectures Posted
See Section XX -- The Wider World of Algorithms. Enjoy!
Wed 30 Jan 2013 4:11 AM CET
Info and FAQ for final exam
1. Unlike the problem sets, you have only ONE attempt, and you MUST submit your answers within 3 hours of beginning the exam. Thus DO NOT START THE EXAM until you are confident that you can concentrate on it for the following three hours.
2. There are 20 questions, and each is worth 2 points. Most are of the "select all that apply" type, rather than the strict multiple choice format of the problem sets. You will receive partial credit for each option that you leave correctly checked or correctly unchecked. (So if you mark 4 out of the 5 options for a problem correctly, you'll receive 1.6 out of the 2 points.) All questions are about material covered in the required (i.e., non-optional) videos.
3. Roughly half of the questions follow fairly directly from the lecture material (assuming that you understand it thoroughly). Roughly a quarter of the questions are variations on problem set questions. Roughly a quarter of the questions demand more thought, for example by asking you to consider whether certain results from lecture do or do not extend to more general situations.
4. You should be able to complete the exam in 90 minutes. To address any potential technical issues --- dropped Internet connections, etc. --- I'm doubling the amount of time and allowing you 3 full hours to complete the exam. Due to the number of students in the course, we won't be able to grant additional special accommodations for anybody.
5. You can take the exam anytime between now and the end of Februrary 10th (US California time, as usual). This is also the final deadline for 50% credit for all unsubmitted homeworks.
6. When you are taking the exam, be sure to save your answers frequently. To be safe, I suggest that you submit your final answers several minutes before the time expires.
7. Certificates of accomplishment will be processed at some point after February 10th. Details will be sent in a separate email.
After finishing the exam, I hope you feel a sense of pride --- this course covers a ton of seriously challenging material!
2. There are 20 questions, and each is worth 2 points. Most are of the "select all that apply" type, rather than the strict multiple choice format of the problem sets. You will receive partial credit for each option that you leave correctly checked or correctly unchecked. (So if you mark 4 out of the 5 options for a problem correctly, you'll receive 1.6 out of the 2 points.) All questions are about material covered in the required (i.e., non-optional) videos.
3. Roughly half of the questions follow fairly directly from the lecture material (assuming that you understand it thoroughly). Roughly a quarter of the questions are variations on problem set questions. Roughly a quarter of the questions demand more thought, for example by asking you to consider whether certain results from lecture do or do not extend to more general situations.
4. You should be able to complete the exam in 90 minutes. To address any potential technical issues --- dropped Internet connections, etc. --- I'm doubling the amount of time and allowing you 3 full hours to complete the exam. Due to the number of students in the course, we won't be able to grant additional special accommodations for anybody.
5. You can take the exam anytime between now and the end of Februrary 10th (US California time, as usual). This is also the final deadline for 50% credit for all unsubmitted homeworks.
6. When you are taking the exam, be sure to save your answers frequently. To be safe, I suggest that you submit your final answers several minutes before the time expires.
7. Certificates of accomplishment will be processed at some point after February 10th. Details will be sent in a separate email.
After finishing the exam, I hope you feel a sense of pride --- this course covers a ton of seriously challenging material!
Tue 29 Jan 2013 4:10 AM CET
Week 6 Overview
APPROXIMATION ALGORITHMS: NP-complete problems require compromises. If you insist on polynomial running time (and don't plan on proving that P=NP), then you need to relax correctness. The best-case scenario is a fast algorithm that produces a solution that is guaranteed to be close to an optimal one. We pursue this approach using the Knapsack problem as a case study. We use the greedy algorithm design paradigm to come up with a pretty good heuristic, and the dynamic programming algorithm design paradigm to develop a heuristic that achieves the full spectrum of running time vs. accuracy trade-offs.
LOCAL SEARCH : In the local search paradigm, one iteratively improves a solution using small (or "local") changes, until a "locally optimal" solution is reached. Local search algorithms often lack both running time and solution quality guarantees, but they can be unreasonably effective in practice. We introduce the paradigm via a concrete example --- the maximum cut problem --- and then discuss the general principles of local search. We conclude with an elegant randomized local search algorithm for the 2SAT problem, whose performance is intimately related to properties of random walks on the nonnegative integers.
HOMEWORK #6 (DUE FEBRUARY 3): The sixth and final problem set and programming assignment (both due February 3rd, or by February 10th for 50% credit) will reinforce your understanding of approximation and local search algorithms, and give you an opportunity to implement a 2SAT algorithm of your choice.
THE FINAL: The final exam will be given during the window January 28 - February 10. You should take it during that window at a time convenient for you. Details to follow in a separate email.
LOCAL SEARCH : In the local search paradigm, one iteratively improves a solution using small (or "local") changes, until a "locally optimal" solution is reached. Local search algorithms often lack both running time and solution quality guarantees, but they can be unreasonably effective in practice. We introduce the paradigm via a concrete example --- the maximum cut problem --- and then discuss the general principles of local search. We conclude with an elegant randomized local search algorithm for the 2SAT problem, whose performance is intimately related to properties of random walks on the nonnegative integers.
HOMEWORK #6 (DUE FEBRUARY 3): The sixth and final problem set and programming assignment (both due February 3rd, or by February 10th for 50% credit) will reinforce your understanding of approximation and local search algorithms, and give you an opportunity to implement a 2SAT algorithm of your choice.
THE FINAL: The final exam will be given during the window January 28 - February 10. You should take it during that window at a time convenient for you. Details to follow in a separate email.
Tue 22 Jan 2013 3:21 PM CET
Week 5 Overview
NP-COMPLETE PROBLEMS: We've now seen clever and efficient algorithms for a dazzling variety of computational problems. Sadly, many natural and important problems do not seem to admit polynomial-time algorithms. We discuss NP-completeness, which formalizes this seeming computational intractability; a simple recipe for proving that a problem is NP-complete; the famous P vs. NP question; and an overview of algorithmic approaches to NP-complete problems.
BEATING BRUTE-FORCE SEARCH : Suppose we want to solve an NP-complete problem exactly. Can we do better than brute-force search? Happily, many NP-complete problems admit search algorithms that are, while exponential-time, faster than brute-force search. We look at two case studies: a backtracking algorithm for the Vertex Cover problem, and a dynamic programming algorithm for the Traveling Salesman Problem.
HOMEWORK #5 (DUE JANUARY 27): The fifth problem set and programming assignment (both due January 27th, or by February 10th for 50% credit) will reinforce your understanding of NP-complete problems, reductions, and the dynamic programming algorithm for the traveling salesman problem.
BEATING BRUTE-FORCE SEARCH : Suppose we want to solve an NP-complete problem exactly. Can we do better than brute-force search? Happily, many NP-complete problems admit search algorithms that are, while exponential-time, faster than brute-force search. We look at two case studies: a backtracking algorithm for the Vertex Cover problem, and a dynamic programming algorithm for the Traveling Salesman Problem.
HOMEWORK #5 (DUE JANUARY 27): The fifth problem set and programming assignment (both due January 27th, or by February 10th for 50% credit) will reinforce your understanding of NP-complete problems, reductions, and the dynamic programming algorithm for the traveling salesman problem.
Tue 15 Jan 2013 6:50 AM CET
Optional Union-Find Videos Posted
The advanced optional videos for Part VIII --- the analysis of union-find data structures --- have finally been posted. For those of you looking for some seriously next-level (but beautiful) material, check them out when you get a chance.
Tue 15 Jan 2013 6:19 AM CET
Week 4 Overview
THE BELLMAN-FORD ALGORITHM: The Bellman-Ford algorithm solves the single-source shortest-path problem. While slower than Dijkstra's algorithm, it accommodates negative edge lengths and is also better suited for distributed implementations. We discuss the basic algorithm and various optimizations. Two optional videos outline some of the key ideas needed to turn the Bellman-Ford algorithm into a practical Internet routing protocol.
ALL-PAIRS SHORTEST PATHS: Why should we be content with computing shortest paths merely from a single source vertex? We can compute all-pairs shortest paths by running a single-source shortest-path algorithm once per vertex, but in many situations we can do better. Exhibits A and B: the algorithms of Floyd-Warshall and Johnson.
HOMEWORK #4 (DUE JANUARY 20): The fourth problem set and programming assignment (both due January 20th, or by February 10th for 50% credit) will reinforce your understanding of shortest paths and the dynamic programming algorithms that compute them.
DISCUSSION FORUMS: There's been lots of great discussion lately over on the discussion forums --- be sure to read and contribute to them, if you haven't already!
ALL-PAIRS SHORTEST PATHS: Why should we be content with computing shortest paths merely from a single source vertex? We can compute all-pairs shortest paths by running a single-source shortest-path algorithm once per vertex, but in many situations we can do better. Exhibits A and B: the algorithms of Floyd-Warshall and Johnson.
HOMEWORK #4 (DUE JANUARY 20): The fourth problem set and programming assignment (both due January 20th, or by February 10th for 50% credit) will reinforce your understanding of shortest paths and the dynamic programming algorithms that compute them.
DISCUSSION FORUMS: There's been lots of great discussion lately over on the discussion forums --- be sure to read and contribute to them, if you haven't already!
Mon 7 Jan 2013 5:29 PM CET
Week 3 Overview
DYNAMIC PROGRAMMING BOOT CAMP: This week is devoted to the dynamic programming design paradigm and a selection of killer applications. We'll begin in Part X by developing a linear-time algorithm for a relatively simple problem, computing a maximum-weight independent set of a path graph. Then we'll zoom out and identify the key principles of dynamic programming. The other three parts highlight three applications: the famous Knapsack problem in Part XI, the sequence alignment problem in Part XII, and computing optimal binary search trees in Part XIII.
HOMEWORK #3 (DUE JANUARY 6): The third problem set and programming assignment are out. Because of the holidays, you have three weeks to do them. As usual, if you miss the deadline you can still get 50% credit if you turn them in by the end of the course (February 10th). The problem set should reinforce the concepts and algorithms studied in the lectures, and the programming assignment asks you to implement a dynamic programming algorithm for the Knapsack problem.
HOLIDAY BREAK: After this week there's a two-week break because of the holiday season. This is also a great opportunity to catch up with the material if you've been too busy for it over the past couple of weeks. The Week 4 material will launch on January 7th. The optional Union-Find material (Part VIII) will go up over the break.
HOMEWORK #3 (DUE JANUARY 6): The third problem set and programming assignment are out. Because of the holidays, you have three weeks to do them. As usual, if you miss the deadline you can still get 50% credit if you turn them in by the end of the course (February 10th). The problem set should reinforce the concepts and algorithms studied in the lectures, and the programming assignment asks you to implement a dynamic programming algorithm for the Knapsack problem.
HOLIDAY BREAK: After this week there's a two-week break because of the holiday season. This is also a great opportunity to catch up with the material if you've been too busy for it over the past couple of weeks. The Week 4 material will launch on January 7th. The optional Union-Find material (Part VIII) will go up over the break.
Tue 18 Dec 2012 2:18 AM CET
Week 2 Overview
KRUSKAL'S MST ALGORITHM: Last week we covered Prim's MST algorithm and a blazingly fast implementation of it. There are several reasons for studying a second greedy MST algorithm, due to Kruskal. First, it's a beautiful algorithm, worthy of a greatest hits compilation. Second, to obtain a super-fast implementation of it, we'll need to learn about the simple but fundamental "Union-Find" data structure. The third reason is covered in the next section...
CLUSTERING: Clustering is an important form of unsupervised learning (i.e., extracting patterns from unlabeled data). These two videos discuss how Kruskal's MST algorithm suggests flexible and useful greedy approaches to clustering problems.
HUFFMAN CODES: Everybody loves compression. It means more songs on your smartphone, faster downloads, and so on. Huffman coding is a fundamental type of lossless compression, used for example in the MP3 standard. In these videos we'll learn about the optimality of Huffman codes, and a blazingly fast greedy algorithm for computing them.
FORTHCOMING UNION-FIND LECTURES: For those of you wondering about the missing "Part VIII", it will be purely optional material about advanced implementations of the union-find data structure. I expect it to get posted in a couple of weeks.
HOMEWORK #2 (DUE DECEMBER 23): The second problem set, due in two weeks (December 23rd), is about MSTs and Huffman codes. Note that starting this week, you get only two attempts per problem set, so pick your answers with care! As usual, if you miss the deadline you can still get 50% credit if you turn it in by the end of the course (February 10th).
The second programming assignment, also due December 23rd (with 10 attempts), asks you to implement the greedy clustering algorithm from lecture. For part (a), a straightforward implementation should suffice. Part (b) involves a graph that is likely too big to fit in your computer's memory, so answering this part will take some ingenuity. You might find this to be one of the harder programming assignments of the course, but please give it your best shot!
DISCUSSION FORUMS: I've been thrilled to see a healthy level of constructive activity on the discussion forums. Please keep it up! --- clarifications on the lectures or assignments, test cases for programming assignments, brainstorming ideas for the optional theory problems (of which I've posted 3 more), etc.
CLUSTERING: Clustering is an important form of unsupervised learning (i.e., extracting patterns from unlabeled data). These two videos discuss how Kruskal's MST algorithm suggests flexible and useful greedy approaches to clustering problems.
HUFFMAN CODES: Everybody loves compression. It means more songs on your smartphone, faster downloads, and so on. Huffman coding is a fundamental type of lossless compression, used for example in the MP3 standard. In these videos we'll learn about the optimality of Huffman codes, and a blazingly fast greedy algorithm for computing them.
FORTHCOMING UNION-FIND LECTURES: For those of you wondering about the missing "Part VIII", it will be purely optional material about advanced implementations of the union-find data structure. I expect it to get posted in a couple of weeks.
HOMEWORK #2 (DUE DECEMBER 23): The second problem set, due in two weeks (December 23rd), is about MSTs and Huffman codes. Note that starting this week, you get only two attempts per problem set, so pick your answers with care! As usual, if you miss the deadline you can still get 50% credit if you turn it in by the end of the course (February 10th).
The second programming assignment, also due December 23rd (with 10 attempts), asks you to implement the greedy clustering algorithm from lecture. For part (a), a straightforward implementation should suffice. Part (b) involves a graph that is likely too big to fit in your computer's memory, so answering this part will take some ingenuity. You might find this to be one of the harder programming assignments of the course, but please give it your best shot!
DISCUSSION FORUMS: I've been thrilled to see a healthy level of constructive activity on the discussion forums. Please keep it up! --- clarifications on the lectures or assignments, test cases for programming assignments, brainstorming ideas for the optional theory problems (of which I've posted 3 more), etc.
Sun 9 Dec 2012 10:31 PM CET
Week 1 Overview
WELCOME: Welcome to Algorithms: Design and Analysis (Part II)! The course will have six weeks of lectures and assignments, followed by a final exam. The "Syllabus" page describes the weekly topics, as well as the accompanying assignments and suggested readings. The "Course Logistics" page discusses assessment and certificates of accomplishment. Note that there is a two-week "holiday break" between the first and second halves of the course. At the beginning of each week, there will be an announcement and email summarizing the highlights of the coming week. For the course's first week, they are as follows.
TWO MOTIVATING APPLICATIONS: We begin with a fairly non-technical discussion of two motivating applications --- distributed shortest-path routing in the Internet, and sequence alignment --- to build excitement for the tools that you'll acquire later in this course.
WEEK 1 REVIEW (OPTIONAL): I'm going to assume that you're familiar with some of the topics covered in Part I, like the basics of asymptotic analysis, data structures, and graph search. If you'd like to review any of the Part I material, all of the videos from that course can be accessed through Coursera (select "Preview"). We've also collected here a selection of these videos for easy reference. I encourage you to watch them throughout the course on a "need-to-know" basis (no need to plow through all of them right away!).
INTRODUCTION TO GREEDY ALGORITHMS: The focus of this week and the next is the greedy algorithm design paradigm. These two non-technical videos discuss the pros and cons of this paradigm and describe a cool application to the optimal management of the contents of a cache.
A SCHEDULING APPLICATION: Scheduling problems come up all the time (e.g., how should a shared resource be allocated?) and greedy algorithms are often useful for them. We'll discuss a specific success story --- minimizing the weighted sum of completion times of a bunch of tasks --- in detail. The correctness proof furnishes a particularly clean example of an "exchange argument".
PRIM'S MST ALGORITHM: The minimum spanning tree (MST) problem, in addition to enjoying several applications, is a uniquely great problem for the study of greedy algorithms. Unusually, several different greedy algorithms always compute an optimal solution. We begin here with the Dijkstra-esque Prim's algorithm. The correctness proof requires understanding the subtly beautiful structure of cuts in graphs, while its blazingly fast implementation relies on a deft application of the heap data structure.
VIDEOS AND SLIDES: Videos can be streamed or downloaded and watched offline (recommended for commutes, etc.). We are also providing PDF lecture slides (with my handwritten annotations), as well as subtitle files (in English and in some cases other languages as well).
HOMEWORK #1 (DUE DECEMBER 16): The first problem set is out now, and is due in roughly two weeks (December 16th). If you miss the deadline you can still get 50% credit if you turn it in by the end of the course (February 10th). You'll normally receive 2 attempts for each problem set (we'll remember your best score), but to warm up with this first assignment you'll get 3 attempts. The problem set consists of 5 problems, about greedy scheduling algorithms and minimum spanning trees.
The first programming assignment is also out, with the same due date as the problem set. Here, we ask you to implement some of the algorithms that we've covered, run them on large inputs, and enter the answer. You can attempt each programming assignment up to 10 times. For the seasoned programmers out there looking for an additional challenge, try doing the programming assignments in a programming language that you don't already know!
DISCUSSION FORUMS: The forums play a crucial role in massive online courses like this one. If you have trouble understanding a lecture or completing an assignment, you should turn to the forums for help. After you've mastered the lectures and assignments for a given week, I hope you'll contribute to the forums and help out your fellow students. While I won't have time to carefully monitor the discussion forums, I'll check in and answer questions whenever I find the time.
OPTIONAL THEORY PROBLEMS: These are challenging problems for those of you looking to really push yourself intellectually. They are completely optional, and will not be graded. You should use the corresponding discussion forum to discuss possible solution approaches with your fellow students. I've posted the first 4, and will aim to add a few more each week.
TWO MOTIVATING APPLICATIONS: We begin with a fairly non-technical discussion of two motivating applications --- distributed shortest-path routing in the Internet, and sequence alignment --- to build excitement for the tools that you'll acquire later in this course.
WEEK 1 REVIEW (OPTIONAL): I'm going to assume that you're familiar with some of the topics covered in Part I, like the basics of asymptotic analysis, data structures, and graph search. If you'd like to review any of the Part I material, all of the videos from that course can be accessed through Coursera (select "Preview"). We've also collected here a selection of these videos for easy reference. I encourage you to watch them throughout the course on a "need-to-know" basis (no need to plow through all of them right away!).
INTRODUCTION TO GREEDY ALGORITHMS: The focus of this week and the next is the greedy algorithm design paradigm. These two non-technical videos discuss the pros and cons of this paradigm and describe a cool application to the optimal management of the contents of a cache.
A SCHEDULING APPLICATION: Scheduling problems come up all the time (e.g., how should a shared resource be allocated?) and greedy algorithms are often useful for them. We'll discuss a specific success story --- minimizing the weighted sum of completion times of a bunch of tasks --- in detail. The correctness proof furnishes a particularly clean example of an "exchange argument".
PRIM'S MST ALGORITHM: The minimum spanning tree (MST) problem, in addition to enjoying several applications, is a uniquely great problem for the study of greedy algorithms. Unusually, several different greedy algorithms always compute an optimal solution. We begin here with the Dijkstra-esque Prim's algorithm. The correctness proof requires understanding the subtly beautiful structure of cuts in graphs, while its blazingly fast implementation relies on a deft application of the heap data structure.
VIDEOS AND SLIDES: Videos can be streamed or downloaded and watched offline (recommended for commutes, etc.). We are also providing PDF lecture slides (with my handwritten annotations), as well as subtitle files (in English and in some cases other languages as well).
HOMEWORK #1 (DUE DECEMBER 16): The first problem set is out now, and is due in roughly two weeks (December 16th). If you miss the deadline you can still get 50% credit if you turn it in by the end of the course (February 10th). You'll normally receive 2 attempts for each problem set (we'll remember your best score), but to warm up with this first assignment you'll get 3 attempts. The problem set consists of 5 problems, about greedy scheduling algorithms and minimum spanning trees.
The first programming assignment is also out, with the same due date as the problem set. Here, we ask you to implement some of the algorithms that we've covered, run them on large inputs, and enter the answer. You can attempt each programming assignment up to 10 times. For the seasoned programmers out there looking for an additional challenge, try doing the programming assignments in a programming language that you don't already know!
DISCUSSION FORUMS: The forums play a crucial role in massive online courses like this one. If you have trouble understanding a lecture or completing an assignment, you should turn to the forums for help. After you've mastered the lectures and assignments for a given week, I hope you'll contribute to the forums and help out your fellow students. While I won't have time to carefully monitor the discussion forums, I'll check in and answer questions whenever I find the time.
OPTIONAL THEORY PROBLEMS: These are challenging problems for those of you looking to really push yourself intellectually. They are completely optional, and will not be graded. You should use the corresponding discussion forum to discuss possible solution approaches with your fellow students. I've posted the first 4, and will aim to add a few more each week.
Sun 2 Dec 2012 11:12 PM CET