Priority queue

• Priority queue

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

    stack — elements are pulled in last-in first-out-order (e.g. a stack of papers)
    queue — elements are pulled in first-in first-out-order (e.g. a line in a cafeteria)


It is a common misconception that a priority queue is a heap. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.


        This is also known as "pop_element(Off)", "get_maximum_element", or "get_front(most)_element".
        Some conventions reverse the order of priorities, considering lower values to be higher priority, so this may also be known as "get_minimum_element", and is often referred to as "get-min" in the literature.
        This may instead be specified as separate "peek_at_highest_priority_element" and "delete_element" functions, which can be combined to produce "pull_highest_priority_element".

In addition, peek (in this context often called find-max or find-min), which returns the highest priority element but does not modify the queue, is very frequently implemented, and nearly always executes in O(1) time. This operation and its O(1) performance is crucial to many applications of priority queues.


Using a priority queue to sort
he semantics of priority queues naturally suggest a sorting method: insert all the elements to be sorted into a priority queue, and sequentially remove them; they will come out in sorted order. This is actually the procedure used by several sorting algorithms, once the layer of abstraction provided by the priority queue is removed


    Heapsort if the priority queue is implemented with a heap.
    Smoothsort if the priority queue is implemented with a Leonardo heap.
    Selection sort if the priority queue is implemented with an unordered array.
    Insertion sort if the priority queue is implemented with an ordered array.
    Tree sort if the priority queue is implemented with a self-balancing binary search tree.


Applications

Bandwidth management
Priority queuing can be used to manage limited resources such as bandwidth on a transmission line from a network router.


Dijkstra's algorithm
When the graph is stored in the form of adjacency list or matrix, priority queue can be used to extract minimum efficiently when implementing Dijkstra's algorithm, although one also needs the ability to alter the priority of a particular vertex in the priority queue efficiently.


Huffman coding
Huffman coding requires one to repeatedly obtain the two lowest-frequency trees. A priority queue makes this efficient.

http://en.wikipedia.org/wiki/Priority_queue

Associative array

• Associative array

In computer science, an associative array, map, or dictionary is an abstract data type composed of a collection of  pairs, such that each possible key appears at most once in the collection.

The dictionary problem is the task of designing a data structure that implements an associative array. A standard solution to the dictionary problem is a hash table; in some cases it is also possible to solve the problem using directly addressed arrays, binary search trees, or other more specialized structures

Associative arrays have many applications including such fundamental programming patterns as memoization and the decorator pattern.

http://en.wikipedia.org/wiki/Associative_array

graph vs tree

• Introduction

Realize that all trees are graphs. A tree is a special case of a graph, one whose nodes are all reachable from some starting node and one that has no cycles.
Graph (c) does not have any cycles, as one less edge than it does number of nodes, and all nodes are reachable. Therefore, it is a tree.
http://msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx

• A tree is a connected graph with no cycles

https://docs.google.com/viewer?a=v&q=cache:2B00UUiFWB0J:www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f09/Site/Materials/Lectures/Lecture18/lecture18.pdf+&hl=en&pid=bl&srcid=ADGEESh21IGgvVbbit2jwxSTnGhgmrTQ7ygsouGco178oA5Zj-HGbftJXWYOo6zmIzJVrz1KflxLwogoo8SkPw6iQOVKvx0fJ6-yOdeZwucLjGfNtXr2MLtxnOwRQKyxN0QFE-R3pEMo&sig=AHIEtbTjJflUVZU-sehW22YfIRzxWuFFUg

A Tree is just a restricted form of a Graph.
Trees have direction (parent / child relationships) and don't contain cycles.
They fit with in the category of Directed Acyclic Graphs (or a DAG)
http://stackoverflow.com/questions/7423401/whats-the-difference-between-the-data-structure-tree-and-graph

Tree is a hierarchical model.
Graph is a network model.
http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

Infix to Postfix Conversion

• Infix to Postfix Conversion : 

Infix String : a+b*c-d
Postfix String : abc*+d-
http://scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/index.htm

• Infix to Postfix Notation

http://www.youtube.com/watch?v=rA0x7b4YiMI

• Infix to Postfix Notation

http://www.youtube.com/watch?v=1X_li3efgDI&feature=related

• Insert-sort with Romanian folk dance

https://www.youtube.com/watch?v=ROalU379l3U

• Algorithms #2 - Insertion Sort

https://www.youtube.com/watch?v=Fr0SmtN0IJM

Binary search algorithm

• Binary search algorithm

In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array.
In each step, the algorithm compares the input key value with the key value of the middle element of the array

If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right

http://en.wikipedia.org/wiki/Binary_search_algorithm

• Binary search algorithm

It means, that in worst case, algorithm makes 20 steps to find a value in sorted array of a million elements or to say, that it doesn't present it the array.


Algorithm

Algorithm is quite simple. It can be done either recursively or iteratively:

get the middle element;
if the middle element equals to the searched value, the algorithm stops;
otherwise, two cases are possible:
searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.
   
   
Java

/**
 * searches for a value in sorted array
 *
 * @param array
 *            array to search in
 * @param value
 *            searched value
 * @param left
 *            index of left boundary
 * @param right
 *            index of right boundary
 * @return position of searched value, if it presents in the array or -1, if
 *         it is absent
 */
int binarySearch(int[] array, int value, int left, int right) {
      if (left > right)
            return -1;
      int middle = (left + right) / 2;
      if (array[middle] == value)
            return middle;
      else if (array[middle] > value)
            return binarySearch(array, value, left, middle - 1);
      else
            return binarySearch(array, value, middle + 1, right);        
}


http://www.algolist.net/Algorithms/Binary_search

• İkili Arama Algoritması (Binary Search Algorithm)

http://www.bilgisayarkavramlari.com/2009/12/21/ikili-arama-algoritmasi-binary-search-algorithm/

• İkili arama algoritması

http://tr.wikipedia.org/wiki/%C4%B0kili_arama_algoritmas%C4%B1

• Binary Search - Example, Explanations, Algorithm & Code Part 2/2

http://www.youtube.com/watch?v=ZvJA-bdIvN8

Graphs

• Directed Graph

The ordered pairs in E represent the direction of the edge, i.e., (tail, head) tail is source vertex and head is the target vertex

Undirected Graph

The pairs in E are unordered pairs, i.e., there is no tail or head and there is no direction to the edge, e.g., (u, v) ∈ E is really the same edge as (v, u)

http://homepages.ius.edu/rwisman/C455/html/notes/AppendixB4/GraphBasics.htm

• Kinds of Graphs

Various flavors of graphs have the following specializations and particulars about how they are usually drawn.
Undirected Graphs.

In an undirected graph, the order of the vertices in the pairs in the Edge set doesn't matter. Thus, if we view the sample graph above we could have written the Edge set as {(4,6),(4,5),(3,4),(3,2),(2,5)),(1,2)),(1,5)}. Undirected graphs usually are drawn with straight lines between the vertices.
The adjacency relation is symetric in an undirected graph, so if u ~ v then it is also the case that v ~ u.

Directed Graphs.

In a directed graph the order of the vertices in the pairs in the edge set matters. Thus u is adjacent to v only if the pair (u,v) is in the Edge set. For directed graphs we usually use arrows for the arcs between vertices. An arrow from u to v is drawn only if (u,v) is in the Edge set. The directed graph below

http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html

• 4.1  Undirected Graphs

Graphs
A graph is a set of vertices and a collection of edges that each connect a pair of vertices


Glossary.
Here are some definitions that we use.

    A self-loop is an edge that connects a vertex to itself.
    Two edges are parallel if they connect the same pair of vertices.
    When an edge connects two vertices, we say that the vertices are adjacent to one another and that the edge is incident on both vertices.
    The degree of a vertex is the number of edges incident on it.
    A subgraph is a subset of a graph's edges (and associated vertices) that constitutes a graph.
    A path in a graph is a sequence of vertices connected by edges. A simple path is one with no repeated vertices.
    A cycle is a path (with at least one edge) whose first and last vertices are the same. A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).
    The length of a path or a cycle is its number of edges.
    We say that one vertex is connected to another if there exists a path that contains both of them.
    A graph is connected if there is a path from every vertex to every other vertex.
    A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs.
    An acyclic graph is a graph with no cycles.
    A tree is an acyclic connected graph.
    A forest is a disjoint set of trees.
    A spanning tree of a connected graph is a subgraph that contains all of that graph's vertices and is a single tree. A spanning forest of a graph is the union of the spanning trees of its connected components.
    A bipartite graph is a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set.

http://algs4.cs.princeton.edu/41undirected/

Binary Search Tree

• Binary Search Trees

• Binary Search Tree Property: The value

stored at a node is greater than the value
stored at its left child and less than the value
stored at its right child
Thus, the value stored at the root of a
subtree is greater than any value in its left
subtree and less than any value in its right
subtree!!


https://docs.google.com/viewer?a=v&q=cache:0Gua_CCn2fYJ:www.cse.unr.edu/~bebis/CS308/PowerPoint/BinarySearchTrees.ppt+&hl=en&pid=bl&srcid=ADGEESgb6XpuTDtC7ykBB3X6TzalNiMPwH4--Dw7oFhsmlz0CKzQYY0pUm1GQH6TnPqGIPWKxJRJmNvlYGyFcVmC2g7csdTN0I6vGHdlpByaLEwFrhxl_vyLNRe2ZBUWxWrbz0he_XGB&sig=AHIEtbSmEUZfU7Uxcaopi5Qoxy10g9wXTg

• Binary Search Tree (§9.1)

A binary search tree is a binary tree storing
keys (or key-element pairs) satisfying the
following property:

Property - given a node with a value X, all the
values of nodes in the left subtree are smaller
than X and all the values of the nodes in the
right subtree are larger than X


https://docs.google.com/viewer?a=v&q=cache:yzHYvCMpV3gJ:www.cs.ucr.edu/cs14/cs14_06win/slides/BinarySearchTrees.pdf+&hl=en&pid=bl&srcid=ADGEESi5_segPdHcDjHa1xfkg_8v2ZjE0Hqp9XTQ0a_oZRS6uzr5xRhdK4dliH6Gs7WKNFQ_B6060x0vw3hGz2MfYC894jagI6gLupiucS66wDOEvcM90mhFIMDPqhp5Bsypzejh7ChF&sig=AHIEtbRXU98VmMnMNIqIlg-F1PZ592hnaA

• Binary Search Trees

A binary search tree is a binary tree with a
special property called the BST-property,
which is given as follows:
⋆ For all nodes x and y, if y belongs to the
left subtree of x, then the key at y is less
than the key at x, and if y belongs to the
right subtree of x, then the key at y is
greater than the key at x.

https://docs.google.com/viewer?a=v&q=cache:VpSPd7v8DmQJ:www.cs.rochester.edu/~gildea/csc282/slides/C12-bst.pdf+&hl=en&pid=bl&srcid=ADGEESjjCepXiYWSyJn_c4qbmrlXw_TN7ScZWuGxkvSiLVSk4SNtl25Vu4j11wdfVnC9a18nXNn2Zu2bkeTI9RY_D9cuNlJqXjH-WAWXTXg6wOYex_KjJBGKSdwHPEdXkbufnmMFzBPK&sig=AHIEtbRCO8kKe5kt_fj8F68UIbr_iLrt-w

• What is a binary search tree?

A binary search tree is a binary tree with the following properties:
The data stored at each node has a distinguished key which is unique in the tree and belongs to a total order. (That is, for any two non-equal keys, x,y either x < y or y < x.)
The key of any node is greater than all keys occurring in its left subtree and less than all keys occurring in its right subtree.

http://pages.cs.wisc.edu/~siff/CS367/Notes/bsts.html

• Binary Search Trees

http://www.youtube.com/watch?v=9z8nyD5J-qE&feature=relmfu

Postfix to Infix

• Problem 3: Postfix to Infix

A popular example of using a stack in data structure courses is to convert an infix expression (e.g. 2 * 5 + 3) to postfix (2 5 * 3 +).
The reverse process is slightly harder, particularly because a given postfix expression can convert to multiple infix expressions due to parentheses
http://www.eecis.udel.edu/~breech/contest.inet.fall.03/problems/toinfix.html

• Postfix to Infix Notation 

http://www.youtube.com/watch?v=OlRENYiiIiw

• Converting Postfix Expressions to Infix

    The postfix expression is scanned from left to right.
    If a token is a number, the token is pushed onto the stack.
    If a token is an operator, the top two infix subexpressions are popped from the stack and a new infix expression is constructed by combining these subexpressions with the operator in a normal infix manner. The resulting expression is then pushed onto the stack. Initially, we will place each subexpression in parentheses to ensure the proper order of evaluation in the final expression.


http://www.codeproject.com/Articles/405361/Converting-Postfix-Expressions-to-Infix

Heapsort

• Heapsort

Heapsort is a sorting algorithm that maintains the O(n lg n) run time (like mergesort) but operates in place (like insertion sort). This sorting algorithm is based on a data structure known as a heap (which is also one way to implement a priority queue).

Heaps
A heap is simply an array viewed as a nearly complete binary tree (meaning a subsequent level is not started until the previous level is completely filled).

Heap values
We define the following values for an array A viewed as a heap
A.length - size of the array
A.heapsize - number of elements in the heap (note A.heapsize ≤ A.length)
height - height of the heap binary tree = Θ(lg n)


Heap operations
A[i] - value at node (element) i
LEFT(i) - index of left child node = 2i
RIGHT(i) - index of right child node = 2i + 1
PARENT(i) - index of parent node = i / 2


Max-heaps
We define a max-heap as a heap that satisfies the property that A[PARENT(i)] ≥ A[i] for all i, i.e. the value of every parent is greater than both children.
Thus for a max-heap, the largest value is stored at the root

Min-heaps
Similarly we define a min-heap as a heap that satisfies the property that A[PARENT(i)] ≤ A[i] for all i, i.e. the value of every parent is less than both children.
Thus for a min-heap, the smallest value is stored at the root.
http://faculty.ycp.edu/~dbabcock/PastCourses/cs360/lecture/lecture07.html

Binary Tree

Binary Trees
A binary tree is a tree in which each node can have maximum two children.
Thus each node can have no child, one child or two children

Consider a set of numbers: 25,63,13, 72,18,32,59,67.
we store these numbers in individual nodes of a singly linked list
To search for a particular item we have to go through the list, and maybe we have to go to the end of the list as well.
Thus if there were n numbers, our search complexity would be O(n).

suppose we order these numbers:
13,18,25,32,59,63,67,72. and store these in another linked list.
search complexity is still O(n)

You simply cannot apply binary search on a linked list with O(log n) complexity.
So a linear linked structure is not helping

The value at any node is more than the values stored in the left-child nodes,
and less than the values stored in the right-child nodes

Implementation
• A binary tree has a natural implementation in linked storage.
A tree is referenced with a pointer to its root.

A tree is a node with structure that contains more trees.
We have actually a tree  located at each node of a tree.

http://www.cs.ucf.edu/courses/cop3502h.02/trees1.pdf

tree traversal

• tree traversal

tree traversal refers to the process of visiting (examining and/or updating) each node in a tree data structure,
Such traversals are classified by the order in which the nodes are visited.



Although linked lists require more memory space than arrays ( as they have to store address at each node),
they have definite advantages  over arrays.
Insertion and deletion of items can be carried out with out involving considerable movement of data.
http://www.cs.ucf.edu/courses/cop3502h.02/trees1.pdf

• Tree Traversals

Linked lists are traversed sequentially from first node to the last node.
However, there is no such natural linear order for the nodes of a tree.
Different orderings are possible for traversing a binary tree.
Every node in the tree is a root for the subtree that it points to.

There are three common traversals for binary trees:
• Preorder
• Inorder
• Postorder

These names are chosen according to the sequence in which the root node and its children are visited.

http://www.cs.ucf.edu/courses/cop3502h.02/trees1.pdf

• Tree Traversals

There are 3 common tree traversals.
1. in-order: left, root, right
2. pre-order: root, left, right
3. post-order: left, right, root

Note "pre" and "post" refer to when we visit the root.
(we always go from left to right throug leaves but when it is in-order root is in the middle,pre-order it's first and post-order it's last.)

The in-order traversal always prints the values in sorted order from smallest to largest.
http://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf

• Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph.

One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.
http://en.wikipedia.org/wiki/Depth-first_search

• In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: 

(a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node.
The BFS begins at a root node and inspects all the neighboring nodes
http://en.wikipedia.org/wiki/Breadth-first_search

• There are three types of depth-first traversal: pre-order, in-order and post-order. For a binary tree, they are defined as operations recursively at each node, starting with the root node follows:

Pre-order:
Visit the root.
Traverse the left subtree.
Traverse the right subtree.

In-order (symmetric):
Traverse the left subtree.
Visit the root.
Traverse the right subtree.

Post-order:
Traverse the left subtree.
Traverse the right subtree.
Visit the root.

http://en.wikipedia.org/wiki/Tree_traversal

• infix traversal gives an infix expression

pre-order traversal gives an pre-order expression
post-order traversal gives an post-order expression

infix,pre-order,post-order traversal example

http://www.cs.nuim.ie/~rosemary/se202/treenotes/sld029.htm

• infix,pre-order,post-order traversal example

http://www.cs.cuw.edu/csc/csc300/PowerPoint/TREE%20TRAVERSAL%20EXAMPLE.htm

• D = node, L = left, R =right

• Preorder (DLR) traversal yields: A, H, G, I,F, E, B, C, D

• Postorder (LRD) traversal yields: G, F, E, I,H, D, C, B, A

• In-order (LDR) traversal yields: G, H, F, I,E, A, B, D, C

• Level-order traversal yields: A, H, B, G, I,C, F, E, D

https://docs.google.com/viewer?a=v&q=cache:tUIMUu37Z0oJ:www.cs.siu.edu/~mengxia/Courses%2520PPT/220/finalreview.ppt+&hl=tr&gl=tr&pid=bl&srcid=ADGEEShcYilAqNqch2AN6p2yyA1XFccuhVzGrCzXYljzzrgoZdqR87OAqbgN_osKxdp3B4Jgy_KkgYCHvIImna7DTFXFxruRbv2o2yIOiBqzf6nd-sjahVvFsq0NOpRuZEjA3MrdXXMr&sig=AHIEtbRCSWKbeBnN-GpbuR0Kj_GGrNrgUA

• Inorder Traversal - LDR

The node’s left subtree is traversed
The node’s data is processed
The node’s right subtree is traversed

Preorder Traversal - DLR

The node’s data is processed
The node’s left subtree is traversed
The node’s right subtree is traversed

Postorder Traversal - LRD

The node’s left subtree is traversed
The node’s right subtree is traversed
The node’s data is processed

https://docs.google.com/viewer?a=v&q=cache:962RB0q-kPkJ:digital.cs.usu.edu/~allan/CS2/Slides/Ch20.pdf+&hl=tr&gl=tr&pid=bl&srcid=ADGEEShPsArt6bX6XAwSHqxzO9ueMEXYOczpYtzLEzcF_Ynxbjqt6S1oSfU6KZShCTWPLazYXtcZsAoDP-iJXq5Ajh_cxtYcXFFOlTGyvNt_1NJ3I4kv2c8oTNYkz372sJqPZFI2kVG0&sig=AHIEtbRfU_jyEsuIyuN6vdEPyzXhoCCEtA

infix prefix postfix notations

Infix notation

Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 2)
It is not as simple to parse by computers as prefix notation ( e.g. + 2 2 ) or postfix notation ( e.g. 2 2 + ), but many programming languages use it due to its familiarity

In infix notation, unlike in prefix or postfix notations, parentheses surrounding groups of operands and operators are necessary to indicate the intended order in which operations are to be performed. In the absence of parentheses, certain precedence rules determine the order of operations.

http://en.wikipedia.org/wiki/Infix_notation


Prefix notation
Polish notation, also known as Polish prefix notation or simply prefix notation, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left of their operands.

http://en.wikipedia.org/wiki/Polish_notation


Postfix notation
Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position.

http://en.wikipedia.org/wiki/Reverse_Polish_notation

How to Calculate the Hamming Code

• How to Calculate the Hamming Code

Hamming codes are used to insert error correction information into data streams. The codes are designed so that an error can not only be detected, but corrected. Adding error correction information increases the amount of data, but increases the reliability of communications over mediums with high error rates

http://www.ehow.com/how_6635076_calculate-hamming-code.html#ixzz2C7sLUvXH

• Hamming Distance

Hamming distance of two bit strings = number of bit positions in which they differ
If the valid words of a code have minimum Hamming distance D, then D-1 bit errors can be detected.
If the valid words of a code have minimum Hamming distance D, then [(D-1)/2] bit errors can be corrected.

• The Hamming Distance is a number used to denote the difference between two binary strings.

Hamming's formulas allow computers to detect and correct error on their own.
The Hamming Code earned Richard Hamming the Eduard Rheim Award of Achievement in Technology in 1996, two years before his death
Hamming's additions to information technology have been used in such innovations as modems and compact discs.

Step 1
Ensure the two strings are of equal length. The Hamming distance can only be calculated between two strings of equal length. String 1: "1001 0010 1101" String 2: "1010 0010 0010"
Step 2
Compare the first two bits in each string. If they are the same, record a "0" for that bit. If they are different, record a "1" for that bit. In this case, the first bit of both strings is "1," so record a "0" for the first bit.
Step 3
Compare each bit in succession and record either "1" or "0" as appropriate. String 1: "1001 0010 1101" String 2: "1010 0010 0010" Record: "0011 0000 1111"
Step 4
Add all the ones and zeros in the record together to obtain the Hamming distance. Hamming distance = 0+0+1+1+0+0+0+0+1+1+1+1 = 6

http://classroom.synonym.com/calculate-hamming-distance-2656.html

• The Hamming Distance can be used to correct or detect errors in a transmission.

If there are d errors, you need a Hamming Distance of 2d+1 to correct or d+1 to detect.

Hamming distance between two vectors is the number of bits we must change to change one into the other.
Example Find the distance between the vectors 01101010 and 11011011.

01101010
11011011

They differ in four places, so the Hamming distance d(01101010; 11011011) = 4.

http://www.math.ryerson.ca/~danziger/professor/MTH108/Handouts/codes.pdf

• Shortcut for hamming code

http://www.youtube.com/watch?v=JAMLuxdHH8o

Loop invariant

In computer science, a loop invariant is an invariant used to prove properties of loops. Informally, a loop invariant is a statement of the conditions that should be true on entry into a loop and that are guaranteed to remain true on every iteration of the loop. This means that on exit from the loop both the loop invariant and the loop termination condition can be guaranteed.
http://en.wikipedia.org/wiki/Loop_invariant

An algorithm's real-time readiness ratio (RTR)

real-time ratio=average-case running time / worst-case running time

	bubblesort	heapsort	insertion	mergesort	quicksort
best	n	nlogn	n	nlogn	nlogn
average	n^2	nlogn	n^2	nlogn	nlogn
worst	n^2	nlogn	n^2	nlogn	n^2

http://www.youtube.com/watch?v=WRekXblcQn8&feature=relmfu

directed acyclic graph (DAG)

• Directed Acyclic Graphs

A directed acyclic graph (DAG) is a directed graph that contains no cycles
http://www.csse.monash.edu/~lloyd/tildeAlgDS/Graph/DAG/

In mathematics and computer science, a directed acyclic graph is a directed graph with no directed cycles
it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again

A collection of tasks that must be ordered into a sequence, subject to constraints that certain tasks must be performed earlier than others, may be represented as a DAG with a vertex for each task and an edge for each constraint

algorithms for topological ordering may be used to generate a valid sequence.

http://en.wikipedia.org/wiki/Directed_acyclic_graph

• A Model to Represent Directed Acyclic Graphs (DAG) on SQL Databases

In short, DAGs have the following properties:

A DAG has directed edges, i.e. the links that connect vertices (nodes) on the graph have a direction. The direction is denoted by an arrow head.
Starting from an arbitrary vertex, if we traverse the vertices in the direction of the arrows, it is not possible to return back to the originating vertex.

A notable and familiar structure that has the above properties is the inheritance hierarchy in Object-Oriented Programming
http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o

Algorithm Analysis

What is an algorithm and why do we want to analyze one? An algorithm is a step-by-step procedure for accomplishing some end.
what can we do with it? Well, obviously we can run the program and observe its behavior.
In order to learn more about an algorithm, we can ``analyze'' it.
By this we mean to study the specification of the algorithm and to draw conclusions about how the implementation of that algorithm--the program--will perform in general.

what can we analyze?
     determine the running time of a program as a function of its inputs;
    determine the total or maximum memory space needed for program data;
    determine the total size of the program code;
    determine whether the program correctly computes the desired result;
    determine the complexity of the program--e.g., how easy is it to read, understand, and modify; and,
    determine the robustness of the program--e.g., how well does it deal with unexpected or erroneous inputs?
   
we are concerned primarily with the running time.
We also consider the memory space needed to execute the program.
There are many factors that affect the running time of a program.
Among these are the algorithm itself, the input data, and the computer system used to run the program
http://www.brpreiss.com/books/opus5/html/page36.html

bubble sort vs quick sort

• bubble sort vs quick sort

http://www.youtube.com/watch?v=vxENKlcs2Tw
bubble sort compares every adjacent element(something next to it) and moves the biggest element forward

(if you are supposed to list numbers in descending order)
the same operation is run on the remaining part of the elements

• Bubble sort

Bubble sort  is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.
The algorithm gets its name from the way smaller elements "bubble" to the top of the list. 
Because it only uses comparisons to operate on elements, it is a comparison sort. 
Although the algorithm is simple, most other algorithms are more efficient for sorting large lists
Bubble sort has worst-case and average complexity both ?(n2), where n is the number of items being sorted

There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). 
Even other O(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort
Therefore, bubble sort is not a practical sorting algorithm when n is large.
Performance of bubble sort over an already-sorted list (best-case) is O(n).

 Large elements at the beginning of the list do not pose a problem, as they are quickly swapped. 
 Small elements towards the end, however, move to the beginning extremely slowly.
 This has led to these types of elements being named rabbits and turtles, respectively



 Pseudocode implementation

 procedure bubbleSort( A : list of sortable items )
   repeat     
     swapped = false
     for i = 1 to length(A) - 1 inclusive do:
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort


http://en.wikipedia.org/wiki/Bubble_sort

• Code snippets

Java

public void bubbleSort(int[] arr) {
      boolean swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < arr.length - j; i++) {                                       
                  if (arr[i] > arr[i + 1]) {                          
                        tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        swapped = true;
                  }
            }                
      }
}
C++

void bubbleSort(int arr[], int n) {
      bool swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < n - j; i++) {
                  if (arr[i] > arr[i + 1]) {
                        tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        swapped = true;
                  }
            }
      }
}


http://www.algolist.net/Algorithms/Sorting/Bubble_sort

binary heap

• GRE Computer Science Question 02

http://www.youtube.com/watch?v=Imfaj84IaWY&feature=relmfu

• Heaps

http://www.youtube.com/watch?v=_9QXNFcrF4c

• Heaps Part 2

http://www.youtube.com/watch?v=DHhPg01rBGs&feature=relmfu

• Binary Heaps

A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:

the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.

Since a heap is a complete binary tree, it has a smallest possible height - a heap with N nodes always has O(log N) height.

http://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html

• Binary Heaps

A binary heap is a complete binary tree, where each node has a higher priority than its children

Complete binary tree: Each node has two children, except for the last two levels.
(The nodes at the last level do not have children.)
New nodes are inserted at the last level from left to right.

This is called heap-structure property.

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L11-BinHeap.htm

• Heap is a binary tree with two special properties: it must have all its nodes in specific order and its shape must be complete.

have duplicate values in a heap — there’s no restriction against that

 The ordering of the child nodes isn’t important for a heap

A heap doesn’t follow the rules of a binary search tree; unlike binary search trees, the left node does not have to be smaller than the right node

Heap can be broadly classified in two types :

1. Min heap

2. Max heap

Min Heap

A min heap is a heap where every single parent node, including the root, is less than or equal to the value of its children nodes.

Max Heap

Every parent node, including the root, is greater than or equal to the value of its children nodes.

Heap Majorly has 3 operations –

Insert Operation(Time complexity O(log n))

Delete Operation (Time complexity O(log n))

Extract-Min (OR Extract-Max) (Time complexity O(n))

The heap data structure has many applications:

Heapsort:with no quadratic worst-case scenarios.

Selection algorithms: A heap allows access to the min or max element in constant time, and other selections (such as median or kth-element) can be done in sub-linear time on data that is in a heap.

Graph algorithms: By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are Prim's minimal-spanning-tree algorithm and Dijkstra's shortest-path algorithm.

Priority Queue: A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods

K-way merge: A heap data structure is useful to merge many already-sorted input streams into a single sorted output stream. 

Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.

https://iq.opengenus.org/max-heap-min-heap/

Selection Sort

• Algorithms Lesson 8: Selection Sort

http://www.youtube.com/watch?v=6nDMgr0-Yyo&feature=relmfu

• Selection Sort

In computer science, a selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm works as follows:
Find the minimum value in the list
Swap it with the value in the first position
Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)


/* a[0] to a[n-1] is the array to sort */
int i,j;
int iMin;

/* advance the position through the entire array */
/*   (could do j < n-1 because single element is also min element) */
for (j = 0; j < n-1; j++) {
    /* find the min element in the unsorted a[j .. n-1] */

    /* assume the min is the first element */
    iMin = j;
    /* test against elements after j to find the smallest */
    for ( i = j+1; i < n; i++) {
        /* if this element is less, then it is the new minimum */
        if (a[i] < a[iMin]) {
            /* found new minimum; remember its index */
            iMin = i;
        }
    }

    /* iMin is the index of the minimum element. Swap it with the current position */
    if ( iMin != j ) {
        swap(a[j], a[iMin]);
    }
}


http://en.wikipedia.org/wiki/Selection_sort

• Selection Sort

https://www.youtube.com/watch?v=f8hXR_Hvybo

• Algorithms #3 - Selection Sort

https://www.youtube.com/watch?v=TW3_7cD9L1A