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. |
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)
- 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
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
Pattern Matching
[edit | edit source]Backtracking
[edit | edit source]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
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
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]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:
- 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]- ↑ 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.