All problems in computer science can be solved by another level of indirection.
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)
- 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))
API(cross indicates Singly Linked List complexities)
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 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)
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.
- 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
- 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
- Inorder Traversal, Recursive creation of balanced BST using middle split technique
- Insert every element in AVL tree
- DSW algorithm= O(n) and in place
Measure of balance of a tree= Heights of subtrees
AVL Property = abs(Height of left subtree – Height of right subtree) <= 1
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)
Put commonly searched for nodes near root.
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)
Naive implementations= Linked List and Array offer O(n) run times for insertion and extraction.
Implemented using Max Heap.
- 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