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