MikeChen's Blog

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

Reference A way to give a new name to an item look like normal variables act like pointers The need for references Useful if we need to keep the same syntax(but avoiding making a copy) Useful as return values, to chain functions together(especially returning *this from member functions to return reference to current object) References are necessary for operator overloading(changing the meaning of operators) warning Similar problems with references as with pointers e.g. do not return a reference to a local variable When the local variable vanishes (e.g. the function ends), the reference refers to something that doesn’t exist. new and delete new vs malloc new knows how big the object is: no call to sizeof() is needed ( unlike malloc() ) new creates an object ( and returns a pointer): allocates memory (probably in same way as malloc() ) new knows how to create the object in memory: c++ objects can consists of more than the visible data members new calls th...

Classes vs structs classes and structs are (almost) the same thing in C++; The difference is only in encapsulation struct defaults to public, class to private If there is only data and no member functions in the code, we use a struct; if you add member functions then use a class. Data and methods in a class have either public or private access. public methods and data can be accessed by anything, like non-static global functions/data in a file. private methods and data can only be accessed by other members of the same class class members default to private access struct members default to public access inheritance To use inheritance, we use the class subclass : public superclass{}; As we can see in the above code, member functions can access the data in classes or structs using this-> not this. . In every getter function, there is a keyword “const” , means access only, no changes. Also you might be curious about how the constructor works. Construct...

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

Are there non-regular languages? The regular languages are those that can be recognized by finite automata; i.e. machines with finite memory. Are there languages that are not regular? Yes! One example: So, how can we tell if a language is regular or not? We use pumping lemma to tell! Pumping lemma Formal statement Let L be a regular language, then there exists an integer n >= 1 depending only on L such that every string w in L of length at least n (n is called the “pumping length”) can be written as w = xyz , satisfying the following conditions: 1. |y| >= 1; 2. |xy| <= n 3. for all k >=0, x y^k z ∈ L what does y mean? y is the substring that can be pumped(removed or repeated any number of times, and the resulting string is always in L) 1. means the loop y to be pumped must be of length at least one. 2. means the loop must occur within the first n characters(|x| must be smaller than n) Below is a formal expression of the pumping lemma: Use of th...

We have covered these topics again and agin in “Expressions” and “Variables” but after the class today, i am willing to share some more useful knowledge and interesting examples with you. Process structure in memory Stack Function calls ( stack frames ) are stored on a stack in memory. Note that most stacks go down in memory addresses, i.e. the stack frame for the new function is lower in memory stack frame when a function call is made, necessary information is collected together Who called the function? So the program knows where to return to when the function ends. What parameters were supplied? Space to put the return value? Somewhere to store local variables while they are needed All these values are stored together in a ‘stack frame’ Lifetime of local variables The local variables for function 2 and function 3 are overwritten by those for function 4 The local variables for function 4 are overwritten by those for function 5 Your local variables only exist fo...

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

Regular Expressions Overview Automata(DFA and NFA) describe languages in a somewhat indirect way: not always obvious what the defined language is. But Regular Expression offer a different, more direct way to describe language. Regular expressions offer something that automata do not: a declarative way to express the strings we want to accept. Thus, regular expressions serve as the input language for many systems that process strings: Search commands such as the UNIX grep Lexical-analyzer generators(Compilers) The operator of regular expressions Regular expressions denote languages. For a simple example, the regular expression 01*+10* denotes the language consisting of all strings that are either a single 0 followed by any number of 1’s or a single 1 followed by any number of 0’s. Before describing the regular expression notation, we need to learn the three operations on languages that the operators of regular expressions represent. These operations are: The un...

It is a surprising fact that every language that can be described by some NFA can also be described by some DFA. Moreover, the DFA has more states than NFA. The smallest DFA can have 2^n states while the smallest NFA for the same language has only n states. We can thus convert an NFA into a DFA by considering each possible set of NFA states as a single DFA state! subset construction The subset construction starts from an NFA N = (Qn, Σ, δn, q0, Fn). Its goal is the description of a DFA D = (Qd, Σ, δd, {q0}, Fd} such that L(D) = L(N). where δD(A)(P,x) = U{δ(q,x) | q ∈ P} FD(A) = {P∈P(Q)|P∩F≠∅} It might be confused if we just say its definition, i’ll show how the NFA converted to DFA. Example The language is same as before–accpets all strings that end in “01” We have figured out its NFA: So first, we want to write a complete subset construction of it. So how many possible states are there in the DFA? 2^3 = 8 states, we use a transition table and write down all ...

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