Day |
Date |
Contents |
Slides |
Assignments |
1 |
Aug 12 |
Time complexities with examples - Asymptotic notations - Theta for tight bound,
big-O for upper bound and big-Omega for lower bound. Analogous to =, <= and >=.
o- strictly higher upper bound and small-omega- strictly lower lower bound analogous to > and < respectively.
Definitions to be learned from Cormen. |
|
|
2 |
Aug 13 |
Masters theorem with examples - finding epsilon > 0 for case 1 and case 3, c < 1 for case 3,
Going to substitution for exact solution, brute force method as a backup.
Sorting algorithms and time complexities in best, worst and average cases- Insertion sort-inversion,
Selection sort - swapping, Bubble sort, Merge sort - external sorting, Heap sort - build heap in O(n) - proof in Cormen,
Quick sort - worst case of O(n^2) |
|
Assignment 1 |
3 |
Aug 14 |
No discussion, Assignments on sorting- time complexity |
|
Assignment 2 |
4 |
Aug 15 |
Hashing- O(1)-search-perfect hashing, hash structure-table, Direct addressing, Open addressing- linear probing-primary clustering, quadratic probing-secondary clustering, double hashing |
|
|
5 |
Aug 16 |
Algorithm design techniques- Dynamic programming, Greedy algorithms, Divide and conquer - with examples, dynamic programming- top down and bottom up approach |
|
|
6 |
Aug 17 |
Graph search- breadth first search-level order traversal in tree, depth first search- algorithm and complexity analysis, applications, Spanning tree- minimum spanning tree, Prims and Kruskal's algorithm and analysis |
|
|
7 |
Aug 18-Aug 22 |
No discussion, solve previous gate questions on algorithms |
|
|
8 |
Aug 23 |
Shortest path algorithms- Relax function, Dijkstras algorithm- single source all destination,array and min heap implementation, failure(wrong output) for negative edge cycle, Bellman Ford- single source all destination, Floyd Warshall- Dynamic programming, Jhonson's algorithm- (optimised Floyd Warshall for sparse graph)- complexity and comparisons, programming- data structures used and initialisation |
|
|
|
|
|
|
For more information visit GO Classroom: https://classroom.gateoverflow.in/course/view.php?id=2