TGGS > ECE > 573
Efficient Algorithms
Asymptotic Notation: Big O, Big Omega, Big Theta. Proof Techniques: Direct Proof, Proof by contradiction, Proof by contrapositive, Proof by induction. Sorting: Bubble sort, Selection sort, Insertion sort, Heap sort, Merge sort, Quicksort. Searching algorithms: Linear search, Binary search. Graph Algorithms: Minimum Spanning Tree, Breadth-first search, Depth-first search, Topological Sorting, Cycle Detection, Bellman-Ford algorithm. Dijkstra’s algorithm, Floyd-Warshall algorithm, Johnson’s algorithm. Data structures: List, Array, Stack, Queue, Hash table, Binary tree, Heap, Priority Queue. Algorithm paradigms: Divide-and-Conquer, Greedy algorithm, Dynamic programming. Computational complexity theory: Theory of NP-completeness. Approximation algorithms. State-Space Search: Brute-Force Search, Backtracking, Branch & Bound. Randomized algorithms.
Credits : 3 (3-0-6)
Pre-Requisites : No
| Course Learning Outcomes (CLOs) : | |
|---|---|
| CLO 1 | explain key mathematical concepts, namely, proof techniques and asymptotic notation, etc. as well as key algorithm design paradigms, namely, divide-and-conquer, dynamic programming, greedy algorithm, brute-force search, backtracking, and branch & bound, etc. |
| CLO 2 | analyze the temporal and the spatial complexity of any given algorithm using the knowledge of algebra, probabilistic analysis, and asymptotic notation |
| CLO 3 | apply the knowledge of algorithms learned in the lectures to solve relevant computational problems |
| CLO 4 | analyze the correctness of algorithms using proof techniques such as proof by contradiction and induction |
| CLO 5 | design efficient algorithms and complex data structures to efficiently solve computational problems |
| CLO1 | CLO2 | CLO3 | CLO4 | CLO5 | |
| ELO 1 | ✓ | ✓ | ✓ | ✓ | |
| ELO 2 | ✓ | ✓ | ✓ | ✓ | |
| ELO 3 | ✓ | ✓ | ✓ | ||
| ELO 4 | ✓ | ✓ | ✓ |
Revision : July 2021 (090245350)
Other Revisions : July 2020