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 bigO 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 computerbased applications today. We conclude the course with a look into a special class of problems called the NPcomplete problems.
Course Information showclose
Course Designer: Dr. Bhanu Kapoor
Primary Resources: Primary sources for this course include videobased 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 pseudocode 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 divideandconquer 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, graphbased algorithms, and their analysis;
 describe treebased algorithms and their analysis; and
 explain the classification of difficult computer science problems as belonging to P, NP, and NPhard classes.
Course Requirements showclose
√ Have access to a computer.
√ Have continuous broadband internet access.
√ Have the ability/permission to install plugins 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 highlevel 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

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 pseudocode and we use pseudocode 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 BYNCSA 3.0. Original version can be seen here.
 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.
 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.
 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 AttributionShareAlike License 3.0 (HTML). You can find the original Wikibooks version of this article here (HTML).  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.
 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 BYNCSA 3.0. Original version can be seen here.
 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.
 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: Read the Prologue of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 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 AttributionShareAlike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).  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.
 Reading: Wikipedia: “Master Theorem”

Unit 3: Divide and Conquer Method
In this unit, we will examine a popular technique called divideandconquer 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: Divideandconquer Algorithms”
Link: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 2: Divideandconquer Algorithms” (PDF)
Instructions: Read Chapter 2 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms (36 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 2: Divideandconquer 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 BYNCSA 3.0. Original version can be seen here.
 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 AttributionShareAlike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).  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 divideandconquer 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 preparation
 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.
 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 BYNCSA 3.0. Original version can be seen here.
 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 BYNCSA 3.0. Original version can be seen here.
 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 AttributionShareAlike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).  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 mergesort 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.
 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 divideandconquer method, solves problem by combining solutions to subproblems. 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 subproblem 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: Read Chapter 6 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms (31 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 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 BYNCSA 3.0. Original version can be seen here.
 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.
 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 AttributionShareAlike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).  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 dynamicprogramming 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.
 Reading: Wikipedia: “Dynamic Programming”

Unit 6: Graph Theory and Graph Algorithms
In this unit, you will learn about graph theory and graphbased 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.
 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: Read pages 104122 of Chapter 4 from S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms (18 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 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.
 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 BYNCSA 3.0. Original version can be seen here.
 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, Breadthfirst Search”
Link: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadthfirst 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 BYNCSA 3.0. Original version can be seen here.  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 breadthfirst search implementation and one on depthfirst 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.
 Lecture: YouTube: MIT Course on Introduction to Algorithms: Dr. Charles E. Leiserson’s “Lec 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadthfirst 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: Read Chapter 5 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms (29 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 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.
 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.
 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.  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.
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 12: Greedy Algorithms – III”

Unit 8: NPCompleteness
In this last unit, we will study a special class of problems called the NPcomplete problems. Many interesting computational problems are NPcomplete, but there are no polynomialtime algorithms known for solving any of them. The unit presents techniques for determining when a problem is NPcomplete.
Unit 8 Time Advisory show close
Unit 8 Learning Outcomes show close

8.1 Introduction to NPCompleteness
 Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 8: NPComplete Problems”
Link: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 8: NPComplete Problems” (PDF)
Instructions: Read Chapter 8 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s book, Algorithms (36 pages).
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms: “Chapter 8: NPComplete Problems”

8.2 NPCompleteness – Part I
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 26: NPCompleteness – Part I”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 26: NPCompleteness – Part I” (YouTube)
Instructions: Please click on the link above, and view the whole video (about 58 minutes) to gain an understanding of NPComplete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 26: NPCompleteness – Part I”

8.3 NPCompleteness – Part II
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 27: NPCompleteness – Part II”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 27: NPCompleteness – 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 NPComplete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 27: NPCompleteness – Part II”

8.4 NPCompleteness – Part III
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 28: NPCompleteness – Part III”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 28: NPCompleteness – Part III” (YouTube)
Instructions: Please click on the link above, and view the whole video (about 57 minutes) to gain an understanding of NPComplete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 28: NPCompleteness – Part III”

8.5 NPCompleteness – Part IV
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 29: NPCompleteness – Part IV”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 29: NPCompleteness – 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 NPComplete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 29: NPCompleteness – Part IV”

8.6 NPCompleteness – Part V
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 30: NPCompleteness – Part V”
Link: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 30: NPCompleteness – Part V” (YouTube)
Instructions: Please click on the link above, and view the entire video (about 41 minutes) to gain an understanding of NPComplete problems in the context of computer algorithms.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.  Assessment: The Saylor Foundation’s “NPCompleteness”
Link: The Saylor Foundation’s “NPCompleteness” (PDF)
Instructions: Please complete all questions in this assessment. There are two questions that are both related to proving NPCompleteness 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.
 Lecture: YouTube: IIT Bombay Course on Design and Analysis of Algorithms: Dr. Sunder Viswanathan’s “Lecture 30: NPCompleteness – 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.
 Final Exam: The Saylor Foundation's CS303 Final Exam