Design and Analysis of Algorithms

| Educational level: this is a tertiary (university) resource.

|

| Completion status: this resource is ~25% complete.

|

| Subject classification: this is a mathematics resource.

|

| Subject classification: this is an information technology resource.

|

Edsger Dijkstra invented the shortest-path algorithm that bears his name. He also made contributions to formal specification and verification, algorithm design, programming languages, program design, operating systems, and distributed processing. Much of his writing is free to access at the E.W. Dijkstra Archive.

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[1]:

* 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

[edit | edit source]

### Introduction

[edit | edit source]

* 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

[edit | edit source]

* 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

[edit | edit source]

* 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

Extra videos

* ADUni Video: Sorting 1

* ADUni Video: Sorting 2

### Divide and Conquer Methods

[edit | edit source]

* 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

[edit | edit source]

* 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

Extra videos

* ADUni Video: Knapsack, Bandwidth Min., Greedy Algorithms 1
* ADUni Video: Greedy Algorithms 2, Intro to NP-Completeness

### Pattern Matching

[edit | edit source]

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

### Backtracking

[edit | edit source]

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

### Graph Algorithms

[edit | edit source]

* 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

[edit | edit source]

* 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

Extra videos

* ADUni Video: Dynamic Programming 1
* ADUni Video: Dynamic Programming 2
* ADUni Video: Parsing
* ADUni Video: Knapsack, Bandwidth Min., Intro: Greedy Algorithms

### NP-Completeness

[edit | edit source]

* 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

Extra videos

* 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

[edit | edit source]

* 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

[edit | edit source]

* IIT Video: Maximum Bipartite Matching

## Problems Sets

[edit | edit source]

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

## Exams

[edit | edit source]

## Textbooks

[edit | edit source]

Free textbooks:

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

## Supplementary Materials

[edit | edit source]

* 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

## Related Websites

[edit | edit source]

## References

[edit | edit source]

1. ↑ Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Preface, pp.v.

## See also

[edit | edit source]

* Computer science program