This website contains nearly complete solutions to the bible textbook - Introduction to Algorithms Third Edition, published by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

hope this helps :)

Dark Mode

Filter

1

2

https://algs4.cs.princeton.edu/cheatsheet/

Commonly encountered functions, helpful formulae and approximations, features of logarithms, asymptotic notations, and solutions to divide-and-conquer recurrences are among the mathematics used in the study of algorithms.

3

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

4

Can anyone tell any other algorithm which is there in syllabus apart from those mentioned below. Also, tell if something below is not there in syllabus

Dynamic Programming:-

1. Matrix Chain Multiplication

2. LCS

3. Subset Sum

4. 0/1 Knapsack

5. Floyd Warshall

6. OBST

7. Closest Pair

Greedy Method:-

1. Prim's

2. Kruskal's

3. Djikstra

4. Bellman Ford

5. Huffman Coding

6. BFS

7. Fractional Knapsack

8. Topological Sort

9. Stongly Connected Component

Backtracking:-

1. DFS

Branch and Bound:-

1. Travelling Salesman

Dynamic Programming:-

1. Matrix Chain Multiplication

2. LCS

3. Subset Sum

4. 0/1 Knapsack

5. Floyd Warshall

6. OBST

7. Closest Pair

Greedy Method:-

1. Prim's

2. Kruskal's

3. Djikstra

4. Bellman Ford

5. Huffman Coding

6. BFS

7. Fractional Knapsack

8. Topological Sort

9. Stongly Connected Component

Backtracking:-

1. DFS

Branch and Bound:-

1. Travelling Salesman

5

**Important Questions**

http://gateoverflow.in/questions/algorithms?sort=featured

Sometimes we need to walk through a given algorithm to get the answer. These questions must not be missed as there is very little chance of a mistake.

To see more, click for the full list of questions or popular tags.