Description
'
About the course
Professor Madhavan Mukund, a faculty from the Chennai Mathematical Institute, has designed this course on “Design and Analysis of Algorithms (DAA)” from the bottom up approach. This course covers the basic concepts in the design and analysis of algorithms, which includes Asymptotic complexity, O() notation, Sorting and searching. It also covers the Algorithms on graphs like exploration, connectivity, shortest paths, directed acyclic graphs, spanning trees. Apart from this, this course covers the design techniques like divide and conquer greedy, dynamic programming. Also, it covers data structures like heaps, the union of disjoint sets, search trees. Finally, it covers the concept of Intractability. This is completely an online course with worldwide accessibility.
Learning Outcomes
After completing this course, you will be able to:
- Develop self-confidence in writing efficient algorithms for the different set of given problems.
- Analyze the time complexity and other aspects of algorithms.
- Boost your hireability through innovative and independent learning.
Target Audience
The course can be taken by:
Students: All students who are pursuing professional graduate/post-graduate courses related to computer science and engineering or data science.
Teachers/Faculties: All computer science and engineering teachers/faculties.
Professionals: All working professionals from computer science / IT / Data Science domain.
Why learn Design and Analysis of Algorithms?
Algorithms are the building blocks of computer programs. They are as important to programming as recipes are for cooking. As a computer scientist, it is important to understand different types of algorithms so that one can use them properly. If you are working on an important piece of software, you will likely need to be able to estimate how fast it is going to run. Such an estimate will be less accurate without an understanding of runtime analysis. Furthermore, you need to understand the details of the algorithms involved so that you will be able to predict if there are special cases in which the software would not work quickly, or if it will produce unacceptable results.
Course Features
- 24X7 Access: You can view lectures as per your own convenience.
- Online lectures: 15 hours of online lectures with high-quality videos.
- Updated Quality content: Content is latest and gets updated regularly to meet the current industry demands.
Test Evaluation
Each lecture will have a quiz containing a set of multiple choice questions. Apart from that, there will be a final test based on multiple choice questions.
Your evaluation will include the overall scores achieved in each lecture quiz and the final test.
Certification
This course is free and it has no certificate.
Topics to be covered
- Module 01: Introduction, Analysis of Algorithms
- What is the course all about?
- Module 02: Example: Air Travel
- What is Air travel problem?
- Module 03: Example: Xerox shop
- What is the Xerox shop problem?
- Module 04: Example: Document similarity
- What is the document similarity problem?
- Module 05: Introduction and motivation
- How the analysis of algorithm is done and what is efficiency and time measurement?
- What is a sorting and video game example?
- What are the order of Magnitude and typical functions?
- Module 06: Input size, worst case, average case
- What are the input size and orders of magnitude?
- How basic operations are chosen and what is the worst case and average case complexity?
- Module 07 : Quantifying efficiency: O( ), Omega( ), Theta( )
- What are Upper bounds and Big O?
- What are Lower bounds, omega, tight bound and theta?
- Module 08 : Examples: Analysis of iterative and recursive algorithms
- What are the different examples of iterative algorithms?
- What are the different examples of recursive algorithms?
- Module 09: Arrays and lists
- How values are stored and Arrays and Lists?
- Module 10: Searching in an array
- How a value is searched in an array and what is Binary Search?
- Module 11: Selection Sort
- What is the Selection Sort algorithm and how it works?
- How is Selection Sort algorithm analyzed?
- Module 12: Insertion sort
- What is the Insertion Sort algorithm and how it works?
- How is the Insertion Sort algorithm analyzed?
- Module 13: Merge sort
- What is Merge Sort Algorithm and How it works?
- How is Merge Sort Algorithm implemented in a program?
- Module 14: Merge sort - analysis
- How is Merge Sort Algorithm analyzed?
- What are the variations on Merge and shortcomings of Merge Sort?
- Module 15: Quicksort
- What is the QuickSort Algorithm and how it works?
- How Is Quick Sort Algorithm implemented in a program?
- Module 16: Quicksort - analysis
- How is a Quick Sort Algorithm analyzed?
- What is the Iterative QuickSort?
- Module 17: Sorting - Concluding remarks
- Which sorting algorithm is the best?
- Module 18: Introduction to graphs
- How are Map and Graph coloring done?
- How is airline routing represented using Graph?
- Module 19: Representing graphs
- What is a Graph and what is an adjacency matrix?
- How to find the path in the adjacency matrix?
- What is Adjacency list?
- Module 20: Breadth-first search (BFS)
- What is the Breadth First Search (BFS) algorithm and how it works?
- How to analyze the complexity of BFS and what more can be done in BFS?
- Module 21: Depth-first search (DFS)
- What is Depth First Search (DFS) algorithm and how it works?
- What is the complexity of DFS and what is DFS numbering?
- Module 22: Applications of BFS and DFS
- What are the BFS and DFS trees?
- What are Directed cycles?
- What are Directed Acyclic Graphs and how directed graphs are connected?
- Module 23: Directed acyclic graphs: topological sort
- How is a problem modeled using graphs and what is Directed Acyclic Graph (DAG)?
- How Topological sorting algorithm works?
- What is the pseudo code for topological sorting algorithm?
- Module 24: Directed acyclic graphs: longest paths
- What is the longest path in DAG?
- What is the pseudo code for Longest Path?
- Module 25: Single source shortest paths: Dijkstra's algorithm
- How to find the shortest path?
- What is the single source shortest path problem?
- How this problem is represented algorithmically and what is Dijkstra's algorithm?
- Module 26: Dijkstra's algorithm: analysis
- Why Dijkstra's algorithm is a greedy algorithm and how much correctness is there in this algorithm?
- What is the complexity of Dijkstra's algorithm?
- What are the limitations of Dijkstra's algorithm?
- Module 27: Negative edge weights: Bellman-Ford algorithm
- What are the shortest paths in graphs where negative weights are allowed?
- What is the Bellman-Ford algorithm, its examples and complexity?
- Module 28: All pairs shortest paths
- How are shortest paths explored inductively?
- What is the Floyd-Warshall algorithm, its examples and complexity?
- What are the historical perspectives of the Floyd-Warshall algorithm and how paths are computed?
- Module 29: Minimum Cost Spanning Trees
- What is a Spanning tree and what are the various facts about trees?
- How to build a minimum cost spanning tree?
- Module 30: Prims Algorithm
- What are Prim's algorithm and its correctness?
- What is the Prim's algorithm for minimum cost spanning tree and its complexity?
- Module 31: Kruskal's algorithm
- What are Kruskal's algorithm and its correctness?
- What is the Kruskal's algorithm for minimum cost spanning tree and its complexity?
- Module 32: Union-Find using arrays
- What is Union-find data structure, its naive implementation and complexity?
- What is the improved implementation of Union-find data structure and why does this help?
- How to use a Union-find data structure in Kruskal's algorithm?
- Module 33: Union-Find using pointers
- How Is Union-find data structure implemented using pointers?
- How can path compression be done?
- Module 34: Priority Queues
- What is a Priority Queue and what are its various operations?
- Module 35: Heaps
- What are a heap and its examples?
- What is insert() operation in heap and its complexity?
- What is delete_max() operation in heap?
- How is heap implemented using arrays and what is heapify()?
- Module 36 : Heaps: Updating values, sorting
- How to update values in Heap?
- What is the complexity of Dijkstra's algorithm?
- Module 37: Counting inversions
- What is the divide and conquer principle, what are recommendation systems and how rankings are compared?
- How are inversions counted?
- How to implement inversions using divide and conquer principle?
- Module 38: the Closest pair of points
- How to find the closest pair of points in a video game example?
- Module 39: Binary Search Trees
- How heaps are implemented in the air traffic control problem?
- What are a Binary Search Tree (BST) and its operations?
- How a successor and a predecessor work?
- How to insert and delete a value in BST?
- Module 40: Balanced search trees
- What are the different notions and situations of balance?
- What are the various functions of balancing a tree and how the slope is computed?
- Module 41: Interval scheduling
- What are Greedy Algorithms and what is the problem of interval scheduling and what are the different greedy strategies?
- How is the algorithm implemented for Greedy strategies?
- Module 42: Scheduling with deadlines: minimizing lateness
- what are the greedy strategies for minimizing maximum lateness?
- What are the different aspects of optimal scheduling?
- Module 43: Huffman codes
- What is the concept of variable length coding and what are optimal prefix codes?
- How to view the codes as a Binary tree?
- What is Huffman's Algorithm and its optimality?
- What is the implementation, complexity and historical perspective of Huffman's algorithm?
- Module 44: Introduction to dynamic programming
- What is the inductive definition, optimal substructure property?
- What are the problem weighted interval scheduling and computational challenge?
- Module 45: Memoization
- What is a subproblem and how to evaluate it?
- What is memorization and how memoized Fibonacci is implemented?
- What is dynamic programming?
- Module 46: Grid Paths
- What is the problem of computing grid paths and its combinational solution?
- What is the inductive formulation of a grid problem?
- How to use dynamic programming on Grid and how is memoization different from dynamic programming?
- Module 47: Common subwords and subsequences
- What is the Longest Common Subword (LCW) problem and how it is addressed?
- What is the Longest Common Subsequence (LCS) problem and how it is addressed?
- Module 48: Edit distance
- What is the problem of edit distance and how it is related to LCS?
- How is the problem of edit distance addressed?
- Module 49: Matrix multiplication
- What is the problem of matrix multiplication?
- How is the problem of martix multiplication addressed?
- Module 50: Linear Programming
- What are Linear Programming and its example?
- What is the Simplex algorithm and what it does?
- How to solve a problem using the Simplex algorithm?
- Module 51: LP modeling: Production Planning
- What is the problem of production planning?
- How is the problem modeled using linear programming?
- Module 52: LP modeling: Bandwidth allocation
- What is the problem of Network Bandwidth and how it is modeled using linear programming?
- Module 53: Network Flows
- What is the oil network problem and how oil flow is formulated using Linear programming?
- What is the Ford-Fulkerson Algorithm and how it is implemented?
- Module 54: Reductions
- What is the problem of course allocation in a school?
- Module 55: Checking Algorithms
- What are efficient algorithms and checking algorithm?
- What is the Boolean Satisfiability problem?
- What is Travelling Salesman problem?
- What is the Independent Set problem?
- Module 56 : P and NP
- What are P and NP?
- How SAT and 3-SAT are reduced within NP?
- What is the Cook-Levin Theorem and how completeness of NP is achieved?
- Design and Analysis of Algorithms - Final Quiz
Note : Parts of this material has been sourced from NPTEL, adapted and modified to adhere to our Pedagogical requirements and uploaded to YouTube for reuse under the same license.
Reviews
There are no reviews yet.