# Design and analysis of algorithms

- Institution: Chennai Mathematical Institute
- Department: Computer Science and Engineering
- Teacher: Prof. Madhavan Mukund
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106106131)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106106131)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

This course will cover basic concepts in the design and analysis of algorithms.

Asymptotic complexity, O() notation

Sorting and search

Algorithms on graphs: exploration, connectivity, shortest paths, directed acyclic graphs, spanning trees

Design techniques: divide and conquer, greedy, dynamic programming

Data structures: heaps, union of disjoint sets, search trees

Intractability

INTENDED AUDIENCE: Students in BE/BTech Computer Science, 2nd/3rd year.

PRE-REQUISITES: Exposure to introductory courses on programming and data structures.

INDUSTRY SUPPORT: This course should be of value to any company working in the area of software services and products.

## Lectures

1. [Course Outline](https://invisiblenetwork.ai/learn/nptel/106106131/71f24de8abaf) (YouTube)
2. [Example: Air Travel](https://invisiblenetwork.ai/learn/nptel/106106131/d2b873443a86) (YouTube)
3. [Example: Xerox shop](https://invisiblenetwork.ai/learn/nptel/106106131/23506245d7e2) (YouTube)
4. [Example: Document similarity](https://invisiblenetwork.ai/learn/nptel/106106131/b18b90ef2026) (YouTube)
5. [Introduction and motivation](https://invisiblenetwork.ai/learn/nptel/106106131/bf5e60002e57) (YouTube)
6. [Input size, worst case, average case](https://invisiblenetwork.ai/learn/nptel/106106131/fff3156ab047) (YouTube)
7. [Quantifying efficiency: O( ), Omega( ), Theta( )](https://invisiblenetwork.ai/learn/nptel/106106131/823a753d093f) (YouTube)
8. [Examples: Analysis of iterative and recursive algorithms](https://invisiblenetwork.ai/learn/nptel/106106131/cf878b3d62db) (YouTube)
9. [Arrays and lists](https://invisiblenetwork.ai/learn/nptel/106106131/a63592a0507a) (YouTube)
10. [Searching in an array](https://invisiblenetwork.ai/learn/nptel/106106131/fd726923e870) (YouTube)
11. [Selection Sort](https://invisiblenetwork.ai/learn/nptel/106106131/d2709f14b030) (YouTube)
12. [Insertion sort](https://invisiblenetwork.ai/learn/nptel/106106131/aa3917d60394) (YouTube)
13. [Merge sort](https://invisiblenetwork.ai/learn/nptel/106106131/08f6e1d70195) (YouTube)
14. [Merge sort - analysis](https://invisiblenetwork.ai/learn/nptel/106106131/76df065a5888) (YouTube)
15. [Quicksort](https://invisiblenetwork.ai/learn/nptel/106106131/11846da8ca64) (YouTube)
16. [Quicksort - analysis](https://invisiblenetwork.ai/learn/nptel/106106131/fd06bf0d7e01) (YouTube)
17. [Sorting - Concluding remarks](https://invisiblenetwork.ai/learn/nptel/106106131/2a19798cda0c) (YouTube)
18. [Introduction to graphs](https://invisiblenetwork.ai/learn/nptel/106106131/3bb1eed34ee9) (YouTube)
19. [Representing graphs](https://invisiblenetwork.ai/learn/nptel/106106131/e1006eda0583) (YouTube)
20. [Breadth first search (BFS)](https://invisiblenetwork.ai/learn/nptel/106106131/c40a2af8745c) (YouTube)
21. [Depth first search (DFS)](https://invisiblenetwork.ai/learn/nptel/106106131/95e80dc821b2) (YouTube)
22. [Applications of BFS and DFS](https://invisiblenetwork.ai/learn/nptel/106106131/1d35d32abc39) (YouTube)
23. [Directed acylic graphs: topological sort](https://invisiblenetwork.ai/learn/nptel/106106131/6cd424a042db) (YouTube)
24. [Directed acylic graphs: longest paths](https://invisiblenetwork.ai/learn/nptel/106106131/27d100e33d19) (YouTube)
25. [Single source shortest paths: Dijkstra's algorithm](https://invisiblenetwork.ai/learn/nptel/106106131/784ec6d29be8) (YouTube)
26. [Dijkstra's algorithm: analysis](https://invisiblenetwork.ai/learn/nptel/106106131/27278835f57f) (YouTube)
27. [Negative edge weights: Bellman-Ford algorithm](https://invisiblenetwork.ai/learn/nptel/106106131/40f67025227f) (YouTube)
28. [All pairs shortest paths](https://invisiblenetwork.ai/learn/nptel/106106131/c17ee8bb9c1f) (YouTube)
29. [Minimum Cost Spanning Trees](https://invisiblenetwork.ai/learn/nptel/106106131/22065cec7374) (YouTube)
30. [Prim's Algorithm](https://invisiblenetwork.ai/learn/nptel/106106131/47aa5bac4067) (YouTube)
31. [Kruskal's algorithm](https://invisiblenetwork.ai/learn/nptel/106106131/2ffea71c8503) (YouTube)
32. [Union-Find using arrays](https://invisiblenetwork.ai/learn/nptel/106106131/f6ebe157b605) (YouTube)
33. [Union-Find using pointers](https://invisiblenetwork.ai/learn/nptel/106106131/4655a706ac8c) (YouTube)
34. [Priority queues](https://invisiblenetwork.ai/learn/nptel/106106131/5537a5658076) (YouTube)
35. [Heaps](https://invisiblenetwork.ai/learn/nptel/106106131/91165c781b0f) (YouTube)
36. [Heaps: Updating values, sorting](https://invisiblenetwork.ai/learn/nptel/106106131/6fb93704bcdf) (YouTube)
37. [Counting inversions](https://invisiblenetwork.ai/learn/nptel/106106131/46bedbb05e7a) (YouTube)
38. [Closest pair of points](https://invisiblenetwork.ai/learn/nptel/106106131/1cfd7f67da4d) (YouTube)
39. [Binary Search Trees](https://invisiblenetwork.ai/learn/nptel/106106131/d900896d1038) (YouTube)
40. [Balanced search trees](https://invisiblenetwork.ai/learn/nptel/106106131/0e26f33c527d) (YouTube)
41. [Interval scheduling](https://invisiblenetwork.ai/learn/nptel/106106131/da36741ac426) (YouTube)
42. [Scheduling with deadlines: minimizing lateness](https://invisiblenetwork.ai/learn/nptel/106106131/e250752c2250) (YouTube)
43. [Huffman codes](https://invisiblenetwork.ai/learn/nptel/106106131/e76406de8ce9) (YouTube)
44. [Introduction to dynamic programming](https://invisiblenetwork.ai/learn/nptel/106106131/b7e158d69cfe) (YouTube)
45. [Memoization](https://invisiblenetwork.ai/learn/nptel/106106131/de7bde0362c8) (YouTube)
46. [Grid Paths](https://invisiblenetwork.ai/learn/nptel/106106131/65b251a2ee92) (YouTube)
47. [Common subwords and subsequences](https://invisiblenetwork.ai/learn/nptel/106106131/4c4c0b2d2268) (YouTube)
48. [Edit distance](https://invisiblenetwork.ai/learn/nptel/106106131/1b47e05881d7) (YouTube)
49. [Matrix multiplication](https://invisiblenetwork.ai/learn/nptel/106106131/0770fd231c56) (YouTube)
50. [Linear Programming](https://invisiblenetwork.ai/learn/nptel/106106131/7054f72f4a6b) (YouTube)
51. [LP modelling: Production Planning](https://invisiblenetwork.ai/learn/nptel/106106131/15941050007b) (YouTube)
52. [LP modelling: Bandwidth allocation](https://invisiblenetwork.ai/learn/nptel/106106131/2a0b2258ffe9) (YouTube)
53. [Network Flows](https://invisiblenetwork.ai/learn/nptel/106106131/476393d9bf10) (YouTube)
54. [Reductions](https://invisiblenetwork.ai/learn/nptel/106106131/f03cd949c61a) (YouTube)
55. [Checking Algorithms](https://invisiblenetwork.ai/learn/nptel/106106131/baf4ad167684) (YouTube)
56. [P and NP](https://invisiblenetwork.ai/learn/nptel/106106131/d1c280f1f323) (YouTube)