Data Science PT 9: Data structures

 

We will briefly review arrays, data structures, linked lists, queues, sets, and stacks here. We want to organize data/memory/objects fairly. We want fast access/updates and and fast searches. We want to support dynamic sets. We can insert, delete, or check membership. If we want more refined data structures if we want more operators. Data structures need to support data arranged in objects that contain fields.

The key is the field that identifies objects. Other fields contain attributes of the object. Some common operators are 

Search(S,k), which searches for object with key k in set S

Insert(S,x), which inserts an object 

Delete(S,x), which reassigns the pointer

Minimum(S), which returns the smallest key

Maximum(S), which returns the largest key. 

Successor(S,x) (nil if last) shows the next object in structures while the Predecessor(S,x) (nil if first)shows the previous object in the structure.

A Stack is LIFO (last in last out) and we can push (insert) or pop (delete) elements from the stack. An example is showing the latest routine details of an operating system when popping. 

A Queue is FIFO (First in first out) which removes first element that is inserted. We can enqueue (insert) and delete (dequeue). an application is customers waiting for order to be processed, we serve the earlier customers first. 

We can implement stacks as an array which is simple but might cause overflow and we must store the Top(S). The operations are Stack_empty(S), Stack_full(S), Push(S,x), and Pop(S).

To implement as Queue, we can implement as array and store a Head and Tail variable. The elements in the Queue are Head(Q), Head(Q)+1, …, Tail(Q)-1. The Indexing is modulo-n. If the queue is empty the Head is equivalent to the Tail. If the Queue is full the Tail + 1 is equal to the Head. 

Linked Lists will arrange objects in linear order. It's hard to implement Linked Lists as an array because it's difficult to add an object "in the middle", so we can use pointers instead. It's easy to insert/delete objects by simply updating the pointers. In a doubly linked list, each object contains key and pointers to the next and previous box. 

List_search(L,k) Search for key k in list with O(n) complexity, not Θ(n). List_insert(L,x) [Θ(1)] adds new object to head of list. List_delete(L,x) splices off data structure and sets next pointer. 

Skip lists utilizes an "express lane" to perform faster searches throughout the data structures. We have an express lane that can skip parts of the linked lists, to make it faster to search for values. This list needs to be sorted. 

Skipping Ke normal objects in an express lane and Ks express objects in a "super" express lane we can determine the total computation time as follows: 

To minimize f(K) we compute the derivative of f(K) with respect to K and set it to 0. 

A graph is a Structure relating different objects, defined as G(V, E) with Vertices V and Edges E. It can either be a directed or undirected graph. 

The edges are arrows in the directed graph. If there is a edge  (u,v)∈E, we can say the v is adjacent to u. The degree is the number of edges connecting with vertex V. We have  edges (v0,v1), (v1,v2),…, (vk-1,vk). We can define path p as as v0=u, vk=u’, (vi-1,vi )∈E, where i∈{1,…,k} to go from v0 to vk. U’ is reachable from u using path p. This is definition of a graph. An example is (D,E) and (E,A). 

A simple path is where all vertices on path are distinct, where a cycle is where the path starts and end on the same vertex ((a,c), (c,a) in the bottom diagram). A acyclic graph is a graph without cycles.

In an undirected graph, a connected component is where all nodes reachable from one another. Connected components partition V into equivalent classes. A connected graph is one large connected component. 

In directed graphs, strongly connected graphs are where all nodes are reachable from one another. A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. Here's an example: 

A bipartite graph can be partitioned into V1, V2. (u,v)∈E implies:

1.Either u∈V1 & v∈V2 

Or 

2. v∈V1 & u∈V2

An application is Y=Xβ+ε (which is linear regression) where V1 corresponds to Y and V2 corresponds to β. The matrix corresponds to edges E and we can estimate β by passing the messages from V1 to V2.

 

The next topic is on trees. A forest is an acyclic undirected graph. A tree is a connected forest. A forest is a union of trees. 

Acyclic graphs are efficient due to lack of redundancy, but suffer in terms of protection and robustness because there is no connectivity if an edge breaks. Any v1,v2∈V is connected by unique simple (no cycles) path. Removing any edge from a tree will cause a disconnect. G is connected and acyclic and |E|=|V|-1. Adding any edge creates a cycle. 

There is no concept of from/to in a free tree, whereas in a rooted tree one node is a root, and the paths leave from the root to other nodes. Path from root r to node x is always unique. In the graph above node 10 is a descendent of node 8. Subtree is the descendants so the subtree of 3 is {3, 1, 6, 4, 7}. The depth (x) is the length of path from the root r to x, and Height(T) is the maximal depth of all of the nodes. All nodes except r have single parent. A leaf is a node without children, for example {1, 4, 7, 13}. Internal nodes are not leaves.  

To implement a tree, there is always a pointer to root, and each node contains pointers to the parent, the children, and the sibling nodes.

Now talking about profiling. Profiling is a dynamic program analysis that measures, the complexity of a program, the instruction usage, or the frequency/duration of function calls. You can profile easily by using the profreport command in Matlab. The following is an example of a typical profiling report. 

We will look through lines with substantial running time, figure out why it took so long, and redesign as needed. We usually will look through lines with >= 10% runtime. Repeat with 5% runtime.