Day 
Date 
Contents 
Slides 
Assignments 
1 
Aug 12 
Time complexities with examples  Asymptotic notations  Theta for tight bound,
bigO for upper bound and bigOmega for lower bound. Analogous to =, <= and >=.
o strictly higher upper bound and smallomega 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 sortinversion,
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)searchperfect hashing, hash structuretable, Direct addressing, Open addressing linear probingprimary clustering, quadratic probingsecondary 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 searchlevel 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 18Aug 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