Algorithms Analysis & Design
Topics Covered in the repo:
- Introduction: Algorithms for accuracy, efficiency (space, time); Algorithms in real world
- Time Complexity: RAM Model, Loop iterations vs execution time, Growth Functions, best-worst scenario
Searching algorithms
- Binary: Logical explanation on the logarithmic time complexity, fitness/feedback function, finding upper - lower bound
- Ternary: Concept, Advantages over binary search
- Balancing between no. of search steps and cost of each step: why quaternary search is not that popular
Sorting algorithms
- Case analysis on N^2 sorting algorithms: Bubble, Insertion/Selection; # of iterations, # of swaps on best/worst scenario
- Linear (case specific) time sorting: Count sort, a good example of why nested iterations is not always multiplied for time complexity"
Sorting contd.
- NlgN sorting: Merge, Quick (fixed and random pivots) Asymptotic Notations: upper, lower, tight bound complexity
Divide and Conquer (DnC) algorithms
- Look back to merge, quick sort
- Max-sum subarray: O(NlgN) [can also be solved in O(N^3), O(N^2), O(N)] DnC contd.: Karatsuba multiplication Time complexity of recursive/DnC algorithms: recursion tree, substitution method, master theorem BFS: traversal, shortest path on unweighted graph, Bicolorable/Bipartite graph detection, cycle detection (odd or even length)
-
DFS: traversal (review), Edge classification, cycle detection
-
What is DAG, Topological ordering, Strongly Connected Components (SCC, Kosaraju's algo)
-
Shortest path algo: What is SSSP and APSP, Dijkstra's algo, Bellman-Ford Algo (Negative-weight edges in play)
-
MST: Kruskal's (+DSU)
-
Greedy: Huffman coding, Interval scheduling (covered in lab before mid)
-
Complexity Class: Constant, Polynomial, Exponential, P-NP
-
Backtracking Algorithms: 8 queen Problem
-
Backtracking Algorithms: 15 puzzle Problem
-
DP-1: Fractional vs 0-1 Knapsack
-
DP-2: LCS, Recurrence relation, Properties: overlapping subprob and opt. substructure