Learn · NPTEL

Course10610613156 lectures

Design and analysis of algorithms

Prof. Madhavan Mukund · Chennai Mathematical Institute

Start with lecture 1 At NPTEL

About

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

Week 1 : Introduction

  1. Course Outline YouTube
  2. Example: Air Travel YouTube
  3. Example: Xerox shop YouTube
  4. Example: Document similarity YouTube
  5. Introduction and motivation YouTube
  6. Input size, worst case, average case YouTube
  7. Quantifying efficiency: O( ), Omega( ), Theta( ) YouTube
  8. Examples: Analysis of iterative and recursive algorithms YouTube

Week 2 : Searching and sorting

  1. Arrays and lists YouTube
  2. Searching in an array YouTube
  3. Selection Sort YouTube
  4. Insertion sort YouTube
  5. Merge sort YouTube
  6. Merge sort - analysis YouTube
  7. Quicksort YouTube
  8. Quicksort - analysis YouTube
  9. Sorting - Concluding remarks YouTube

Week 3 : Graphs

  1. Introduction to graphs YouTube
  2. Representing graphs YouTube
  3. Breadth first search (BFS) YouTube
  4. Depth first search (DFS) YouTube
  5. Applications of BFS and DFS YouTube
  6. Directed acylic graphs: topological sort YouTube
  7. Directed acylic graphs: longest paths YouTube

Week 4 : Weighted graphs

  1. Single source shortest paths: Dijkstra's algorithm YouTube
  2. Dijkstra's algorithm: analysis YouTube
  3. Negative edge weights: Bellman-Ford algorithm YouTube
  4. All pairs shortest paths YouTube
  5. Minimum Cost Spanning Trees YouTube
  6. Prim's Algorithm YouTube
  7. Kruskal's algorithm YouTube

Week 5: Data Structures: Union-Find and Heaps

  1. Union-Find using arrays YouTube
  2. Union-Find using pointers YouTube
  3. Priority queues YouTube
  4. Heaps YouTube
  5. Heaps: Updating values, sorting YouTube
  6. Counting inversions YouTube
  7. Closest pair of points YouTube

Week 6: Data Structures: Search Trees

  1. Binary Search Trees YouTube
  2. Balanced search trees YouTube
  3. Interval scheduling YouTube
  4. Scheduling with deadlines: minimizing lateness YouTube
  5. Huffman codes YouTube

Week 7: Dynamic Programming

  1. Introduction to dynamic programming YouTube
  2. Memoization YouTube
  3. Grid Paths YouTube
  4. Common subwords and subsequences YouTube
  5. Edit distance YouTube
  6. Matrix multiplication YouTube

Week 8: Linear Programming and Network Flows

  1. Linear Programming YouTube
  2. LP modelling: Production Planning YouTube
  3. LP modelling: Bandwidth allocation YouTube
  4. Network Flows YouTube
  5. Reductions YouTube
  6. Checking Algorithms YouTube
  7. P and NP YouTube

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
Chennai Mathematical Institute
Department
Computer Science and Engineering
Teacher
Prof. Madhavan Mukund
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Madras.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed