Topic | Name | Description |
---|---|---|
Course Introduction | ||
1.1: Introduction to Algorithms | Watch this video to learn the basics of the algorithm. You can skip the first 17 minutes of the video as they talk about MIT class related logistics for the course. |
|
1.2: Introduction to Framework for Algorithm Analysis | Watch this video to learn about the basics of the algorithm analysis and associated framework. |
|
1.3: The Importance of Algorithms | Read this article for an overview of importance of algorithms as well as a listing of some of the key algorithm areas. |
|
1.4: Control Instructions | Read this page to get an introduction to algorithms. |
|
Complete all questions in this assignment. There are three questions on finding the complexity of the algorithm using the pseudo code and finding the number of instructions executed to solve the problem. Each instruction is associated with some constant cost for execution. You can check your answers against the Answer Key. |
||
2.1: Introduction to Algorithms | Watch this video to learn about the basics of the algorithm. |
|
2.2: Asymptotic Analysis | Watch this video to learn about the ideas behind the use of asymptotic analysis in algorithms. |
|
2.3: Introduction to Analysis of Algorithms | Read the Prologue of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms. |
|
2.4: Master Theorem | Read this article to learn about the use of Master Theorem in analyzing recursive problems. |
|
Complete all questions in this assignment. There are six questions listed in two parts. The first part requires solving the problems using the Master Theorem discussed in the lectures. The second part requires solving for complexity of the algorithms using the first principles. You can check your answers against the Answer Key. |
||
3.1: Introduction to Divide and Conquer Algorithms | Read Chapter 2 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms. |
|
3.2: Recurrences in Algorithms | Watch this lecture to learn about the basics of the algorithm. |
|
3.3: Recursion | Read this article to learn about the mathematical concepts behind the idea of recursion. |
|
Complete all questions in this assignment. There are two questions on the divide-and-conquer strategy. The first one involves a search strategy, whereas the second one involves a multiplication strategy. You can check your answers against the Answer Key. |
||
4.1: Introduction to Sorting Algorithms | Watch this video to learn about sorting algorithms. |
|
Watch this video to learn about sorting algorithms. |
||
4.2: Sorting Algorithms - Part I | Watch this video to learn about the basics of sorting algorithms. |
|
4.3: Sorting Algorithms - Part II | Watch this video to learn about various types of sorting algorithms. |
|
4.4: Popular Sorting Algorithms | Read this article to learn about the popular sorting algorithms in use today. |
|
Please complete all questions in this assignment. There are two questions on the sorting algorithms. The first one involves the merge-sort algorithm and requires you to work through the merging part of the algorithm. The second one then asks you to implement the merging work that you just completed in the first problem. You can check your answers against the Answer Key. |
||
5.1: Introduction to Dynamic Programming | Read Chapter 6 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms. |
|
5.2: Dynamic Programming | Watch this video to learn about dynamic programming concepts. |
|
5.3: The Knapsack Problem | Watch this video series to learn about how the knapsack problem is solved using dynamic programming techniques. |
|
5.4: Dynamic Programming Examples | Read this article to learn about the different types of problems to which dynamic programming techniques are applied. |
|
Complete all questions in this activity. There is one question on the dynamic-programming paradigm that requires two implementations. The first one involves the use of the regular approach to matrix multiplication, and the second one requires the dynamic programming approach. You have to compare the runtimes for the two approaches. You can check your answers against the Answer Key. |
||
6.1: Introduction to Graph Theory | Read this chapter for an introduction to graph theory. |
|
6.2: Paths in Graphs | Read Chapter 4 from S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms. |
|
6.3: Graph Data Structures | Watch this video to learn about data structures used in graph algorithms. |
|
6.4: Graph Theory Algorithms - Part I | Watch this video to learn about graph theory concepts, greedy algorithms, and minimum spanning trees. |
|
6.5: Graph Theory Algorithms - Part II | Watch this video to learn about shortest path problems. |
|
Complete all questions in this assignment. There is one question on the breadth-first search implementation and one on depth-first search implementation. You can check your answers against the Answer Key. |
||
7.1: Introduction to Greedy Algorithms | Read Chapter 5 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms. |
|
7.2: Greedy Algorithms - Part I | Watch this video to learn about greedy algorithms. |
|
7.3: Greedy Algorithms - Part II | Watch this video to learn about greedy algorithms. |
|
7.4: Greedy Algorithms - Part III | Watch this video to learn about greedy algorithms. |
|
Read this article to learn about the mathematical concept behind the idea of recursion. |
||
Complete all questions in this activity. There is one question on the minimum spanning tree problem requiring two implementations using the Kruskal's algorithm and the Prim's algorithm. You can check your answers against the Answer Key. |
||
8.1: Introduction to NP-Completeness | Read Chapter 8 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms. |
|
8.2: NP-Completeness - Part I | Watch this video to learn about NP-Complete problems in the context of computer algorithms. |
|
8.3: NP-Completeness - Part II | Watch this video to learn about NP-Complete problems in the context of computer algorithms. |
|
8.4: NP-Completeness - Part III | Watch this video to learn about NP-Complete problems in the context of computer algorithms. |
|
8.5: NP-Completeness - Part IV | Watch this video to learn about NP-Complete problems in the context of computer algorithms. |
|
8.6: NP-Completeness - Part V | Watch this video to learn about NP-Complete problems in the context of computer algorithms. |
|
Complete all questions in this assignment. There are two questions that are both related to proving NP-Completeness of a given problem. You can check your answers against the Answer Key. |