COURSE OUTLINE: 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.
Overview
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
Tags
Related Courses
Related articles
Reviews
4.6 rating, based on 7 Class Central reviews
-
Abhishek Wayalkar
The Design and Analysis of Algorithms* course was well-structured and comprehensive. It effectively covered essential topics such as time and space complexity, divide-and-conquer, greedy algorithms, dynamic programming, and graph algorithms. The course was clear and practical, providing a solid foundation in algorithm design and analysis.
-
It is a good course for students👍🏻 it is really helpful for us thank you for this course language is very understandable also net and clean video quality
-
Nanda MahalkarDAA course was challenging but rewarding. Learned advanced algorithms and data structures. Practical applications were insightful. Highly recommend for CS students. -
Tanvi ChaudhariDesign analysis of algorithms is difficult subject to me but after completing this course is going simple. In that all key points are covered. It's really helpful. -
Bhavna ThombreThe course is very nice and it helps in to new knowledge about design analysis and algorithms. The course is very informative and easy to learn and understand. -
Course is very helpful for understanding concepts of DAA.This course explains in detail all things .
-
Design and analysis of algorithms. Its really helped me to again my extra knowledge. I came to know that how to design algorithms.finally tq u for this online cousres
