# Design and Analysis of Algorithms

Donald Knuth lists, in the preface of The Art of Computer Programming Vol 3, the following as the important questions of design and analysis of algorithms:
* How are good algorithms discovered?
* How can given algorithms and programs be improved?
* How can the efficiency of algorithms be analyzed mathematically?
* How can a person chose rationally between different algorithms for the same task?
* In what senses can algorithms be proved "best possible"?
* How does the theory of computing interact with practical considerations?
* How can external memories like tapes, drums, or disks be used efficiently with large databases?

## Course Outline
### Introduction

* IIT Video: Introduction to the Design and Analysis of Algorithms
* MIT Video: Introduction to Algorithms, Insertion Sort, Mergesort
* Lesson 1: Introduction to algorithms
* Lesson 2: Insertion sort

### Mathematical Foundations

* Asymptotic Notation - Recurrences-Substitution-Master-Method (Video)
** Asymptotic Notation - Recurrences - Substitution, Master Method (PDF)
* IIT Video: Algorithm Analysis Framework 1
* IIT Video: Algorithm Analysis Framework 2
* IIT Video: Asymptotic Notations
* Lesson 1: Solving Recurrence Relations

### Sorting

* MIT Video: Quicksort, Randomized Algorithms
* IIT Video: Average case Analysis of Quicksort
* MIT Video: Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort
* IIT Video: Lower Bounds for Sorting
* ADUni Video: Sorting 1
* ADUni Video: Sorting 2

### Divide and Conquer Methods

* IIT Video: Algorithm Design Techniques : Basics [46:23.]
* MIT Video: Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication
* IIT Video: Divide and Conquer 1
* IIT Video: Divide and Conquer 2 - Median Finding
* IIT Video: Divide and Conquer 3 - Surfing Lower Bounds
* IIT Video: Divide and Conquer 4 - Closest Pair of Points

### Greedy Methods

* MIT Video: Greedy Algorithms, Minimum Spanning Trees
* IIT Video: Greedy Algorithms 1
* IIT Video: Greedy Algorithms 2
* IIT Video: Greedy Algorithms 3
* IIT Video: Greedy Algorithms 4
* ADUni Video: Knapsack, Bandwidth Min., Greedy Algorithms 1
* ADUni Video: Greedy Algorithms 2, Intro to NP-Completeness

### Pattern Matching

* IIT Video: Pattern Matching 1
* IIT Video: Pattern Matching 2

### Backtracking

* IIT Video: Backtracking 1
* IIT Video: Backtracking 2

### Graph Algorithms

* ADUni Video: Graph Algorithms 1 - Topological Sorting, Prim's Algorithm
* ADUni Video: Graph Algorithms 2 - DFS, BFS, Kruskal's Algorithm, Union Find Data Structure
* ADUni Video: Graph Algorithms 3: Shortest Path
* IIT Video: Shortest Paths 1: Properties, Dijkstra's Algorithm, Breadth-first Search
* IIT Video: Shortest Paths 2: Bellman-Ford, Linear Programming, Difference Constrain
* IIT Video: Shortest Paths 3: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson

### Dynamic Programming

* IIT Video: Introduction to Dynamic Programming
* IIT Video: Longest Common Subsequence
* IIT Video: Matrix Chain Multiplication
* IIT Video: Scheduling with Startup and Holding Costs
* MIT Video: Dynamic Programming, Longest Common Subsequence
* ADUni Video: Dynamic Programming 1
* ADUni Video: Dynamic Programming 2
* ADUni Video: Parsing
* ADUni Video: Knapsack, Bandwidth Min., Intro: Greedy Algorithms

### NP-Completeness

* IIT Video: NP-Completeness 1 - Motivation
* IIT Video: NP-Completeness 2
* IIT Video: NP-Completeness 3
* IIT Video: NP-Completeness 4
* IIT Video: NP-Completeness 5
* IIT Video: NP-Completeness 6
* ADUni Video: Greedy Algorithms 2, Intro to NP-Completeness
* ADUni Video: NP Completeness 2, Reductions
* ADUni Video: NP Completeness 3, More Reductions
* ADUni Video: NP Completeness 4

### Approximation algorithms

* IIT Video: Approximation Algorithms 1
* IIT Video: Approximation Algorithms 2
* IIT Video: Approximation Algorithms 3 - NP-Complete Problems
* ADUni Video: Approximation Algorithms Algorithms

### Maximum Bipartite Matching

* IIT Video: Maximum Bipartite Matching

## Problems Sets

solve the recurrence equuation for t(n)=2t(n-1)+n2^n+n^2

## Textbooks

Free textbooks:
* Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

## Supplementary Materials

* Extra lecture videos:
** http://www.cs.sunysb.edu/~algorith/video-lectures/
** http://www.cise.ufl.edu/~sahni/cop3530/
** http://www.srcf.ucam.org/algorithms/videos.html
* Full algorithms course materials by Jeff Erickson
* Art of Programming Contest by Ahmed Shamsul Arefin
* A full course on Algorithmic Problem Solving
* Problems on Algorithms by Ian Parberry
* Books related to algorithms and computer science in general