## All problems in computer science can be solved by another level of indirection.

# Amortized Analysis

Collective cost sum may be less than individual worst case cost.

Average cost of an operation.

**Aggregate Method Amortized cost= ***(Cost of n operations) / n*

**Banker’s Method Amortized Cost= **Set tokens cost for each operation, insert & move. Spend tokens to pay for each operation. Example-

3 tokens for each operation in dynamic array: One for insert, one on element after inserting, one on element at [capacity/2].

O(3) = O(1) cost

**Physicist’s Method Amortized Cost= **Assign a potential function to state of data structure. This defines a potential energy which changes at every state change.

- Potential energy at base case = 0
- Potential can never be negative

**Amortized cost** = Constant cost + Potential(current state) – Potential(previous state)

# Arrays

- Constant time access elements, linear time manipulations except ends
- Address calculation: array_base + (element_size) *
**((fin_row – init_row) * (row_length) + (fin_col – init_col))**

# Linked Lists

### API(cross indicates Singly Linked List complexities)

# Stack

Stack is FIFO structure.

**API- Push, Pop, Peak, Empty**

Stack can be implemented using Linked Lists or Arrays.

- Implement a dynamic stack(vector growth principles)

# Queue

Queue is a FIFO structure.

**API- Enqueue, Dequeue, Empty
**

Queues can be implemented in the following ways:

- Using a Singly/Doubly Linked List
- Using an array(Fixed size queue)

# Tree

Used to represent data in hierarchy.

- In a valid tree, N nodes= N-1 edges.
- Every node has only one incoming edge(except root).
- Height of node= No of edges in longest path from node to leaf
- Height of tree= Height of root node
- Measured from bottom
- Height of empty tree= -1
- Height of leaf node= 0

- Depth of node= No of edges in path from root to node(root lies at depth 0)
- Measured from top

**API- Root, Node, Leaf, Child, Parent, Descendant, Ancestor, Sibling, Interior Node, Level, Height, Depth, Forest.**

# Binary Tree

**Strict/Proper Binary Tree=**Every node can have only 0 or 2 children**Complete Binary Tree=**All levels are completely filled, except possibly last levels. The last levels are as left as possible.- Height=
*floor(log n)*

- Height=
**Perfect Binary Tree=**Complete Binary Tree in which all levels are completely filled.- Number of nodes=
*(2^(h+1)) – 1 = (2^levels) -1* - Height for n nodes=
*log(n+1) – 1*

- Number of nodes=
**Balanced Binary Tree=**Difference between height of left and right subtree for every node is not more than K (given), usually 1**Maximum number of nodes at level i=***(2^i)***Implementing Binary Tree**- Linked List
- Array=
**Heap**

# Binary Search Tree

Binary tree in which every left value of all nodes in left subtree is lesser, and value in all nodes of right subtree is greater or equal.

**Traversal: BFS(**Queue),**DFS (**Pre order, in order, Post order)- In order traversal of BST = Sorted List
- BST are extremely useful to store sorted list of elements

### Balancing BST

- Inorder Traversal, Recursive creation of balanced BST using middle split technique
- Insert every element in AVL tree
- DSW algorithm= O(n) and in place

# AVL Tree

**Measure of balance of a tree**= Heights of subtrees

**AVL Property = ***abs (Height of left subtree – Height of right subtree) <= 1*

**AVL Theorem**

* Let N be a node of an AVL tree. Let h be the height of this tree. Then each subtree of N has at least the height Fibonacci(h)!*

**API= ***Insert(value), Delete(value), Merge(Tree), Split(key)*

# Splay Tree

*Put commonly searched for nodes near root.*

# Heap

**Binary Max Heap**= Binary tree where the value of a node is at least the value of all it’s children.

**Binary Min Heap= **Binary tree where value of a node is less than or equal the value of all its children

- Implemented using
**Complete Binary Trees**(low height, representable in form of arrays).- Parent=
*floor( i – 1/2 )* - Left child index=
*2i+1* - Right child index=
*2i+2*

- Parent=

**Heap Sort= **Generalization of Selection Sort Algorithm

**Turn array into Heap**= Sift down top half elements

**API= ***GetMax(), Insert(int) , SiftUp(Node ) , SiftDown(Node) , Node* ExtractMax(), ChangePriority(Node*) , Remove(int)*

# Priority Queue

Naive implementations= Linked List and Array offer O(n) run times for* insertion* and *extraction.
*Implemented using

**Max Heap.**

# TODO

- Implement MinHeap, MaxHeap, Priority Queue, AVL Tree, merge, split
- Assignment, Week 3
- Implement all basic operations for BST in lectures, especially delete
- JULY17 Priority Queue question