# Basic Algorithms

Some basic algorithms for coding interviews. Codes here are written in Python-style pseudocode. Actual tested codes will be put on my GitHub Repo.

### Sorting

• Insertion sort
• Alg:
Assume the head of the array is sorted. For each element afterwards, insert it to the corresponding proper location in the sorted head.
• Time: $O(n^2)$ average, $O(n^2)$ worst, $O(n)$ best
• Bubble sort
• Alg: Repeat (for at most n times). For each pass, traverse the array to check if it is sorted (a.k.a: A[i]<=A[i+1]). If not, swap the locations of A[i] and A[i+1]. Then increment i. Repeat until no swap is needed in a traversal.
• Time: $O(n^2)$ average, $O(n^2)$ worst, $O(n)$ best.
• Alg: If A[i] is M, then place it at the $M^{th}$ bucket. Traverse through the buckets to get all numbers in place
• Time: O(M)
• Space: O(M)
• Merge sort
• Alg: Divide the array recursively into two subarrays. Merge them together to replace the original one.
• Time: $O(n log(n))$ average, $O(n log(n))$ worst, $O(n log(n))$ best.
• Quick sort
• Alg: Divide and rearrange the array into two subarrays so that everything in the left subarray <= pivot <= everything in the right subarray. Now the location of pivot is decided. Apply the aforementioned procedure to each of its subarrays.
• Time: $O(n log(n))$ average, $O(n^2)$ best, $O(n log(n))$ best.
• Heap sort
Alg: construct a heap (O(n)). Repeatedly extract the root to append to the sorted array (O(n log(n))).

• Insertion / Deletion: O(1) time
• Implementation
• Stack
• Property: LIFO
• Implementation in Python: Using list.pop(), list.append(x)
• Queue
• Property: FIFO
• Implementation in Python: Use del(list[i]), list.insert()
• Hash Table
• Property: Constant Query time
• Libraries available: Python dictionary, Java Map.
• Tree
Following descriptions for tree traversal are for binary trees; they can be generalized to other trees.

• Level-order traversal
• Iterative:
Dequeue an element, enqueue left kid, enqueue right kid, repeat until queue is empty.
• Pre-order traversal

• Recursive
• Iterative
Pop and print current, push right, push left. Repeat until Stack is empty.
• In-order traversal

• Recursive
• Iterative
(1) Init Stack and set current to root
(2) While current is not null, push current and current=current.left
(3) If current is Null, then:
Current = pop(), print current, current=current.right, then go to (2)
(4) If current is Null and stack is empty, finish.
• Post-order traversal

• Recursive
• Iterative
(1) Init two stacks, s1 and s2. Push root to s1.
(2) While s1 is not empty:
Pop n from s1, and push to s2.
Push to s1 n.left;
Push to s1 n.right;
(3) After s1 is empty, pop s2.
• Graph
• Representation: a set of Edge, and a set of Vertices (Nodes).

### Special Trees

• Heap
• Peek
• Insert. O(log(n))
• RetrieveMax. O(log(n))
• Heapsort. O(nlog(n))
• Heap and priority queue
• Binary Searching Tree

• Peek
• Insert. O(log(n))
• Delete(k).
• AVL tree

• Balance Factor of a node is height of right - height of left child tree.
• An AVL invariant tree has Balance Factor between [-1, 1] for all nodes.
• An AVL tree is an AVL invariant BST.
• To insert an element to an AVL within O(h):
• Red-black tree
• Trie

### Graphical Algorithms

• Iterative solution
For each node dequeueâ€™d, push left child to queue, push right child to queue. Repeat until the queue is empty.
• Notes:
(1) BFS does not visit an edge twice.
(2) In a unit length edged graph, if node u is visited before v, then d(s,u)<=d(s,v) where d denotes the shortest distance and s is the source node.
(3) The time and space complexity of BFS are both O(|V|+|E|).
• Depth-first Search (DFS)
• Recursive
• Iterative
Initialize a stack. For each visiting node, push all unvisited neighbours to a stack. Pop() from the stack to visit a node.
(1) In CLRS the DFS starts from all nodes, where here DFS only traverses from one.
(2) DFS does not visit an edge twice.
(3) The time and space complexity of DFS are both O(|V|+|E|). However, if you are DFS-ing a tree with branch factor b and depth k, the time complexity is still $O(b^k)$, but the space complexity is $O(bk)$.
• Shortest Path: Dijkstra
Alg:
(1) Initialization: set dist of all vertices to $\infty$. Mark all nodes unvisited.
(2) Start from the initial node. Set dist[start]=0:
Pick the unvisited node with least dist as u
Update all neighbours of u:
For v in u.neighbours:
v.dist = min(v.dist, u.dist + W(u,v))

Then remove u from the unvisited set.
(3) Stop when the destination node is visited, or when u has infinity distance.
• Proof of correctness: proof of greedy algorithm.
• Time complexity: O(|E| + |V|log|V|)
• Shortest path with negative weighted edge: Bellman-Ford

• All-source shortest Path: Floyd-Warshall

• All-pair shortest paths with negative weight circle: Johnson

### Network Flow Algorithms

• Flow Network Definitions

• Finding maximum flow: Ford-Fulkerson

• Improved maximum flow: Edmond-Karp

• Faster maximum flow: Push-relabel

• Applications of network flow: bipartite matching

### Linear Programming

• Definitions

• Simplex Algorithm

### Complexity Theory

• Definitions: CNF, P, NP

• Definitions: NPC