The final exam goes live on May 4th. Here are some details.

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 May 4th and the end of May 17th (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. Statements of accomplishment will be processed at some point after May 17th. 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!

Wed 29 Apr 2015 9:00 AM CEST

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.

WIDER WORLD OF ALGORITHMS: These optional lectures discuss some topics that we didn't have time to cover, and are meant to encourage you to continue your algorithmic studies.

HOMEWORK #6 (DUE MAY 10TH): The sixth and final problem set and programming assignment (both due May 10th, or by May 17th 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 May 4 - May 17. You should take it during that window at a time convenient for you. Details to follow.

Sat 25 Apr 2015 9:00 AM CEST

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 MAY 3): The fifth problem set and programming assignment (both due May 3rd, or by May 17th for 50% credit) will reinforce your understanding of NP-complete problems, reductions, and the dynamic programming algorithm for the traveling salesman problem.

Sat 18 Apr 2015 9:00 AM CEST

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 APRIL 26TH): The fourth problem set and programming assignment (both due April 26th, or by May 17th for 50% credit) will reinforce your understanding of shortest paths and the dynamic programming algorithms that compute them.

Sat 11 Apr 2015 9:00 AM CEST

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 APRIL 19): The third problem set and programming assignment are out. As usual, if you miss the deadline you can still get 50% credit if you turn them in by the end of the course (May 17th). 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.

Sat 4 Apr 2015 9:00 AM CEST

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. 

UNION-FIND LECTURES: This is purely optional material about advanced implementations of the union-find data structure. For those of you looking for some seriously next-level (but beautiful) material, check them out when you get a chance.

HOMEWORK #2 (DUE APRIL 12): The second problem set, due in two weeks (April 12th), 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 (May 17th).

The second programming assignment, also due April 12th (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 might take some ingenuity.

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. 

Sat 28 Mar 2015 8:00 AM CET

It can be challenging to be successful in a MOOC, because there is not much guidance on how to take the course. This is why we'd like to share some advice to help you achieve your goals. The following tips are based on what successful students did in previous iterations of the course.

Tue 24 Mar 2015 9:00 PM CET

Hello and Welcome,

We would like to find out more about your background and motivation for taking this course. To this end, we created a short course survey for you. It is optional, but we encourage you to take it at the beginning of the class.

Thanks and see you in class!

- Tim and the Course Team

Mon 23 Mar 2015 3:00 AM CET

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 statements of accomplishment. 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 (both handwritten and typed versions), as well as subtitle files (in English and in some cases other languages as well). In most video players you can adjust the video speed to accommodate your preferred pace.

HOMEWORK #1 (DUE APRIL 5): The first problem set is out now, and is due by April 5th. If you miss the deadline you can still get 50% credit if you turn it in by the end of the course (May 17th). 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: Discussion forums play an absolutely crucial role in massive online courses, especially with an all-volunteer staff like in 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 learners. The last time this course was offered, the level of engagement on the forums was amazing! 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 learners. I've posted the first 4, and will aim to add a few more each week.

Mon 16 Mar 2015 8:00 AM CET