This course focuses on the fundamentals of computer algorithms, emphasizing methods useful in practice. We look into the algorithm analysis as a way to understand behavior of computer programs as a function of its input size. Using the big-O notation, we classify algorithms by their efficiency. We look into basic algorithm strategies and approaches to problem solving. Some of these approaches include the divide and conquer method, dynamic programming, and greedy programming paradigms. Sorting and searching algorithms are discussed in detail as they form part of a solution to a large number of problems solved using computers. We also provide an introduction to the graph theory and graph algorithms as they are also used in many computer-based applications today. We conclude the course with a look into a special class of problems called the NP-complete problems.

## Topic outline

- Course Introduction
- Unit 1: Introduction to Algorithms
This unit introduces what algorithms are and discusses their importance with the role that algorithms play compared to other technologies used in computers. We look into description of algorithms using pseudo-code and we use pseudo-code for algorithmic analysis. We will go through an introduction of algorithms using examples of sorting algorithms while discussing the importance of algorithm analysis in that context.

**Completing this unit should take you approximately 5 hours.** - 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.

- Unit 2: Introduction to Analysis of Algorithms
In this unit, we explore how we can express an algorithm's efficiency as a function of its input size. The order of growth of running time of an algorithm gives a simple characterization of algorithm's efficiency and allows us to relate performance of alternative algorithms. Asymptotic analysis is based on the idea that as the problem size grows, the complexity will eventually settle down to a simple proportionality to some known function. This idea is incorporated in the "Big Oh", "Big Omega", and "Big Theta" notations for asymptotic performance. These notations are useful for expressing the complexity of an algorithm without getting lost in unnecessary detail.

**Completing this unit should take you approximately 9 hours.** - 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.

- Unit 3: Divide and Conquer Method
In this unit, we will examine a popular technique called divide-and-conquer that is used in solving computer science problems. This technique solves the problem by breaking up the problem into smaller problems of same type and then recursively solving these smaller problems and combining their answers. We will also look into analysis of these algorithms through the use of recursion techniques.

**Completing this unit should take you approximately 10 hours.** - 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.

- Unit 4: Sorting Algorithms
This unit introduces algorithms that sort real numbers. Algorithms often use sorting as a key subroutine. There is a wide variety of sorting algorithms, and they use a rich set of techniques. These algorithms have different runtime complexities and work better in certain conditions. Some of algorithms that we will study include Quick Sort, Insertion Sort, Bubble Sort, and Merge Sort.

**Completing this unit should take you approximately 7 hours.** - 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.

- Unit 5: Dynamic Programming
In this unit, we will study another popular computer science algorithmic paradigm called the dynamic programming. Dynamic programming, like the divide-and-conquer method, solves problem by combining solutions to sub-problems. Dynamic programming typically applies to optimization problems in which a set of choices must be made in order to arrive at an optimal solution. It is effective when a given sub-problem may arise from more than one partial set of choices. We will look into problems, such as the longest common subsequence and the knapsack problem, to explain the key ideas behind dynamic programming.

**Completing this unit should take you approximately 7 hours.** - 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.

- Unit 6: Graph Theory and Graph Algorithms
In this unit, you will learn about graph theory and graph-based algorithms. Graphs are a pervasive data structure in computer science and algorithms working with them are fundamental to the subject. We will review basic concepts of graph and associated terminology. We will also see how we can represent graphs in computer algorithms and use these representations to solve some common problems, such as finding the shortest paths between any two places. You will also get an introduction to trees and a minimum weight spanning tree algorithm.

**Completing this unit should take you approximately 10 hours.** - 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.

- Unit 7: Greedy Algorithms
In this unit, we will look into a common computer science algorithm technique called the greedy algorithms. Like the dynamic programming paradigm, greedy algorithms typically apply to optimization problems in which a set of choices must be made in order to arrive at an optimal solution. The idea of greedy algorithm is to make each choice in a locally optimal manner. We will explore some common greedy algorithms in use today as a way of explaining the topic in this unit.

**Completing this unit should take you approximately 7 hours.** - 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.

- Unit 8: NP-Completeness
In this last unit, we will study a special class of problems called the NP-complete problems. Many interesting computational problems are NP-complete, but there are no polynomial-time algorithms known for solving any of them. The unit presents techniques for determining when a problem is NP-complete.

**Completing this unit should take you approximately 11 hours.** - 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.