1 | DS + DAA

1.1 DS A. AVL (Adelson, Velski & Landis) [O(log n)]

B. Binary [O(log n)]
1.1.1 Data C. Red-black [O(log n)]
D. Binary Search [O(n)] (pre-, in- and post-order traversal]
1. Data vs. Info
E. B [O(log n)]
2. Basic Terminology
F. B+ [O(logb n), b is order]
(a) Data and Data item G. B∗ [O(log n)]
(b) Group and Elementary items H. Minimum Spanning [Kruskal’s O(|E| log |E|) (select
(c) Entity and Entity Set smallest one) and Prim’s O(|E| log |V |) - binary heap
(d) Field, Record, File and O(|E| + |V | log |V |) - Fibonacci heap (start from one
(e) Primary Key node) Algorithms]
(f) Key-value pairs
ii. Graph [Traversal]
1.1.2 Data Structures A. Depth First [O(|E| + |V |)][ (stack, adjacent nodes)
B. Breadth First [O(|E| + |V |)] (queue, current node)
1. Simple or Primitive
iii. Heap
(a) Boolean
A. Binary [O(n)]
(b) Character
B. Binomial [O(log n)]
(c) Integer
C. Fibonacci [O(log n)]
(d) Floating-point
(e) Double 3. Abstract
(f) Reference (Pointers) (a) List
(g) Enumerated type (b) Stack
2. Composite or Non-primitive or structure or aggregate (c) Queue
(a) Linear i. Double-ended (Deque)
ii. Priority
i. Array [O(n)]
iii. Circular
ii. List [O(n)]
(d) Tree
A. Array List [O(n)]
(e) Graph
B. Linked List (Singly, Doubly and Circular) [O(n)]
(b) Non-Linear 1.1.3 DS Operations
i. Tree 1. Inserting

2
 2. Deleting 8. Types of Algorithms
3. Traversing/Visiting (a) Constant (1)
4. Searching (b) Logarithmic (log n)
5. Sorting (c) Linear (n)
6. Merging (d) Linear Logarithmic (n log n)
(e) Quadratic (n2 )
1.2 DAA (f) Cubic (n3 )
(g) Exponential (2n )
1.2.1 Algorithms 9. Recurrence Analysis
1. Writing Algorithms [SPARKS] (a) Substitution Method
2. Algorithm Criteria (b) Recursion-tree Method
(a) Input (c) Master Method
(b) Output
(c) Definiteness 1.2.2 Sorting and Searching
(d) Finiteness
1. Properties of Sorting Algorithms
(e) Effectiveness
(f) Unambiguous (a) In-place and Not-in-place (extra space requirement)
(b) Internal and External (size of data ≤, > RAM)
3. Analysis of Algorithms
(c) Stable and Not-stable (preserves order of equal elements)
(a) Priori (d) Adaptive and Non-adaptive (takes adv. of already sorted items)
(b) Posterior
2. Sorting
4. Types of Analysis (Analyzing Cases)
(a) Bubble [O(n2 )] (comparison bubble goes to end; sort backward)
(a) Best Case [Bogus] (b) Insertion [O(n2 )] (start sorting from the very end)
(b) Average Case [Sometimes Done] (c) Selection [O(n2 )] (select and sort/swap the smallest element)
(c) Worst Case [Usually Done] (d) Merge [O(n log n)] (divide into subs, to the end; sort bottomup)
5. Asymptotic Analysis (e) Quick [O(n log n)] (use pivot to divide the list in two sorted ones)
(a) O-Notation [Upped Bound, Worst Case] (f) Heap [O(n log n)] (build-max-heap using heapify)
(b) θ-Notation [Order, Average Case] (g) Radix [O(wn)] (compare from lsd to msd, word size w)
(c) Ω-Notation [Lower Bound, Best Case] (h) Shell [O(n6/5 )] (sort every 4th element, 2nd , at last use insertion)
√
6. Rates of Growth [1, log log n, log n, log2 n, 2log n , n, log n!, n log n, 3. Searching
n2 , 2n , 4n , n!, 22 ]
n
(a) Linear or√Sequential [O(n)] (compare √ every element)
7. Some Important Run-times (b) Jump [O( n)] (sorted, jump m = n items, compare; use linear)
(a) 2n+1 = O(2n ) (c) Binary [O(log n)] (sorted, divide into two, compare with mid)
(b) n! = O(nn ) (d) Interpolation [O(log log n)] (Binary wt mid = L + (H+L)×(X−A[L])
A[H]−A[L]
)
(c) log n! = O(n log n) (e) Hash
1.2.3 Divide-and-Conquer 3. The Traveling Salesperson Problem
1. The Method
2. Binary Search 1.2.8 Shortest Path Problems
3. Mergesort 1. Single-source
4. Quicksort (a) Dijkstra’s [O(|V |2 ) - queue, O(|E|+|V | log |V |) - Fibonacci heap]
5. Selection sort (b) Bellman-ford [O(|V | · |E|)] (Moore, -ve edges allowed)
6. Strassen’s Matrix Multiplication
2. Single-destination (single-source with reverting edge-direction)
1.2.4 The Greedy Method 3. Single-pair (use single-source)
4. All-pairs
1. The Method
2. Counting Coins Problem (a) Floyd-warshall [O(|V |3 )] (-ve edges allowed)
3. Knapsack Problem
4. Job Sequencing with Deadlines 1.2.9 Formulas
5. Minimum Spanning Trees 2n
1. Ways of putting balanced parenthesizes = n+1 Cn
= Catalan number,
6. Single Source Shortest Paths
where n is number of operators.
1.2.5 Dynamic Programming 2. Max number of trees created from n labeled nodes = nn−2
3. Spanning Tree
1. The Method
2. Longest Common Subsequence (a) To convert a complete graph to MST remove e − n + 1 edges.
3. Multistage Graphs (b) A complete graph has maximum number of MSTs = nn−2
4. All Pairs Shortest Paths 4. Binary Tree (height h)
5. Optimal Binary Search Trees
2n C
(a) Binary tree created from n labeled nodes = n! · n+1 n

6. 0/1-Knapsack Problem 2n C
(b) Binary tree created from n unlabeled nodes = n+1n
7. The Traveling Salesperson Problem (c) Height h = log n
(d) Max number of nodes = 2h+1 − 1
1.2.6 Backtracking (e) Min number of nodes = 2h
1. The Method (f) Max number of nodes at ith height/level = 2i
2. The 8-Queen Problem (g) Max distance between two nodes = 2 log n
3. Sum of Subsets
5. AVL Tree
4. Graph Coloring
5. Hamiltonian Cycles (a) Max number of nodes = 2h+1 − 1
6. Knapsack Problem (b) Min number of nodes = f (h + 2) − 1
(c) Max height = 1.44 × log n
1.2.7 Branch-and-Bound 6. 2-3 Tree
h+1
1. The Method (a) Max number of nodes = 3 2 −1
2. 0/1-Knapsack Problem (b) Min number of nodes = 2h+1 − 1
 (c) Max number of keys = 3h+1 − 1
(d) Min number of keys = 2h+1 − 1
(e) Max height = log3 n
(f) Min height = log n
7. 2-3-4 Tree
h+1
(a) Max number of nodes = 4 3 −1
(b) Min number of nodes = 2h+1 − 1
(c) Max number of keys = 4h+1 − 1
(d) Min number of keys = 2h+1 − 1
(e) Max height = log4 n
(f) Min height = log n
8. Red-black Tree
(a) Max number of nodes = 22h − 1
(b) Min number of nodes = 2h+1 − 1
9. B Tree (order m)
h+1
(a) Max number of nodes = mm−1−1
2(d m eh −1)
(b) Min number of nodes = dm
2
e−1
+1
2
(c) Max number of keys = m h+1
−1
(d) Min number of keys = 2d m2 eh − 1
10. Heap (total nodes n)
(a) Max number of nodes at hth level = d 2h+1
n
e