Design & Analysis of Algorithms (DAA)
DSSSB TGT CS — Section B P2 (Rank ~11). Focus: notations, paradigm ideas, complexity table, graphs.
1. Algorithm Properties
An algorithm should be:
| Property | Meaning |
|---|---|
| Input | Zero or more inputs |
| Output | At least one output |
| Definiteness | Clear, unambiguous steps |
| Finiteness | Terminates after finite steps |
| Effectiveness | Steps doable / basic enough |
Also: correctness, efficiency (time/space).
2. Asymptotic Notations
| Notation | Meaning |
|---|---|
| O (Big-O) | Upper bound (grows no faster than) |
| Ω (Omega) | Lower bound |
| Θ (Theta) | Tight bound (both upper & lower) |
- Ignore constants and lower-order terms: (3n^2+2n+5 = O(n^2)).
- Trap: (O) is not always “worst case” — it is an upper bound; people often use it for worst-case runtime informally.
3. Best / Average / Worst Case
| Case | Meaning |
|---|---|
| Best | Minimum time over inputs of size n |
| Average | Expected time over input distribution |
| Worst | Maximum time — common exam focus |
Example: Linear search — best O(1), worst O(n).
4. Algorithm Design Paradigms
| Paradigm | Idea | Examples |
|---|---|---|
| Divide & Conquer | Split → solve → combine | Merge sort, binary search, quicksort |
| Greedy | Locally optimal choice now | Kruskal, Prim, activity selection, Dijkstra* |
| Dynamic Programming (DP) | Optimal substructure + overlapping subproblems; store results | Fibonacci DP, 0/1 knapsack, LCS |
*Dijkstra is greedy-style shortest path (non-negative weights).
- Backtracking / branch-and-bound — awareness for exams.
5. Sorting Complexities (must memorize)
| Algorithm | Best | Average | Worst | Space (extra) | Stable? |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) avg | No* |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
*Typical in-place quicksort not stable.
- Comparison sort lower bound: Ω(n log n) worst-case for general comparison sorts.
6. Searching
| Method | Idea | Time |
|---|---|---|
| Linear | Scan sequentially | O(n) |
| Binary | Sorted array; halve search space | O(log n) |
- Binary search requires sorted data.
7. Graph Traversals
| BFS | DFS | |
|---|---|---|
| Structure | Queue | Stack / recursion |
| Explores | Level by level | Deep path first |
| Use | Shortest path in unweighted graph | Cycle detect, topo sort, connectivity |
8. Shortest Path & MST
| Algorithm | Idea |
|---|---|
| Dijkstra | Greedy; grow set of finalized distances; non-negative weights |
| Bellman-Ford | Handles negative edges; detect negative cycles (awareness) |
| Kruskal MST | Sort edges; add if no cycle (Union-Find) |
| Prim MST | Grow tree from a start vertex by cheapest edge out |
- MST = Minimum Spanning Tree — connect all vertices, min total weight, no cycle.
- Trap: Dijkstra fails with negative edge weights.
9. NP-Hard (light)
| Class (informal) | Idea | | --- | --- | --- | | P | Solvable in polynomial time | | NP | Verifiable in polynomial time (exam-level slogan) | | NP-complete / NP-hard | “Hard” problems; no known poly-time algorithm |
- Exam: TSP, some scheduling — often cited as hard; don’t over-formalize.
10. Space–Time Tradeoff
- Use more memory to save time (e.g. hashing, DP tables, indexes).
- Or compress/recompute to save space at cost of time.
- Classic: lookup tables vs recalculation.
Quick Revision Traps
- Θ = tight; O = upper; Ω = lower.
- Quicksort worst O(n²); merge always O(n log n).
- Binary search needs sorted input.
- BFS → queue; DFS → stack.
- Dijkstra → non-negative weights.
- Kruskal sorts edges; Prim grows from a vertex.
- Greedy ≠ always optimal for every problem; DP when overlapping subproblems.