CSCA 5414: Dynamic Programming, Greedy Algorithms

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.

   2. Resubmissions may be permitted but not lead to grade changes.