# 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.

1. Potential energy at base case = 0
2. Potential can never be negative

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

# Arrays

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

### 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.

1. 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:

1. Using a Singly/Doubly Linked List
2. 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)
• 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
• 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
• 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

1. Inorder Traversal, Recursive creation of balanced BST using middle split technique
2. Insert every element in AVL tree
3. 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

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