Preview this course in the non-credit experience today!
Start working toward program admission and requirements right away. Work you complete in the non-credit experience will transfer to the for-credit experience when you upgrade and pay tuition. See How It Works for details.

Cross-listed with DTSA 5503

• Course Type: Pathway | Breadth
• Specialization: Foundations of Data Structures and Algorithms
• Instructor: Dr. Sriram Sankaranarayanan, Professor of Computer Science
• Prior knowledge needed: You must understand all concepts covered in Dr. Sankaranarayanan's non-credit Algorithms for Searching, Sorting, and Indexing and Trees and Graphs: Basics courses to succeed in this course. We highly recommend successfully completing those two courses in the non-credit experience before starting this course; they are a great option to refresh your skills and ensure you're ready. Note that you cannot apply credit from either of these courses toward MS-CS graduation requirements.  Calculus, probability theory: distributions, expectations and moments. Some programming experience with Python.

Mathematical Background

Calculus, Introduction to Complex Algebra, Probability Theory: distributions and expectations.

Programming Background

The course involves solving programming assignments in Python. Beginner to intermediate programming experience with Python.

• Basic control structures in python: conditional branches, for loops and recursion.

• Functions: defining and calling functions, and recursion.

• Familiarity with scientific computation libraries, such as numpy.

• Our use of python will get more sophisticated as the course progresses to accommodate some learning of python.

## Course Description

This course is part three of a specialization on algorithms and data structures. It covers basic algorithm design techniques such as divide and conquer, dynamic programming, and greedy algorithms. It concludes with a brief introduction to intractability (NP-completeness) .

## Learning Outcomes

• Describe basic algorithm design techniques.
• Create divide and conquer, dynamic programming, and greedy algorithms.
• Understand intractable problems, P vs NP and the use of integer programming solvers to tackle some of these problems.

Assignment

Quizzes (Multiple Choice)

2% each (28% total)

Programming Assignments 1-3

15% each (45% total)

Programming Assignment 4

17%

Final Exam

10%

Total

100%

## Course Content

Duration: 12 hours

We will formally cover divide and conquer algorithms as a design scheme and look at some divide and conquer algorithms we have encountered in the past. We will learn some divide and conquer algorithms for Integer Multiplication (Karatsuba’s Algorithm), Matrix Multiplication (Strassen’s Algorithm), Fast Fourier Transforms (FFTs), and Finding Closest Pair of Points.

• We have seen examples of divide and conquer algorithms in previous courses, such as mergesort and quicksort algorithms.

• We will study more algorithms that fit this design paradigm.

• We will study Fast Fourier Transforms (FFT), a particularly useful divide and conquer algorithm that has wide applications in data analysis.

• FFT requires familiarity with complex numbers and their properties. A brief introduction is provided, along with pointers to further resources.

Assignments

We will have quizzes after most of the lessons in this module. These quizzes are multiple choice, and you will have unlimited attempts to solve them/get them right.

Programming Assignment

We will have a programming assignment that will help you approach the development of algorithms related to what we study in this module.

Duration: 9 hours

In this module, you will learn about dynamic programming as a design principle for algorithms. We will provide a step-by-step approach to formulating a problem as a dynamic program and solving these problems using memoization. We will cover dynamic programming for finding longest common subsequences, Knapsack problem and some interesting dynamic programming applications.

• We will introduce the concept of dynamic programming using a simple example of the "rod cutting problem".

• We will see that dynamic programming uses a step-by-step approach that involves making a recurrence, memoizing the recurrence and extracting the solution.

• We will study related problems such as the coin changing problem and the famous knapsack problem, which has numerous applications.

• Finally, we will study the longest common subsequence problem which is commonly used in computational biology applications such as gene sequence alignment.

Assignments

We will have quizzes after most of the lessons in this module. These quizzes are choose the correct answer style and you will have unlimited attempts to solve them/get them right.

Programming Assignment

We will have a programming assignment that will help you approach the development of algorithms related to what we study in this module.

Duration: 7 hours

In this module, we will learn about greedy algorithms. We will understand the basic design principles for greedy algorithms and learn about a few algorithms for greedy scheduling and Huffman codes. We will also learn some interesting cases when being greedy provides a guaranteed approximation to the actual solution.

These are algorithms that are based on making "fast and local" decisions and compare them against a carefully considered but expensive strategy such as dynamic programming studied in the previous module.

• We compare a greedy solution to the coin changing problem against the dynamic programming solution provided in the previous module.

• We study cases where greedy algorithms turn out to be optimal: interval scheduling to maximize the number of activities and the problem of designing prefix codes for compressing text files.

Assignments

We will have quizzes after most of the lessons in this module. These quizzes are 'select the correct answer' style and you will have unlimited attempts to solve them/get them right.

Programming Assignment

We will have a programming assignment that will help you approach the development of algorithms related to what we study in this module.

Duration: 11 hours

Module 4 will introduce intractability and serve as an introduction to the field of NP completeness.

• We will look at ways to describe problems and algorithms using some ideas from theory of computation.

• We will classify problems that can be solved in polynomial time as opposed to problems whose solutions can be verified in polynomial time.

• We define the class of nondeterministic polynomial time (NP) problems, contrasting it against polynomial time solvable problems (P)

• We define NP completeness and study SAT, a prototypical NP complete problem.

• We show how problems can be reduced to one another and study properties of these reductions.

Assignments

We will have quizzes after most of the lessons in this module. These quizzes are 'choose the correct answer' style and you will have unlimited attempts to solve them/get them right.

Programming Assignment

We will have a programming assignment that will help you approach the development of algorithms related to what we study in this module.

Duration: 1.5 hours

This module contains materials for the final exam. If you've upgraded to the for-credit version of this course, please make sure you review the additional for-credit materials in the introductory module and anywhere else they may be found.

This is a "take home" final exam. You have 24 hours to solve them.

• The time limit will not be enforced by Coursera. Instead, we will leave it to the honor code that you will submit the final exam 24 hours after you start.

• We reserve the right to go through your final exam and penalize your work if we find evidence that you took more than the given 24 hours.

• If you have accommodations, you can take more time as allowed by your accommodations.

The final is identical to a programming assignment: the problems are algorithmic coding problems that require you to use the concepts you have learned so far to solve problems.

We expect that the problems will cumulatively require 4 - 6 hours of work to finish and the remaining time will provide you the necessary flexibility.

Format

• Each problem has an algorithm design part: you should write pseudocode and work out the worst/expected case running time for your own benefit.

• However, these portions will not be graded.

• Each problem has a coding portion where you will have to code up your solution.

• The coding portion will be graded against automatic tests.

Rules

1. The exam is open book and notes.

1. You may access your own notes and any resources available through the Coursera class website.

2. You may access python language documentation and tutorials online.

2. Your code should be efficient: if you have inefficiency the notebook may not pass all the tests in time.

1. If the notebook does not pass all tests within a time limit (set internally by Cousera's autograder), you will not receive points.

3. Use of external resources other than those sanctioned above is disallowed:

1. Asking for help from anyone other than course facilitators is disallowed.

2. Course facilitators will be able to provide clarifications about problems but no extra hints will be provided.

3. Posting problems from this exam on external websites/forums is disallowed.

4. Cutting and pasting code fragments from external sources is prohibited.

5. Searching for solutions online is strictly forbidden.

4. Please do not post any part of this exam or solutions online.

5. It is highly recommended that you start the exam during a time when a course facilitator is available through email to provide timely clarifications.

6. Do not submit until you are ready

1. Do not submit the exam until you are fully done.