Algorithms & Data Structures - Introduction

When we devise an algorithm, we should be able to do the following three:

1. Identify what we're trying to achieve - formalize
2. We need to analyze it's correctness.
3. Also, we have to analyze it's efficiency (time, memory usage, power consumption).

Here is a very simple code. Can you guess what it's doing?

#include <iostream>

int what(int a, int b)
{
	int x = a,  y = b, z = 0;
	while (x > 0) {
		z = z + y;
		x = x - 1;
	}
	return z;
}

int main() {
	std::cout << what(10, 2) << std::endl;
	return 0;
}
        

The answer is what(a,b)=a*b.

1. Proof of correctness of the algorithm.
   Claim: before and after the while, ab = xy+z.
   Base case:beginning of the code - x=a, y=b, z=0, so ab = ab + 0 which is true.
   Inductive step: if ab = xy + z, then for the new values the same should be true: ab=x'y'+ z'
   Let's check the values within the while loop: x'=x-1, y'=y, z'=z+y
   Then, the claim was x'y'+z' should be equal to ab.
   x'y'+z'=(x-1)(y)+(z+y)=xy-y+z+y=xy+z
   Form the inductive step, x'y'+z' equal to ab: x'y'+z'=ab. So, if ab = xy + z, then for the new values, the same should be true: ab=x'y'+ z' is confirmed.
   ab=xy+z has been holding true since the beginning of the loop until the end of the while loop.
   We proved it's correctness!


2. How what(a,b)=a*b?
   At the beginning:
   x=0, xy+z=ab Then, xy=z becomes 0*z=z
   So, xy+z=ab=z, in other words, what(a,b) is doing multiplication, a*b.
   


3. Efficiency:
   If we increase the number, something like what(98765, 4321), how long it will take?
   Answer: it's linear, if number gets bigger, time increases accordingly.

"On the basis of the issues discussed here, I propose that members of SIGACT, and editors of computer science and mathematics journals, adopt O, Ω, and θ notations as defined above, unless a better alternative can be found reasonable soon."
-D.E. Knuth, "Big Omicron and Big Omega and Big Theta", SIGACT News, 1976. Reprinted in "Selected Papers on Analysis of Algorithms."

1. T(n) = O(f(n)) (big-oh) means that the growth rate of T(n) is asymptotically less than or equal to to the growth rate of f(n).
2. T(n) = Ω(f(n)) (Omega) means that the growth rate of T(n) is asymptotically greater than or equal to to the growth rate of f(n).
3. T(n) = θ(f(n)) (Theta) means that the growth rate of T(n) is asymptotically equal to to the growth rate of f(n).
4. So, if T(n) = n^2 + 5n, the followings are true.
   T(n) = Ω(n)
   T(n) = θ(n^2)
   T(n) = O(n^3)
   

Why data strcutures matter?

We need to organize data so that it can be accessed quickly and usefully. Examples of data structures are queues, stacks, lists, heaps, search trees, hashtables, bloom filters, union-find, etc.

Why do we have so many data structures?

That's because different data structures support different sets of operations. In other words, each of them is suitable for different types of tasks.

So, a programmer should choose the minimal data structure that supports all the operations that's needed.

1. Stacks and Queues
   Stacks and queues are dynamic sets in which the element removed from the set by delete operation.
   In a stack, the element deleted from the set is the one most recently inserted: the stack implementations a last-in, first-out or LIFO, policy.
   Similarly, in a queue, the element deleted is always the one that has been in the set for the longest time:
   the queue implements a first-in, first-out, or FIFO, policy.
   Here are examples:
   Stack with linked list data structure
   Class Stack with linked list data structure
   Generic Stack with array
   Example 8 - Queue Struct : Using Linked List
   Example 8B - Queue Class: Using Linked List
   Queue: Using Vector
   


2. Linked Lists
   A linked list is a data structure in which the objects are arranged in a linear order.
   Unlike an array, however, in which the linear order is determined by the arrays indices, the order in a linked list is determined by a pointer in each object.
   Linked lists provide a simple, flexible representation for dynamic sets, supporting several operations: search, insert, delete, minimum, maximum, successor, and predecessor.
   A list may have one of several forms.
   It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not.
   If a list is singly linked, we omit the prev pointer in each element.
   If a list is sorted, the linear order of the list corresponds to the linear order of keys stored in elements of the list; the minimum element is then the head of the list, and the maximum element is the tail.
   If the list is unsorted, the elements can appear in any order.
   In a circular list, the prev pointer of the head of the list points to the tail, and the next pointer of the tail of the list points to the head. We can think of a circular list as a ring of elements. Here is some Linked List Examples in C++.
   



3. Binary Search Trees
   The search tree data structure supports many dynamic-set operations, including search, minimum, maximum, predecessor, successor, insert, and delete.
   Thus, we can use a search tree both as a dictionary and as a priority queue.
   Basic operations on a binary search tree take time proportional to the height of the tree.
   For a complete binary tree with n nodes, such operations run in O(log n) worst-case time.
   If the tree is a linear chain of n nodes, however, the same operations take O(n) worst-case time.
   In general, the expected height of a randomly built binary search tree is O(log n), so that basic dynamic-set operations on such a tree take O(log n) time on average.
   In practice, we can't guarantee that binary search trees are built randomly, but we can design variations of binary search trees with good guaranteed worst-case performance. One such variation is red-black tree which gives us height O(log n).
   Here is some Binary Tree Examples in C++.
   



4. B-Trees
   

   From "Introduction to Algorithms" 3rd Ed., 2009.

   B-trees are balanced search trees designed to work well on disks or other direct-access secondary storage devices. B-trees are similar to red-black trees, but they are better at minimizing disk I/O operations. Many database systems use B-trees to store information.
   
   
   1. B-trees differ from red-black trees in that B-tree nodes may have many children, from a few to thousands. The branching factor of a B-tree can be quite large, although it usually depends on characteristics of the disk unit used.
   
   
   2. B-trees are similar to red-black trees in that every n-node B-tree has height of O(log n). The exact height of a B-tree can be considerably less than that of a red-black tree, however, because of its branching factor, and hence the base of the logarithm that expresses its height, can be much larger. Therefore, we can also use B-trees to implement many dynamic-set operations in time O(log n).
   
   



5. Red-Black Trees
   A Red-Black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK.
   By constraining the node colors on any simple path from the root to leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.
   Each node of the tree now contains the attributes color, key, left, right, and p.
   If a child or the parent of a node does not exist, the corresponding pointer attribute of the node contains the value NIL.
   We consider these NILs as being pointers to leaves (external nodes) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.
   A red-black tree is a binary tree that satisfies the following red-black properties:
   
   1. Every node is either red or black.
   2. The root is black.
   3. Every leaf(NIL) is black.
   4. If a node is red, then both its children are black.
   5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
   STL map is implemented using this RB-Tree.



6. AVL Trees
   An AVL tree is a BST that is height balanced: for each node x, the heights of the left and right subtrees of x differ by at most 1.



7. RB-tree vs AVL-tree
   AVL trees are always at the optimal balance point, but can slow down inserts and deletes because they are more rigidly balanced than red-black trees. But we will have the fastest look times.
   Red black trees are also self balancing but can become slightly imbalanced to improve insert and delete times, with a small potential hit to search times.
   
   
   
8. Hash Tables
   Many applications require a dynamic set that support only the dictionary operations such as insert, search, and delete.
   A hash table is an effective data structure for implementing dictionaries. Although searching for an element in a hash table can take as long as searching for an element in a linked list - O(n) time in the worst case - in practice, hashing performs extremely well.
   Under reasonable assumptions, the average time to search for an element in a hash table is O(1).
   A hash table generalizes the simpler notion of an ordinary array.
   Directly addressing into an ordinary array makes effective use of our ability to examine an arbitrary position in an array in O(1) time.
   When the number of keys actually stored is small relative to the total number of possible keys, hash table becomes an effective alternative to directly addressing an array, since a hash table typically uses an array of size proportional to the number of keys actually stored. Instead of using the keys as an array index directly, the array index is computed from the key.
   Implementing hash table involves couple of ideas such as chaining as a way to handle collisions in which more than one key map to the same array index and open addressing which is another way to deal with collisions, and perfect hashing which gives us O(1) worst-case search time.
   Check an example for Hash Table from K&R.;
   More on hashing Hash Map Sample codes
   Comparison: Hash Table vs Tree
   Examples of application: 1. De-duplication
   
   1. Removing duplicates from a stream of objects such as linear scan through a huge file or object arriving in real time (packets).
   2. Keep track of unique objects.
      1. reports unique visitors to web site
      2. avoid duplicates in search results
   3. How?
      When a new object x arrives, lookup x in hash table. If not found, insert x into hash table.
   Examples of application: 2. The 2-sum problem
   
   1. Input: unsorted array of n integers. Target sum t with any two numbers in the array.
   2. Goal: Determine whether or not there are two numbers x, y in the array with x+y = t.
   Examples of application: 3. Historical applications
   
   1. symbol tables in compilers
   2. blocking network traffic
   3. search algorithms (e.g., game tree exploration)
   Bloom filters
   



9. Heap
   In a heap, the records are stored in an array so that each key is guaranteed to be larger than its two children keys. So, no node in a heap-ordered tree has a key larger than the key at the root.
   The basic operations are:
   
   1. insert - adding a new object to the heap, O(log(n))
   2. extract - extracting max (or min) value, O(log(n))
   3. heapify - n batched inserts, O(n)
   4. delete - O(log(n))
   heap sort


10. Spatial Data Structures
    A spatial data structure is one that organized geometry in two- and three- dimensional hierarchical structures. So, the structure is nested and of recursive nature.
    
    1. Bounding Volume Hierarchy
    2. BSP Tree
    3. Octrees
    4. Scene Graph

Sorting Algorithms

n : the number of items to be sorted
k : the size of each key
d : the digit size used by the implementation.

1. Bubble Sort
2. Insertion Sort
3. Quick Sort
4. Selection Sort
5. Heap Sort
6. Bucket Sort
7. Merge Sort
8. Radix Sort
9. Counting Sort

1. Divide and Conquer


2. Randomized Algorithms


3. Greedy Algorithms
   Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit (local optimization). Although such an approach can be disastrous for some computational tasks, there are many for which it is optimal.
   Greey algorithms iteratively make myopic decisions, hoping everything works out at the end.
   
   1. Greey algorithm always makes the choice that currently seems to give the highest gain, that is to be as greedy as possible.
   2. It makes a locally optimal choice in the hope that the remaining unique subproblem leads to a globally optimal solution.
   3. For many problems, a greedy algorithm gives an optimal solution, but not for all problems.
   4. Even when Greey algorithm does not construct an optimal solution, the solution can be used as a starting point to actually construct an optimal solution.
   A game like chess can be won only by thinking ahead: a player who is focused entirely on immediate advantage is easy to defeat. But in many other games, such as Scrabble, it is possible to do quite well by simply making whichever move seems best at the moment and not worrying too much about future consequences.
   Example: Dijkstra's shortest path algorithm which process each destination once, irrevocably.
   
   Greedy vs. Divide & Conquer
   
   1. Easy to propose multiple greey algorithms for many problems
   2. Easy to analyze the running time
   3. Hard to establish correctness contrast with straightforward inductive correctness proofs
   4. Most of the greedy algorithms are not correct even if our intuition say otherwise!


4. Dynamic Programming (DP)

1. Depth-First Search (DFS)
   
   1. explore aggressively, only retreat when necessary
   2. computes a topological ordering of a directed acyclic graph and strongly connected components of directed graphs
      
      picture from Strongly Connected Component
   3. linear runtime


2. Breadth-First Search (BFS)
   
   1. explore nodes in layers
   2. runtime - linear time
   3. application - shortest paths

Compression Algorithm - Huffman