[go: up one dir, main page]
Scribd
Upload
3 views2 pages

ADA Revision Sheet

This document serves as a crash revision sheet for the ADA exam, outlining key concepts such as asymptotic notations, time complexities of various algorithms, and techniques like dynamic programming, greedy algorithms, and graph algorithms. It also covers NP-complete topics and methods like backtracking and branch and bound. The sheet emphasizes the importance of noting time complexity and identifying algorithm classes.

Uploaded by

ashwinikrishnamurthyudupa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views2 pages

ADA Revision Sheet

This document serves as a crash revision sheet for the ADA exam, outlining key concepts such as asymptotic notations, time complexities of various algorithms, and techniques like dynamic programming, greedy algorithms, and graph algorithms. It also covers NP-complete topics and methods like backtracking and branch and bound. The sheet emphasizes the importance of noting time complexity and identifying algorithm classes.

Uploaded by

ashwinikrishnamurthyudupa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

ADA Exam - 1 Page Crash Revision Sheet

- Asymptotic Notations:
- Big O (O): Upper bound (worst-case)
- Omega (Omega): Lower bound (best-case)
- Theta (Theta): Tight bound (average-case)
- Common Complexities: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n)

- Masters Theorem (T(n) = aT(n/b) + f(n)):


- Case 1: f(n) = O(n^log_b a - ) T(n) = Theta(n^log_b a)
- Case 2: f(n) = Theta(n^log_b a) T(n) = Theta(n^log_b a * log n)
- Case 3: f(n) = Omega(n^log_b a + ) T(n) = Theta(f(n)) [Regularity condition must hold]

- Time Complexities:
- Bubble/Selection Sort: O(n²)
- Merge Sort / Quick Sort (avg): O(n log n)
- Binary Search: O(log n)
- Matrix Multiplication (Strassen): ~O(n^2.81)

- Tree Traversals:
- Inorder: Left, Root, Right
- Preorder: Root, Left, Right
- Postorder: Left, Right, Root

- Dynamic Programming (DP):


- 0/1 Knapsack: DP[i][w] = max(DP[i-1][w], DP[i-1][w-wt[i]] + val[i])
- Matrix Chain Mult: DP[i][j] = min(DP[i][k] + DP[k+1][j] + cost)
- Optimal Substructure + Overlapping Subproblems

- Greedy Algorithms:
- Activity Selection: Choose earliest finishing first
- Huffman Coding: Use min-heap to combine least freq nodes
- MST: Kruskals (edges, sort), Prims (priority queue)
- Dijkstras: Shortest Path (min-priority queue)

- Graph Algorithms:
- BFS: Queue, level-order
- DFS: Stack/recursion, depth-first
- Warshalls: Transitive closure
- Floyds: All-pairs shortest path (DP)

- NP-Complete Topics:
- P: Solvable in poly time
- NP: Verifiable in poly time
- NP-Complete: In NP + All NP problems reduce to it
- Examples: n-Queens, Hamiltonian Circuit, Subset Sum, TSP

- Backtracking:
- Try Recurse Undo (e.g., n-Queens)
- Used when brute force is too slow

- Branch and Bound:


- Use bounds to prune search space
- Common in: TSP, Assignment Problem

- Tip: Always write time complexity & identify algorithm class (Greedy, DP, etc.)

You might also like