CS2420 Notes PDF

Preview

Summary

Download CS2420 Notes PDF

Description

1/11/16 What is an algorithm?  In mathematics and computer science, an algorithm is a step-by-step procedure for calculations  Computational procedure that takes some values as input and produces some values as output. Sequence of computational steps that transform the input into the output. What is a data structure?  A data structure is a particular way of storing and organizing data in computers so that it can facilitate certain operations efficiently  A way to conserve time and space  Designing data structures as an independent problem  Designing data structures for an algorithm About this course  Important o Fundamental knowledge for designing algorithms

Algorithm Analysis How do you know whether or not it’s good/efficient? Insertion Sort Input: A[0 …. n-1] of size n Output: a sorted array A in ascending order Example: [34,8,64,51,32,21] Output: [8,21,32,34,51,84] 1/13/16 – Algorithm Analysis How do we evaluate whether an algorithm is good/efficient?  Resources consumed by the algorithm o Time o Space/Memory  How do we know how much time/space an algorithm uses? o Algorithm analysis

Pseudo code for insertion sort for i = 1 to n-1 temp = A[i]; j = i-1; while (j>= 0 and temp > A[i]) A[j+1] = A[j]; j--; a[j+1] = temp; How do we measure the running time of the insertion sort?  Depends on input size o n = 6, n = 6,000,000  Depends on input pattern o Best case: input is already sorted ascending  Only compare with one number o Worst case: input is already sorted descending  You compare with every number o Average case: difficult to define.  Depends on the machines o Super computers vs. PC Our Solutions  Define a time function T(n) of the input size n o example T(n) = 3n^2 + 5n +23  Only consider the worst case o Provide a guarantee o Best case is meaningless  The best case is already sorted, so why use a sorting algorithm o Average case is difficult to define; in most problems, the average case is the worst case  Use the RAM (random access machine) as the computing model: certain primitive operations take constant time each. Time c for a fixed value c. o Arithmetic operations: +,-,*,/  Assume that they all take the same time o Data movements: =, load, copy  Assume they take a constant time o Comparisons: > < ==  Assume they take a constant time  Summary: Use a function T(n) of input size n to describe the running time of the algorithm in the worst case under the RAM model Rules for writing algorithms  Remove the low-order terms  Ignore the leading constant

Exercises for algorithm analysis  If you have a for loop and a while loop, the order is O(n^2) o Not necessarily  With one for loop, O(n) 1/15/2016 This is Order constant Input: A[0...n-1] For(i=0;inext;





return p; } Insert(x) o Insert a new value x into the sorted list o Idea: scan the list from head, find the first number larger than x, and insert x in front of that number o Time for each operation: O(n) P ->next->value > value(x) q ->next = p->next; p->next = q; Insert(x) o Insert a new value x into the sorted list o Time for each operation : O(n) Void insert(ListNode * Head, int x) { ListNode * q = new ListNode(x); If head = null or head -> value > x { q -> next = head; head = q; } else ListNode * p = head; While (p->next != null and p->next->value < x) {both have to be true to keep going} P = p->next; q->next = p->next; p->next = q;



Remove(x) o Remove the new value x from the sorted list o Idea: scan the list from the head, find x, and remove it o Time for each operation: O(n) p->next = q->next



Reverse() o Reverse the list o Idea: scan the list from head, for each node, move it to the front of the list o Time for the operation: O(n)

Doubly Linked list Struct ListNode { int value; ListNode * next, * prev; }; Removing a value q: q- >prev -> next = q -> next; q-> next - > prev = q -> prev; Delete q; Queue  A queue is a data structure that stores and retrieves items in a first-in-first-out manner  A real life example: waiting in line  An application related to CS: jobs in printer  Queue operations: enqueue and dequeue o Enqueue: insert a new item x to the rear of Q  Enqueue(q,4); o Dequeue: remove the front item and return it  X = dequeue(Q); Implementing Queues by linked lists struct ListNode { Int value; ListNode * next; };  Maintain two pointers o Front: pointing to first node o Rear: pointing to last node Time: O(1) because you don’t need to scan the list. We already have a rear pointer Enqueue(front, rear, x) { ListNode * q= new ListNode(x); If front != null rear->next = q; rear = q; else front = q; rear = q;

Time: O(n) int dequeue(front, rear) { if front == null exit(1); else int value = front -> value; {eventually youre going to return this value} ListNode * q = front; If front != rear {at least two items in queue} front= front->next; else front = read = null; delete q; return value; Stacks  A stack is a data structure that stores and retrieves items in a last-in-first-out manner (LIFO) o Queues: first in first out  Stack operations: push, pop o Both operations happen at the top of the stack o Push(x): add a new item x on the top of the stack o Pop(): remove the top from the stack and return it o Implementation: by an array  Maintain a top index  Time for each push or pop: O(1) Size = 20; Int * A = new int [size]; Top = 0; Push(x) { if top < size A[top] = x; Top++; Else Cout 0 (not empty) top--; return a[top]; else

cout left); visit v; //cout key in-order(v-> right); The search operation  Search(root,x): given the root of the tree and a value x, return the node whose key is x; return NULL if such a node does not exist  Idea: starting from the root, for each node v in the search path o If x==v - >key, return v; o If xkey, search v->left recursively o If x>v->key, search v->right recursively o If v == NULL, return NULL;  Time: O( n) (worst case)  Implement it in both a recursive way and an iterative way  Time: O(h) where he is the height of the tree, more accurate Recursively bool Search( TreeNode * v, int x) { if v == NULL return false; if x = v->key return true; if x < v->key return search(v->left, x); else x> v->key return search(v->right, x); }

Iteratively bool search(root, x) { TreeNode * v = root; while (v!=NULL) { if x = v->key; return true; if x < v->key v= v->left; else x > v->key v = v->right; } return false; } Min and Max: O(h) findMin(root)  Find the smallest key in the tree o Starting from the root, always follow the left child FindMax(root)  Starting from the root, always follow the right child  Find the largest key in the tree Insertion  Insert(x): insert a node to T with key x  Algorithm: proceed down the tree as you would in a search operation If x is found Do nothing; Else Insert a new node Insert implementations  The iterative way  The recursive way

Iteratively

Void insert(root, x) { if root == NULL root = new TreeNode(x); return; TreeNode * v = root; while (x != v->key) { if x < v->key if v->left != NULL v= v->left; else v->left = new TreeNode(x); return; if x > v->key SAME AS OTHER SIDE } return false; } Recursively Void insert(TreeNode * v, int x) { if v == NULL // if the root is empty v = new TreeNode(x); return; if x == v->key return; // do nothing if x < v->key if v->left == NULL // create a link to the new node v->left = new TreeNode(x); else insert(v->left, x); // otherwise you keep traveling down the tree else x> v->key if v->right == NULL v->right = new TreeNode(x); else insert(v->right, x); } OR Recursively

Void insert(TreeNode * &v, int x) // need to pass by reference { if v == NULL // if the root is empty v = new TreeNode(x); return; if x == v->key return; // do nothing if x < v->key insert(v->left, x); else x> v->key insert(v->right, x); } Remove/Delete  Remove(x): given a value x, remove the node whose key is x from the tree; if x is not in the tree T, do nothing  Algorithm idea: o Search x in T  If x is not found, do nothing  If x is found at node v  Depending on the number of children v has, there are three cases Remove: three cases  V is a leaf o Remove v immediately  V has only one child o Replace v by v’s only child  V has two children o Find the smallest node u in the right subtree of v  U does not have a left child o Replace v by u o Remove u (recursively)

Void remove(TreeNode * &V, int x)

{ if v == NULL {return;} if x < v->key remove(v->left, x); if x > v->key remove(v->right, x); if x == v->key{ // have the node and now you’re moving into the tree cases if(v->left == NULL && v->right == NULL){ delete v; (or return) if(v->left ==NULL ){ // creating a link, and using a temp variable to store v Tree Node * temp = v; V = v->right; Delete temp; If(v->right == NULL){ TreeNode * temp = v; V = v->left; Delete temp; If(v->left != NULL && v->right != NULL){ TreeNode * u = v->right; While(u->left != NULL) { U = u->left;} v->key = u->key; remove(u, u->key); // where u is also v->right Remove: implementation  Using recursion with reference is the easiest way  Time: O(h)

Pointers: Int *p; Int a =5; P = &a; (this is taking the address of a and assigning it to p) Cout left; K2_>left = k1 ->right; K1->right = K2; K2->HEIGHT = 1 + max;

void right rotate (AVLNode * &v) {

Removals

Hash Tables An exercise on designing data structures Given a sequence of numbers A=5,4,6,10,20 design a data structure to support the following operations:  Search(x) o Return A[x];  Insert(x) o A[x] = 1;  Delete(x) o A[x] = 0; Best solution: AVL trees A new assumption:  Every element of A is from a set U={0,1,2….n-1} of integers o U is called the universe and n is a fixed integer Direct Address  Key idea: use x as the index of T (where T is an array)  Issue: N may be too big  Solution: use a hash function Notation  A hash table is essentially an array  T[0,…m-1]: the hash table  m: the size of the has table  n: the total number of elements in T  x: a key  hash(x): the hash function o the item with key x hashes to T[hash(x)] o hash(x) = x%m  the new issue: collisions o two keys x and y with x != y but hash(x) = hash(y) o x and y hashes to the same slot/cell of T Resolving Collisions  separate chaining o idea: place all the elements that hash to the same slot of T into a linked list  T is still an array, but each element of T is a pointer variable that points to the head of the linked list (or to a node)

Implementation: Static: element * T[10]; Each element is a pointer variable Dynamic: Int m = 10; Element * T = new Element[m]; //Here, each element is of type element so each T[i] is just an integer type and not a pointer variable int m = 10; element ** T = new Element *[m]; // here, each element is now a pointer Initialization: For I = 0 to m-1 T[i] = NULL; Search(x):  Find the element whose key is x in the hash table T  Idea: find the correct slot and then traverse the list to search  Time: linear in the length of the list Bool search(int x) { Element *p = T[hash(x)]; While(p!= NULL and p->key != x){ P = p->next; If( p == NULL) {return false;} Else {return true;} Insert(x):  Insert a new element x into the hash table T  Idea; find the correct slot of T and insert x in the front of the list  Time: O(1)  Void insert(int x) { element * p = T[hash(x)]l element *q = new element(x); q - >next = p; T[hash(x)] = q;

2/26/16

Search int search(x) { //initial slot where I = 0 int I = 0; //iright->height)| 1 and H[i] < H[parent(i)] ){ Swap H[i] with H[parent(i)]; I = parent(i);

Fibonacci Heap: decreaseKey:O(1) Soring Algorithms...