Welcome to Week 7 of Algorithms, Part II. We have released the course materials for the week: three lectures, three sets of exercises, three sets of job interview questions, and a final exam.

• Exercises: due two weeks after they are released.
  

• Job interview questions: ungraded and for your own enrichment.
  

• Final exam: due two weeks after it is released.
  

Our lectures this week are centered on the idea of problem-solving models like maxflow and shortest path, where a new problem can be formulated as an instance of one of those problems, and then solved with a classic and efficient algorithm. To complete the course, we describe the classic unsolved problem from theoretical computer science that is centered on the concept of algorithm efficiency and guides us in the search for efficient solutions to difficult problems.

Lecture: Reductions. In this lecture our goal is to develop ways to classify problems according to their computational requirements. We introduce the concept of reduction as a technique for studying the relationship among problems. People use reductions to design algorithms, establish lower bounds, and classify problems in terms of their computational requirements.

Lecture: Linear Programming (optional). The quintessential problem-solving model is known as linear programming, and the simplex method for solving it is one of the most widely used algorithms. In this lecture, we given an overview of this central topic in operations research and describe its relationship to algorithms that we have considered.

Lecture: Intractability. Is there a universal problem-solving model to which all problems that we would like to solve reduce and for which we know an efficient algorithm? You may be surprised to learn that we do no know the answer to this question. In this lecture we introduce the complexity classes P, NP, and NP-complete, pose the famous P = NP question, and consider implications in the context of algorithms that we have treated in this course.

Exercises. Drill exercises on the lecture material.

Job Interview Questions. Algorithmic interview questions based on the lecture material.

Suggested readings. Section 6.5—6.6 (pp. 903-921) in Algorithms, 4th edition.

Final Exam. The final exam consists of multiple-choice and short-answer questions about the course materials.

Fri 13 Dec 2013 6:01 PM CET

Welcome to Week 6 of Algorithms, Part II. We have released the course materials for the week: two lectures, two sets of exercises, a programming assignment, and two sets of job interview questions.

• Exercises: due two weeks after they are released.
  

• Programming assignment: due two weeks after it is released.
  

• Job interview questions: ungraded and for your own enrichment.
  

We complete our study of string processing by considering a number of ingenious algorithms that take full advantage of several of the fundamental methods covered earlier in the course. In the first lecture, we consider regular expression pattern matching, where the goal is to find strings from a specified set in a given text. In the second lecture, we consider classic methods for data compression.

Lecture: Regular Expressions. A regular expression is a method for specifying a set of strings. Our topic for this lecture is the famous grep algorithm that determines whether a given text contains any substring from the set. We examine an efficient implementation that makes use of our digraph reachability implementation from Week 1.

Lecture: Data Compression. We study and implement several classic data compression schemes, including run-length coding, Huffman compression, and LZW compression. We develop efficient implementations from first principles using a Java library for manipulating binary data that we developed for this purpose, based on priority queue and symbol table implementations from earlier lectures.

Exercises. Drill exercises on the lecture material.

Job Interview Questions. Algorithmic interview questions based on the lecture material.

Programming Assignment: Burrows-Wheeler algorithm. Implement the Burrows-Wheeler data compression algorithm.

Suggested readings. Section 5.4 and 5.5 in Algorithms, 4th edition.

Fri 6 Dec 2013 6:01 PM CET

Welcome to Week 5 of Algorithms, Part II. We have released the course materials for the week: two lectures, two sets of exercises, a programming assignment, and two sets of job interview questions.

• Exercises: due two weeks after they are released.
  

• Programming assignment: due two weeks after it is released.
  

• Job interview questions: ungraded and for your own enrichment.
  

This week, we consider two different search problems involving strings. In the first lecture, we build upon the ideas we considered for string sorts to develop string search methods that are even faster than hashing and even more flexible than binary search trees. In the second lecture we consider classic algorithms for the substring search problem, where the goal is to find a given substring in a large text.

Lecture: Tries. In this lecture we consider specialized algorithms for symbol tables with string keys. Our goal is a data structure that is as fast as hashing and even more flexible than binary search trees. We begin with multiway tries; next we consider ternary search tries. Finally, we consider character-based operations, including prefix match and longest prefix, and related applications.

Lecture: Substring Search. In this lecture we consider algorithms for searching for a substring in a piece of text. We begin with a brute-force algorithm, whose running time is quadratic in the worst case. Next, we consider the ingenious Knuth-Morris-Pratt algorithm whose running time is guaranteed to be linear in the worst case. Then, we introduce the Boyer-Moore algorithm, whose running time is sublinear on typical inputs. Finally, we consider the Rabin-Karp fingerprint algorithm, which uses hashing in a clever way to solve the substring search and related problems.

Exercises. Drill exercises on the lecture material.

Programming Assignment: Boggle. Write a program to play the word-game Boggle.

Job Interview Questions. Algorithmic interview questions based on the lecture material.

Suggested readings. Section 5.2 and 5.3 in Algorithms, 4th edition.

Fri 29 Nov 2013 6:01 PM CET

Welcome to Week 4 of Algorithms, Part II. No new material will be released this week. You can use this week to get caught up or take a break.

Please remember that by taking this course, you are bound by the honor code not to post solutions (or partial solutions) to the programming assignments. This includes discussion forum posts, web pages, and public repositories (such as Github). If you are doing so, please take a few minutes now to remove any material that could compromise the integrity of the programming assignments for current or future students. Also, if you discover solutions or partial solutions that are public, please feel free to politely ask the individual to remove the code (since they may be unaware of the course policy).

Also, please do not post the course materials (videos, lecture slides, etc.) to other websites or YouTube. You are most welcome to download the videos and lecture slides for personal use.

Finally, we note that all of the code in stdlib.jar and algs4.jar has been released under the GPLv3, so feel free to use, modify, and improve these libraries accordingly.

Fri 22 Nov 2013 6:01 PM CET

Welcome to Week 3 of Algorithms, Part II. We have released the course materials for the week: two lectures, two sets of exercises, a programming assignment, and two sets of job interview questions.

• Exercises: due two weeks after they are released.
  

• Programming assignment: due two weeks after it is released.
  

• Job interview questions: ungraded and for your own enrichment.
  

This week we finish our study of graph algorithms by considering the classic maxflow and mincut problems, two problem-solving models that are useful in a broad variety of applications. Then we pivot to begin our study of string-processing algorithms, starting with substantially improved algorithms for sorting in the case when keys are strings.

Lecture: Maximum Flow and Minimum Cut. In this lecture we introduce the maximum flow and minimum cut problems. We begin with the Ford-Fulkerson algorithm. To analyze its correctness, we establish the maxflow-mincut theorem. Next, we consider an efficient implementation of the Ford-Fulkerson algorithm, using the shortest augmenting path rule. Finally, we consider applications, including bipartite matching and baseball elimination.

Lecture: Radix Sorts. In this lecture we consider specialized sorting algorithms for strings and related objects. We begin with a subroutine to sort integers in a small range. We then consider two classic radix sorting algorithms—LSD and MSD radix sorts. Next, we consider an especially efficient variant, which is a hybrid of MSD radix sort and quicksort known as 3-way radix quicksort. We conclude with suffix sorting and related applications.

Exercises. Drill exercises on the lecture material.

Programming Assignment: Baseball Elimination. Given the standings in a sports division at some point during the season, determine which teams have been mathematically eliminated from winning their division.

Job Interview Questions. Algorithmic interview questions based on the lecture material.

Suggested readings. Section 6.4 (pp. 886-902) and 5.1 in Algorithms, 4th edition.

Fri 15 Nov 2013 6:01 PM CET

Welcome to Week 2 of Algorithms, Part II. We have released the course materials for the week: two lectures, two sets of exercises, a programming assignment, and two sets of job interview questions.

• Exercises: due two weeks after they are released.
  

• Programming assignment: due two weeks days after it is released.
  

• Job interview questions: ungraded and for your own enrichment.
  

This week is devoted to two classic graph problems that have found extensive applications for decades. While the basic algorithms are easy to understand, efficient implementations in practical situations typically require deployment of data structures such as the priority queue and union-find structures that we considered in Part I. We also consider the fact that simple variations can lead to deep and difficult computational problems.

Lecture: Minimum Spanning Trees. In this lecture we study the minimum spanning tree problem. We begin by considering a generic greedy algorithm for the problem. Next, we consider and implement two classic algorithm for the problem—Kruskal's algorithm and Prim's algorithm. We conclude with some applications and open problems.

Lecture: Shortest Paths. In this lecture we study shortest-paths problems. We begin by analyzing some basic properties of shortest paths and a generic algorithm for the problem. We introduce and analyze Dijkstra's algorithm for shortest-paths problems with nonnegative weights. Next, we consider an even faster algorithm for DAGs, which works even if the weights are negative. We conclude with the Bellman-Ford-Moore algorithm for edge-weighted digraphs with no negative cycles. We also consider applications ranging from content-aware fill to arbitrage.

Exercises. Drill exercises on the lecture material.

Job Interview Questions. Algorithmic interview questions based on the lecture material.

Programming Assignment: Content-Aware Resizing. Implement a seam-carving algorithm for content-aware resizing.

Suggested readings. Section 4.3 and 4.4 in Algorithms, 4th edition.

Fri 8 Nov 2013 6:01 PM CET

Welcome to Week 1 of Algorithms, Part II. We have released the course materials for the week: two lectures, two sets of exercises, a programming assignment, and two sets of job interview questions.

• Exercises: due two weeks after they are released.
  

• Programming assignment: due two weeks after it is released.
  

• Job interview questions: ungraded and for your own enrichment.
  

We begin our exploration of advanced algorithms by looking at data structures for graphs, which are essential models for a broad variety of real-world problems. A number of classic algorithms are easy to implement, but worthy of careful study both because convincing oneself that they operate as intended can be a challenge and because their performance is strongly dependent on proper use of the basic data structures that we covered in Algorithms Part I.

Lecture: Undirected Graphs. We define an undirected graph API and consider the adjacency-matrix and adjacency-lists representations. We introduce two classic algorithms for searching a graph—depth-first search and breadth-first search. We also consider the problem of computing connected components and conclude with related problems and applications.

Lecture: Directed Graphs. In this lecture we study directed graphs. We begin with depth-first search and breadth-first search in digraphs and describe applications ranging from garbage collection to web crawling. Next, we introduce a depth-first search based algorithm for computing the topological order of an acyclic digraph. Finally, we implement the Kosaraju-Sharir algorithm for computing the strong components of a digraph.

Exercises. Drill exercises on the lecture material.

Programming Assignment: WordNet. Determine the semantic relatedness of two nouns using the WordNet lexicon.

Job Interview Questions. Algorithmic interview questions based on the lecture material.

Suggested readings. Section 4.1 and 4.2 in Algorithms, 4th edition.

Fri 1 Nov 2013 5:01 PM CET

Thanks for enrolling in our course Algorithms, Part II. We're excited to let you know that the course will get started on November 1, 2013 and will run for seven weeks. You can review the syllabus and schedule to see what's coming. We'll also send weekly announcements summarizing what's to happen each week.

The course is the second part of a two-part course that is based on a variety of material that we have prepared over many years:

• The lecture videos, lecture slides, exercises, programming assignments, and "job interview" questions will be available at the Coursera website.


• Whether or not you have completed Algorithms, Part I, the lecture videos from that part of the course will be left open for your reference (provided that you are already enrolled), as several of the algorithms in Part II extend or depend upon the basic algorithms and data structures covered in Part I.


• Our textbook Algorithms, 4th edition is the basic reference for the material we will be covering. Although the lectures are designed to be self-contained, we will assign optional readings for students who wish more extensive coverage of the material. You can purchase the textbook in either hardcover or electronic format from amazon.com.


• Our booksite, which is open to everyone and contains a wealth of supplementary information, including synopses of the textbook and Java code that you will be using throughout the course.

To maximize your chance of success in this course, you should get in the mindset of being an active participant who writes and debugs code; solves problems; studies the available resources; and engages in the discussion forums, meetups, and Google+ hangouts, as opposed to a passive participant who just watches the lecture videos. You'll get a good feeling for the spirit and pace of the course when you work on the first programming assignment, which will introduce you to our Java programming model in the context of an application to computational linguistics. If you haven't programmed in Java recently, you might wish to prepare for the course by writing some code, perhaps with the help of our Introduction to Programming in Java textbook and associated booksite.

To keep you informed, we'll email weekly announcements summarizing what's to happen each week.

Fri 25 Oct 2013 6:01 PM CEST

All video recordings, assessments and other materials made available in connection with this course are subject to copyright protection and may be used only for private study by persons who are enrolled in this course. Any other use of these materials must be with the express, written permission of Robert Sedgewick and Kevin Wayne.

No certificates, statements of accomplishment, or other credentials will be awarded in connection with this course.

Fri 1 Jun 2012 7:48 PM CEST