MikeChen's Blog

Graph Definition of a graph A graph is a set of nodes, or vertices, connected by edges. Graphs can be undirected - edges don’t have direction directed - edges have direction Undirected graphs can be represented as directed graphs where for each edge (X,Y) there is a corresponding edge (Y,X) . Graphs can also be unweighted weighted - edges have weights Notation Set V of vertices (nodes) Set E of edges (E⊂V*V) Node B is adjacent to A if there is an edge from A to B.(A —–>B) Paths and reachability A path from A to B is a sequence of vertices A1,…,An such that there is an edge from A to A1, from A1 to A2,… from An to B Vertex B is reachable from A if there is a path from A to B Other Terminology A cycle is a path from a vertex to itself Graph is acyclic if it does not have cycles Graph is connected if there is a path between every pair of vertices Graph is strongly connected if there is a path in both directions between every pair of vertices how t...

Useful definitions Prefix: a string w is a prefix of a string x, denoted w ⊏ x e.g., ab ⊏ abcca Suffix: a string w is a suffix of a string x, denoted w ⊐ x e.g., cca ⊐ abcca the empty string ε is both a prefix and a suffix of every string Automata-based matching The brute force approach used by NaiveStringMatch is simple, but not very efficient, when a match fails, it simply increments the shift and tries again, however in some cases, the next shift can’t possibly be valid, given what we know about the pattern and the text character that failed to match. One way of encoding the structure of the pattern is by using an automaton that scans T for an occurrence of P The automaton examines each character in the text exactly once, giving a worst case matching time of O(n) However, automata-based matching algorithms require a pre-processing step to build the automaton from the pattern Suffix function for a pattern Before, we get into this automata-based matching method...

Definition of string matching problem informal: given a text(sequence of characters) T of length n, and a pattern P(sequence of characters) of length m, determine if P occurs in T Naive string matching algorithm NaiveStringMatch(T, P) for(s = 0; s < T.length - P.length; s++) j = 1; while(T[s+j] == P[j] and j <= P.length) j++; if(j == P.length+1) return s; return -1; note that the array started at index 1 instead of 0 note that s is a shift(not an array index) and so counts from 0 not 1 note also that if T.length < P.length, the for loop is skipped, and we return -1 immediately Naive algorithm NaiveStringMatch moves the pattern along the text string, until it finds a shift(offset) for which the characters in the pattern are equal to the characters in the next The for loop considers each possible shift explicitly, start with a 0 shift The while loop and conditional determines whether the current shift i...

Binary Search Tree Motivation Why we need BST? We learned binary search before, if we search for an element within a sorted array is fast. The search will be in O(logn), but arrays suffer from being slow, O(n), to insert new elements . So we need a search trees attempt to fix the inefficiency of insertion whilst keeping good O(log n) properties for search. A binary search tree is a binary tree storing key-value entries at its internal nodes and satisfying the following “search tree” property: let u, v and w be any three nodes such that u is in the left subtree of v and w is in the right subtree of v. Then we must have key(u)<= key(v) <= key(w) Now we are going to implement the binary search tree. Similar to the previous implementation, when we want to implement a tree-structure, what we should do first is to define Node in tree. Search Search for a BST is relatively easy, we have learned binary search before, so we use the similar style. To search for...

HashTables Hash tables are a concrete data structure which is suitable for implementing maps. Basic idea: convert each key into an index in a big array Lookup of keys and insertion and deletion in a hash table usually runs in O(1) time Hash Function and Hash tables A hash function h maps keys of a given type to integers in a fixed interval [0, N-1] The integer h(k) is called the hash value of key k Example of hash function: h(k) = k mod N A hash table for a given key type consists of Hash function h Array (called table) of size N When implementing a map with a hash table, the goal is to store them (k,v) at index i = h(k) Collision handling Collisions occur when different elements are mapped to the same cell. A lot of the theory and practice of hashing consists of devising better ways to avoid or handle collisions. Hash functions A hash function is usually specified as the composition of two functions: Hash code: h1: keys->integers java: key.hashCode() Co...

ADT: Maps A map models a collection of key-value entries that is searchable ‘by the key’. Multiple entries with the same key are not allowed. Map ADT over Key and Value The difference between Map and Priority Queue Both insert entries based on a key but: Map: can access any key using “get(K k)” PQ: access only the minimum key using “RemoveMin()” Implement Map We can implement a map using an doubly-linked list. Every Node in the linked list is a K,V pair. So first, we need to implement doubly-linked list What we have in doubly linked list? We need a new class node to represent every element We also need a header and a trailer, header is previous to the first node and trailer is after the last node Because it is a doubly linked list, the node should linked with previous node and next node Ok, let’s started to build doublylinked list Here, we define the bullet point above, then we need to specify the operations. So what operations to perf...

Priority Queue and Heap A priority queue stores a collection of entries Each entry is a pair (key, value) A heap is a binary tree storing key-value pairs at its nodes and satisfying the following properties: Heap-Order : for every internal node v other than the root key(v) >= key(parent(v)) It is a complete binary tree Motivation We have three ways to implement priority queue unsorted list (O(1) for insert but O(n) for removeMin() and min()) sorted list (O(n) for insert but O(1) for removeMin()) Heap(Explain later) We want to find a data structure which can optimize priority queue operation to be better than O(n). Then, we find heap, which gives us O(logn) due to the usage of binary tree. The difference between priority queue and Maps(HashMaps)? Both have key and values. Two distinct entries in a priority queue can have the same key. But in hashmap, the key should be different. Is it a reason why PQ doesnt have find(key)? Why? It is because in pr...

Amortized analysis Why talking about amortized analysis When we are learning “Vector” in ACE class, we came up with a growable array-based vector. We want to know what if we execute “push” operation, but the array is full. Instead of throwing a exception, we would like to replace the array with a larger one Algorithm push(o) if t = s.length -1 then A <- new array of size ... for i <- 0 to t do A[i] <- S[i] t <- t+1 A[t+1] <- o garbage collection S From pseudo-code above, what should be the size of the new array? There are two simple strategy you can came up with quickly • incremental strategy: increase size by a constant c • doubling strategy: double the size What is the common analysis for this question? Suppose some individual operation (such as ‘push’) takes time T in the worst-case. So for the total s operations, the worst-case time should be sT(upper bound) • however, such an upper-bound might not ever occur. Because the...

Recurrence Relation Acknowledgement The following content is summarized by G52ACE class and MIT open source course(Introduction to Algorithms). Main Body We don’t care the official definition of recurrence relation, but we need to know: Suppose that the runtime of a program is T(n), then a recurrence relation will express T(n) in terms of its values at other (smaller) values of n. Example: Suppose the runtime of merge-sort of an array of n integers is T(n). Then T(n) = 2 T(n/2) + b + a n: • “2 T(n/2)” is due to having to sort the two sub-arrays each of size n/2 • “b” is the cost of doing the split • “a n” is the cost of doing the merge (and any copying to/from the workspace, etc.) Also, what is our base case? ===> T(1) = 1 Thus, how can we solve this recurrence relation? Solving Recurrence using induction(introduced by G52ACE course) General pattern 1. Starting from the base case, use the recurrence to work out many cases, by directly substituting and working u...