Questions? Consult the FAQs!
Course Question & Answer
 |
This course is currently being improved through our peer review process. |
Algorithms
Purpose of Course showclose
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.
Course Information showclose
Course Designer: Dr. Bhanu Kapoor
Primary Resources: Primary sources for this course include video-based lectures and online reading materials from books and other sources. Some of the key sources include:
- MIT: Dr. Charles E. Leiserson’s “Introduction to Algorithms”
- IIT Bombay: Dr. Abhiram Ranade’s “Introduction to Algorithms”
- University of California – Berkeley: Dr. Jonathan Shewchuk’s “Data Structures”
- University of California – Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms
- IIT Bombay: Dr. Sunder Viswanathan’s “Design and Analysis of Algorithms”
Time Commitment: The course will require approximately 100 work hours over a period of 15 weeks to complete. This includes time spent on lectures, readings, homework, and examinations to complete the requirements.
Tips/Suggestions: Please follow the directions in each unit of the Course Outline section to navigate through the course materials.
Learning Outcomes showclose
- Explain and identify the importance of algorithms in modern computing systems and their place as a technology in the computing industry.
- Indentify algorithms as a pseudo-code to solve some common problems.
- Describe asymptotic notations for bounding algorithm running times from above and below.
- Explain methods for solving recurrences useful in describing running times of recursive algorithms.
- Explain the use of Master Theorem in describing running times of recursive algorithms.
- Describe the divide-and-conquer recursive technique for solving a class of problems.
- Describe sorting algorithms and their runtime complexity analysis.
- Describe the dynamic programming technique for solving a class of problems.
- Describe greedy algorithms and their applications.
- Describe concepts in graph theory, graph-based algorithms, and their analysis.
- Describe tree-based algorithms and their analysis.
- Explain the classification of difficult computer science problems as belonging to P, NP, and NP-hard classes.
Course Requirements showclose
√ Have access to a computer.
√ Have continuous broadband internet access.
√ Have the ability/permission to install plug-ins or software (e.g. Adobe Reader or Flash).
√ Have the ability to download and save files and documents to a computer.
√ Have the ability to open Microsoft files and documents (.doc, .ppt, .xls, etc.).
√ Be competent in the English language.'
√ Have read the Saylor Student Handbook.
√ Be knowledgeable about basics of computer programming using a high-level language, such as C/C++ and/or have completed Introduction to Computer Science I (CS101), Introduction to Computer Science II course (CS102), Elementary Data Structure (CS 201), and Discrete Structures (CS 202) from “The Core Program” in the Computer Science discipline.
√ Be comfortable in writing, compiling, and executing your own programs.
√ Be knowledgeable about basics of discrete mathematics concepts.
Unit Outline show close
Expand All Resources Collapse All Resources
-
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.
Unit 1 Time Advisory show close
Unit 1 Learning Outcomes show close
-
1.1 Introduction to Algorithms
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 1: Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort”
Link: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 1: Administrivia; Introduction; Analysis of Algorithms, Insertion Sort; Mergesort” (YouTube)
Also available in:
Adobe Flash
iTunes
Mp4
Instructions: Please click the link above, and view the video fully to gain an understanding of 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.
Terms of use: Erik Demaine and Charles Leiserson 6.046J/18.410J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011). License: Creative Commons BY-NC-SA 3.0. Original version can be seen here.See a broken link? Please let us know!
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 1: Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort”
-
1.2 Introduction to Framework for Algorithm Analysis
- Lecture: IIT Bombay Course on Introduction to Algorithms: Dr. Abhiram Ranade’s “Lec 2: Framework for Algorithm Analysis”
Link: IIT Bombay Course on Introduction to Algorithms: Dr. Abhiram Ranade’s “Lecture 2: Framework for Algorithm Analysis” (YouTube)
Instructions: Please click the link above, and view the video in its entirety (56:22 minutes) to gain an understanding of the basics of the algorithm analysis and associated framework.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: IIT Bombay Course on Introduction to Algorithms: Dr. Abhiram Ranade’s “Lec 2: Framework for Algorithm Analysis”
-
1.3 The Importance of Algorithms
- Reading: Topcoder: Ibackstrom’s “Importance of Algorithms”
Link: Topcoder: Ibackstrom’s “Importance of Algorithms” (HTML)
Instructions: Please read the “Importance of Algorithms” webpage in its entirety for an overview of importance of algorithms as well as a listing of some of the key algorithm areas.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: Topcoder: Ibackstrom’s “Importance of Algorithms”
-
1.4 Control Instructions
- Reading: Wikibooks: “Algorithms/Introduction”
Link: Wikibooks: “Algorithms/Introduction” (PDF)
Instructions: Please read all of the sections on this webpage to get an introduction to algorithms.
Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikibooks version of this article here (HTML).See a broken link? Please let us know!
- Assessment: The Saylor Foundation’s “Introduction to Algorithms”
Link: The Saylor Foundation’s “Introduction to Algorithms” (PDF)
Instructions: Please complete all questions in this assessment. 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 with the Saylor Foundation’s “Answer Key” (PDF).
This assessment should take you approximately 2 hours to complete, including review for preparation.See a broken link? Please let us know!
- Reading: Wikibooks: “Algorithms/Introduction”
-
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.
Unit 2 Time Advisory show close
Unit 2 Learning Outcomes show close
-
2.1 Introduction to Algorithms
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Erik Demaine’s “Lec 2: Introduction to Algorithms”
Link: YouTube: MIT Course on Introduction to Algorithms: Dr. Erik Demaine’s “Lec 2: Introduction to Algorithms” (YouTube)
Instructions: Please click the link above, and view the video in its entirety (about 1 hour and 10 minutes) to gain an understanding of the basics of the algorithm. Please note that this lecture also covers the topic outlined in subunit 2.4 of this unit.
Terms of use: Erik Demaine and Charles Leiserson 6.046J/18.410J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011). License: Creative Commons BY-NC-SA 3.0. Original version can be seen here.See a broken link? Please let us know!
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Erik Demaine’s “Lec 2: Introduction to Algorithms”
-
2.2 Asymptotic Analysis
- Lecture: YouTube: University of California, Berkeley’s Course on Data Structures: Dr. Jonathan Shewchuk’s “Asymptotic Analysis”
Link: YouTube: University of California, Berkeley’s Course on Data Structures: Dr. Jonathan Shewchuk’s “Asymptotic Analysis” (YouTube)
Instructions: Please click the link above, and view the video in its entirety (about 49 minutes) to gain an understanding of the ideas behind the use of asymptotic analysis in algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: University of California, Berkeley’s Course on Data Structures: Dr. Jonathan Shewchuk’s “Asymptotic Analysis”
-
2.3 Introduction to Analysis of Algorithms
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 0: Prologue”
Link: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 0: Prologue” (PDF)
Instructions: Please click on the hyperlink titled “Prologue” to download the PDF filed of Chapter 0 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms. Please read the entire text (9 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 0: Prologue”
-
2.4 Master Theorem
- Reading: Wikipedia: “Master Theorem”
Link: Wikipedia: “Master Theorem” (PDF)
Instructions: Please read the article titled “Master Theorem” to get an understanding of the use of Master Theorem in analyzing recursive problems.
Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).See a broken link? Please let us know!
- Assessment: The Saylor Foundation’s “Introduction to Analysis of Algorithms”
Link: The Saylor Foundation’s “Introduction to Analysis of Algorithms” (PDF)
Instructions: Please complete all questions in this assessment. 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 with The Saylor Foundation’s “Answer Key” (PDF).
This assessment should take you approximately 3 hours to complete, including review for preparation.See a broken link? Please let us know!
- Reading: Wikipedia: “Master Theorem”
-
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.
Unit 3 Time Advisory show close
Unit 3 Learning Outcomes show close
-
3.1 Introduction to Divide and Conquer Algorithms
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 2: Divide-and-conquer Algorithms”
Link: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 2: Divide-and-conquer Algorithms” (PDF)
Instructions: Please click on the hyperlink titled “Divide-and-conquer algorithms” to download the PDF file for Chapter 2 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms. Please read the entire text (36 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 2: Divide-and-conquer Algorithms”
-
3.2 Recurrences in Algorithms
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Erik Demaine’s “Lec 3: Introduction to Algorithms”
Link: YouTube: MIT Course on Introduction to Algorithms: Dr. Erik Demaine’s “Lec 3: Introduction to Algorithms” (YouTube)
Instructions: Please click the link above, and view the video in its entirety (approximately 1 hour and 8 minutes) to gain an understanding of the basics of the algorithm.
Terms of use: Erik Demaine and Charles Leiserson 6.046J/18.410J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011). License: Creative Commons BY-NC-SA 3.0. Original version can be seen here.See a broken link? Please let us know!
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Erik Demaine’s “Lec 3: Introduction to Algorithms”
-
3.3 Recursion
- Reading: Wikipedia: “Recursion”
Link: Wikipedia: “Recursion” (PDF)
Instructions: Please read the article titled “Recursion” to get an understanding of the mathematical concept behind the idea of recursion.
Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).See a broken link? Please let us know!
- Assessment: The Saylor Foundation’s “Divide and Conquer”
Link: The Saylor Foundation’s “Divide and Conquer” (PDF)
Instructions: Please complete all questions in this assessment. 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 with the Saylor Foundation’s “Answer Key” (PDF).
This assessment should take you approximately 1.5 hours to complete, including reviews for preparationSee a broken link? Please let us know!
- Reading: Wikipedia: “Recursion”
-
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.
Unit 4 Time Advisory show close
Unit 4 Learning Outcomes show close
-
4.1 Introduction to Sorting Algorithms
- Lecture: YouTube: Knight School (2009)’s “Lec 3: Algorithmic Thinking” and Google CEO’s interview of 2008 Presidential Candidate Barack Obama in “Barack Obama – Computer Science Question”
Links: YouTube: Knight School (2009)’s “Lec 3: Algorithmic Thinking” and Google CEO’s interview of 2008 Presidential Candidate Barack Obama in “Barack Obama – Computer Science Question” (YouTube)
Instructions: Please click on the links above, and view each video (about 10 minutes total) fully to gain an introduction to sorting algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: Knight School (2009)’s “Lec 3: Algorithmic Thinking” and Google CEO’s interview of 2008 Presidential Candidate Barack Obama in “Barack Obama – Computer Science Question”
-
4.2 Sorting Algorithms – Part I
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 4: Quicksort, Randomized Algorithms”
Link: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 4: Quicksort, Randomized Algorithms” (YouTube)
Also available in:
Adobe Flash
iTunes
Mp4
Instructions: Please click on the link above, and view the video in its entirety (about 1 hour and 20 minutes) to gain an understanding of the basics of sorting algorithms.
Terms of use: Erik Demaine and Charles Leiserson 6.046J/18.410J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011). License: Creative Commons BY-NC-SA 3.0. Original version can be seen here.See a broken link? Please let us know!
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 4: Quicksort, Randomized Algorithms”
-
4.3 Sorting Algorithms – Part II
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Erik Demaine’s “Lec 5: Introduction to Algorithms”
Link: YouTube: MIT Course on Introduction to Algorithms: Dr. Erik Demaine’s “Lec 5: Introduction to Algorithms” (YouTube)
Instructions: Please click on the link above, and view the video in its entirety (about 1 hour and 17 minutes) to gain an understanding of various types of sorting algorithms.
Terms of use: Erik Demaine and Charles Leiserson 6.046J/18.410J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011). License: Creative Commons BY-NC-SA 3.0. Original version can be seen here.See a broken link? Please let us know!
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Erik Demaine’s “Lec 5: Introduction to Algorithms”
-
4.4 Popular Sorting Algorithms
- Reading: Wikipedia: “Sorting Algorithms”
Link: Wikipedia: “Sorting Algorithms” (PDF)
Instructions: Please read the entire article titled “Sorting Algorithms” to get an overview of all popular sorting algorithms in use today.
Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).See a broken link? Please let us know!
- Assessment: The Saylor Foundation’s “Sorting”
Link: The Saylor Foundation’s “Sorting” (PDF)
Instructions: Please complete all questions in this assessment. 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 with the Saylor Foundation’s “Answer Key” (PDF).
This assessment should take you approximately 3 hours to complete, including reviews for preparation.See a broken link? Please let us know!
- Reading: Wikipedia: “Sorting Algorithms”
-
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.
Unit 5 Time Advisory show close
Unit 5 Learning Outcomes show close
-
5.1 Introduction to Dynamic Programming
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 6: Dynamic Programming”
Link: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 6: Dynamic Programming” (PDF)
Instructions: Please click on the hyperlink titled “Dynamic Programming” to open the PDF file for Chapter 6 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms. Please read this entire document (31 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 6: Dynamic Programming”
-
5.2 Dynamic Programming – Part I
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 15: Dynamic Programming, Longest Common Subsequence”
Link: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 15: Dynamic Programming, Longest Common Subsequence” (YouTube)
Also available in:
Adobe Flash
iTunes
Mp4
Instructions: Please click on the link above, and view the video in its entirety (1 hour and 11 minutes) to gain an understanding of dynamic programming concepts.
Terms of use: Erik Demaine and Charles Leiserson 6.046J/18.410J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011). License: Creative Commons BY-NC-SA 3.0. Original version can be seen here.See a broken link? Please let us know!
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 15: Dynamic Programming, Longest Common Subsequence”
-
5.3 Knapsack Problem
- Lecture: YouTube: Julimbob’s “Dynamic Programming - Knapsack Problem Part 1” “Dynamic Programming - Knapsack Problem Part 2” “Dynamic Programming - Knapsack Problem Part 3”
Links: YouTube: Julimbob’s “Dynamic Programming - Knapsack Problem Part 1” (YouTube) “Dynamic Programming - Knapsack Problem Part 2” (YouTube) “Dynamic Programming - Knapsack Problem Part 3” (YouTube)
Instructions: Please click on the links above, and view the brief videos (10 minute for Part 1 and about 5 minutes each for Parts 2 and 3) to gain an understanding of how the knapsack problem is solved using dynamic programming technique.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: Julimbob’s “Dynamic Programming - Knapsack Problem Part 1” “Dynamic Programming - Knapsack Problem Part 2” “Dynamic Programming - Knapsack Problem Part 3”
-
5.4 Dynamic Programming Examples
- Reading: Wikipedia: “Dynamic Programming”
Link: Wikipedia: “Dynamic Programming” (PDF)
Instructions: Please read the entire article titled “Dynamic Programming” to get an overview of different types of problems to which dynamic programming technique is applied.
Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).See a broken link? Please let us know!
- Assessment: The Saylor Foundation’s “Dynamic Programming”
Link: The Saylor Foundation’s “Dynamic Programming” (PDF)
Instructions: Please 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 with the Saylor Foundation’s “Guide to Responding.” (PDF)
This activity should take you approximately 10 hours to complete, including reviews for preparation.See a broken link? Please let us know!
- Reading: Wikipedia: “Dynamic Programming”
-
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.
Unit 6 Time Advisory show close
Unit 6 Learning Outcomes show close
-
6.1 Introduction to Graph Theory
- Reading: University of California, San Diego: Edward A. Bender and S. G. Williamson’s “Basic Concepts in Graph Theory”
Reading:University of California, San Diego: Edward A. Bender and S. G. Williamson’s “Basic Concepts in Graph Theory” (PDF)
Also Available in:
EPUB
Instructions: Please scroll down to the items listed under “Second Course.” Then, click on the “GT pdf” hyperlink below the title “Unit GT: Basic Concepts in Graph Theory” to open the PDF document. Please read the text in its entirety (67 pages).
Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.See a broken link? Please let us know!
- Reading: University of California, San Diego: Edward A. Bender and S. G. Williamson’s “Basic Concepts in Graph Theory”
-
6.2 Paths in Graphs
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 4: Paths in Graphs”
Link: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 4: Paths in Graphs” (PDF)
Instructions: Please click on the hyperlink titled “Paths in Graphs” to download the PDF of Chapter 4 from S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms. Please read the document up until page 122.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 4: Paths in Graphs”
-
6.3 Graph Data Structures
- Lecture: YouTube: PatrickJMT’s “Graph Theory – An Introduction”
Link: YouTube: PatrickJMT’s “Graph Theory – An Introduction” (YouTube)
Instructions: Please click on the link above, and view the video in its entirety (12:32 minutes) to gain an understanding of data structures used in graph algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: PatrickJMT’s “Graph Theory – An Introduction”
-
6.4 Graph Theory Algorithms – Part I
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 16: Greedy Algorithms, Minimum Spanning Trees”
Link: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 16: Greedy Algorithms, Minimum Spanning Trees” (YouTube)
Also available in:
Adobe Flash
iTunes
Mp4
Instructions: Please click on the link above, and view the entire video (approximately 1 hour 24 minutes) to gain an understanding of graph theory concepts, introduction to greedy algorithms, and minimum spanning trees.
Terms of use: Erik Demaine and Charles Leiserson 6.046J/18.410J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011). License: Creative Commons BY-NC-SA 3.0. Original version can be seen here.See a broken link? Please let us know!
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 16: Greedy Algorithms, Minimum Spanning Trees”
-
6.5 Graph Theory Algorithms – Part II
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search”
Link: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search” (YouTube)
Also available in:
Adobe Flash
iTunes
Mp4
Instructions: Please click on the link above, and view entire the video (approximately 1 hour 24 minutes) to gain an understanding of shortest path problems.
Terms of use: Erik Demaine and Charles Leiserson 6.046J/18.410J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 21, 2011). License: Creative Commons BY-NC-SA 3.0. Original version can be seen here.See a broken link? Please let us know!
- Assessment: The Saylor Foundation’s “Graph Theory and Graph Algorithms”
Link: The Saylor Foundation’s “Graph Theory and Graph Algorithms” (PDF)
Instructions: Please complete all questions in this activity. There is one question on the breadth-first search implementation and one on depth-first search implementation. You can check your answers with the Saylor Foundation’s “Guide to Responding.” (PDF)
This activity should take you approximately 8 hours to complete, including reviews for preparation.See a broken link? Please let us know!
- Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search”
-
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.
Unit 7 Time Advisory show close
Unit 7 Learning Outcomes show close
-
7.1 Introduction to Greedy Algorithms
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 5: Dynamic Programming”
Link: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 5: Greedy Algorithms” (PDF)
Instructions: Please click on the hyperlink titled “Greedy Algorithms” to open the PDF file for Chapter 5 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms. Please read the entire chapter (29 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 5: Dynamic Programming”
-
7.2 Greedy Algorithms – Part I
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 10: Greedy Algorithms – I”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 10: Greedy Algorithms – I” (YouTube)
Instructions: Please click on the link above, and view the video in its entirety (about 52 minutes) to gain an understanding of greedy algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 10: Greedy Algorithms – I”
-
7.3 Greedy Algorithms – Part II
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 11: Greedy Algorithms – II”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 11: Greedy Algorithms – II” (YouTube)
Instructions: Please click on the link above, and view the entire video (about 54 minutes) to gain an understanding of greedy algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 11: Greedy Algorithms – II”
-
7.4 Greedy Algorithms – Part III
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 12: Greedy Algorithms – III”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 12: Greedy Algorithms – III” (YouTube)
Instructions: Please click on the link above, and view the entire video (about 50 minutes) to gain an understanding of greedy algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Assessment: The Saylor Foundation’s “Greedy Algorithms”
Link: The Saylor Foundation’s “Greedy Algorithms” (PDF)
Instructions: Please 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 with the Saylor Foundation’s “Guide to Responding.” (PDF)
This activity should take you approximately 12 hours to complete, including reviews for preparation.See a broken link? Please let us know!
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 12: Greedy Algorithms – III”
-
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.
Unit 8 Time Advisory show close
Unit 8 Learning Outcomes show close
-
8.1 Introduction to NP-Completeness
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 8: NP-Complete Problems”
Link: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 8: NP-Complete Problems” (PDF)
Instructions: Please click on the hyperlink titled “NP-Complete Problems” to download the PDF file for Chapter 8 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms. Please read the entire chapter (36 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 8: NP-Complete Problems”
-
8.2 NP-Completeness – Part I
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 26: NP-Completeness – Part I”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 26: NP-Completeness – Part I” (YouTube)
Instructions: Please click on the link above, and view the whole video (about 58 minutes) to gain an understanding of NP-Complete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 26: NP-Completeness – Part I”
-
8.3 NP-Completeness – Part II
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 27: NP-Completeness – Part II”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 27: NP-Completeness – Part II” (YouTube)
Instructions: Please click on the link above, and view the video in its entirety (about 1 hour and 16 minutes) to gain an understanding of NP-Complete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 27: NP-Completeness – Part II”
-
8.4 NP-Completeness – Part III
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 28: NP-Completeness – Part III”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 28: NP-Completeness – Part III” (YouTube)
Instructions: Please click on the link above, and view the whole video (about 57 minutes) to gain an understanding of NP-Complete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 28: NP-Completeness – Part III”
-
8.5 NP-Completeness – Part IV
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 29: NP-Completeness – Part IV”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 29: NP-Completeness – Part IV” (YouTube)
Instructions: Please click on the link above, and view the video in its entirety (about 1 hour and 10 minutes) to gain an understanding of NP-Complete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 29: NP-Completeness – Part IV”
-
8.6 NP-Completeness – Part V
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 30: NP-Completeness – Part V”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 30: NP-Completeness – Part V” (YouTube)
Instructions: Please click on the link above, and view the entire video (about 41 minutes) to gain an understanding of NP-Complete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.See a broken link? Please let us know!
- Assessment: The Saylor Foundation’s “NP-Completeness”
Link: The Saylor Foundation’s “NP-Completeness” (PDF)
Instructions: Please complete all questions in this assessment. There are two questions that are both related to proving NP-Completeness of a given problem. You can check your answers with the Saylor Foundation’s “Guide to Responding.” (PDF)
This assessment should take you approximately 2 hours to complete, including reviews for preparation.See a broken link? Please let us know!
- Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 30: NP-Completeness – Part V”
-
Final Exam
- Final Exam: The Saylor Foundation's CS303 Final Exam
Link: The Saylor Foundation's CS303 Final Exam
Instructions: You must be logged into your Saylor Foundation School account in order to access this exam. If you do not yet have an account, you will be able to create one, free of charge, after clicking the link.See a broken link? Please let us know!
- Final Exam: The Saylor Foundation's CS303 Final Exam
