Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

NPTEL

Design and analysis of algorithms

NPTEL and Chennai Mathematical Institute via YouTube

Syllabus

Course Outline.
Example: Air Travel.
Example: Xerox shop.
Example: Document similarity.
Introduction and motivation.
Input size, worst case, average case.
Quantifying efficiency: O( ), Omega( ), Theta( ).
Examples: Analysis of iterative and recursive algorithms.
Arrays and lists.
Searching in an array.
Selection Sort.
Insertion sort.
Merge sort.
Merge sort - analysis.
Quicksort.
Quicksort - analysis.
Sorting - Concluding remarks.
Introduction to graphs.
Representing graphs.
Breadth first search (BFS).
Depth first search (DFS).
Applications of BFS and DFS.
Directed acylic graphs: topological sort.
Directed acylic graphs: longest paths.
Dijkstras algorithm: analysis.
Negative edge weights: Bellman-Ford algorithm.
All pairs shortest paths.
Minimum Cost Spanning Trees.
Prims Algorithm.
Kruskals algorithm.
Union-Find using arrays.
Union-Find using pointers.
Priority queues.
Heaps.
Heaps: Updating values, sorting.
Counting inversions.
Closest pair of points.
Binary Search Trees.
Balanced search trees.
Interval scheduling.
Scheduling with deadlines: minimizing lateness.
Huffman codes.
Introduction to dynamic programming.
Memoization.
Grid paths.
Common subwords and subsequences.
Edit distance.
Matrix multiplication.
Linear Programming.
LP modelling: Production Planning.
LP modelling: Bandwidth allocation.
Network Flows.
Reductions.
Checking Algorithms.
P and NP.
Single source shortest paths: Dijkstras algorithm.

Taught by

NPTEL-NOC IITM

Related Courses

Reviews

Start your review of Design and analysis of algorithms

Never Stop Learning!

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free