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))

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