CS313 | Design and Analysis of Algorithms
- Rating: 4.85
- (439)
Course overview
Design and Analysis of Algorithms introduces algorithms by looking at the real-world problems that motivate students. The course teaches students a range of design and analysis techniques for problems that arise in computing applications. The course encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.
What you will learn
-
CLO-1 Reproduce design of algorithms using different algorithms design techniques (C3 - Applying).
-
CLO-2 Analyze the time and space complexity of different algorithms (C4 - Analyzing).
-
CLO-3 Implement the algorithms, compare the implementations empirically (C5 - Evaluating).
- Asymptotic Analysis
- Algorithm Warm-up, Big-O Notation, Fibonacci Series, Greatest Common Divisor
- Greedy Algorithms
- Largest Number, Car Fueling, Grouping Children, Fractional Knapsack
- Divide-and-Conquer
- Linear & Binary Search, Master Theorem, Selection, Merge, and Quick Sort
- Dynamic Programming
- The Alignment Game, Computing Edit Distance Knapsack, Placing Parentheses, Maximum Value of an Arithmetic Expression
- Decomposition of Graphs
- Directed Acyclic Graphs, Paths in Graphs, Dijkstra's Algorithm, Bellman-Ford Algorithm, Minimum Spanning Trees
- Paths in Graphs
- Bidirectional Dijkstra, A* Algorithm, Performance of A*, Bidirectional A* Witness Search, Query, Node Ordering
Course program
| Lessons | Name | Description | Duration | Week | Slides |
|---|---|---|---|---|---|
| 1 | Introduction to Course | Design and Analysis of Algorithms | 1 hours | 1 | AAF1901-01 |
| 2 | Algorithmic Warm Up | Maximum Pairwise Product, Fibonacci Series | 2 hours | 1 | AAF1901-02 |
| 3 | Asymptotic Notations: Big O | Computing Run-time, Growth Rate | 3 hours | 2 | AAF1901-03 |
| 4 | Main Ingredients of Greedy Algorithms | Greedy Algorithm | 1 hours | 3 | AAF1902-01 |
| 5 | Grouping Children | Greedy Algorithm | 2 hours | 3 | AAF1902-02 |
| 6 | Fractional Knapsack | Greedy Algorithm | 3 hours | 4 | AAF1902-03 |
| 7 | Divide and Conquer | Main Idea | 1 hours | 5 | AAF1903-01 |
| 8 | Linear Search | Divide and Conquer | 1 hours | 5 | AAF1903-02 |
| 9 | Binary Search | Divide and Conquer | 1 hours | 5 | AAF1903-03 |
| 10 | Polynomial Multiplication | Divide and Conquer | 3 hours | 6 | AAF1903-04 |
| 11 | Master Theorem | Divide and Conquer | 3 hours | 7 | AAF1903-05 |
| 12 | Selection Sort | Divide and Conquer | 1 hours | 8 | AAF1903-06 |
| 13 | Merge Sort | Divide and Conquer | 1 hours | 8 | AAF1903-07 |
| 14 | Quick Sort | Divide and Conquer | 1 hours | 8 | AAF1903-08 |
| 15 | Change Problem | Dynamic Programming | 1 hours | 9 | AAF1904-01 |
| 16 | String Comparison | Dynamic Programming | 2 hours | 9 | AAF1904-02 |
| 17 | Knapsack | Dynamic Programming | 1 hours | 10 | AAF1904-03 |
| 18 | Placing Paranthesis | Dynamic Programming | 2 hours | 10 | AAF1904-04 |
| 19 | Representing Graphs | Decomposition of Graphs | 3 hours | 11 | AAF1905-01 |
| 20 | Exploring Graphs | Decomposition of Graphs | 1 hours | 12 | AAF1905-02 |
| 21 | Connectivity in Graphs | Decomposition of Graphs | 2 hours | 12 | AAF1905-03 |
| 22 | Topological Sorting | Directed Acyclic Graph | 1 hours | 13 | AAF1905-04 |
| 23 | Strongly Connected Components | Directed Graph | 2 hours | 13 | AAF1905-05 |
| 24 | Most Direct Route - BFS | Paths in Graph | 1 hours | 14 | AAF1906-01 |
| 25 | Fastest Route - Dijkstra Algorithm | Paths in Graph | 2 hours | 14 | AAF1906-02 |
| 26 | Currency Exchange - Bellman-Ford Algorithm | Paths in Graph | 1 hours | 15 | AAF1906-03 |
| 27 | Kruskal Algorithm and Prim Algorithms | Minimum Spanning Tree | 2 hours | 15 | AAF1906-04 |
| Lessons | Name | Description | Duration | Week | Slides |
|---|---|---|---|---|---|
| 1 | Stable Matching | Gale-Shapley Algorithm | 1 hours | 1 | DAAF1801 |
| 2 | Gale-Shapley Demo | Representative Problems | 2 hours | 1 | DAAF1802 |
| 3 | Algorithm Analysis | Asymptotic Order of Growth | 3 hours | 2 | DAAF1803 |
| 4 | Binary Search Demo | Algorithm Analysis | 3 hours | 3 | DAAF1804 |
| 5 | Graph | Connectivity, Bipartite Graph, DAG, Topological Sort | 3 hours | 4 | DAAF1805 |
| 6 | Greedy Algorithms I | Coin Change, Interval Scheduling and Partitioning | 3 hours | 5 | DAAF1806 |
| 7 | Earliest-Finish-Time-First Algorithm | Interval Scheduling | 3 hours | 6 | DAAF1807 |
| 8 | Earliest-Start-Time-First Algorithm | Interval Partitioning | 3 hours | 7 | DAAF1808 |
| 9 | Greedy Algorithms II | Shortest Path, MST, Clustering, Min-Cost Arborescences | 3 hours | 8 | DAAF1809 |
| 10 | Dijkstra Algorithm | Shortest Path - Efficient Implementation | 3 hours | 9 | DAAF1810 |
| 11 | Minimum Spanning Tree | Red-Blue, Prim, Kruskal, Boruvka Algorithms | 3 hours | 10 | DAAF1811 |
| 12 | Edmonds Branching | Min-Cost Arborescences | 3 hours | 11 | DAAF1812 |
| 13 | Divide and Conquer | Merge Sort, Quick Sort, Median and Selection | 3 hours | 12 | DAAF1813 |
| 14 | Merge Sort | Sorting Algorithm | 3 hours | 13 | DAAF1814 |
| 15 | Merge Invert | Merge and Count | 3 hours | 14 | DAAF1815 |
| 16 | Quick Select | 3-Way Partition | 3 hours | 15 | DAAF1816 |