Notes

Asymptotic Notations are languages that allow us to analyze an algorithm's running time by identifying its behavior as the input size for the algorithm increases. This is also known as an algorithm's growth rate. Does the algorithm suddenly become incredibly slow when the input size grows? Does it mostly maintain its quick run time as the input size increases? Asymptotic Notation gives us the ability to answer these questions.

Insertion Sort is an effective algorithm for sorting a small number of elements. Insertion Sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left.

The algorithm takes as a parameter an array A[1,..., n] containing a sequence of length n that is to be sorted. The algorithm sorts the input numbers in-place: it rearranges the numbers within the array A, with at most a constant number of them stored outside the array at any time. The input array A contains the sorted output sequence when the Insertion Sort procedure is finished.  The algorithm written in Pseudocode is the following:

Analysis of Insertion Sort: The time taken by Insertion Sort depends on the input: sorting a thousands numbers takes longer than sorting three numbers. Moreover, Insertion Sort can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they are. 

We are often interested in considering the worst - case, that in this case is the reverse ordered sequence:

Divide and Conquer Approach, many useful algorithms are recursive in structure, to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems. These algorithms typically follow a divide - and - conquer approach, i.e. they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the problem recursively, and then combine these solutions to create a solution to the original problem.

The divide - and - conquer paradigm involves three steps at each level of the recursion:

• Divide the problem into a number of subproblems that are smaller instances of the same problem.
• Conquer the subproblems by solving them recursively.
• Combine the solutions to the subproblems into the solution for the original problem.

Analysis of Divide and Conquer Algorithms, when an algorithm contains a recursive call to itself, we can often describe its running time by a recurrence, which describes the overall running time on a problem of size n in terms of the running time on smaller inputs.

There are two common ways of solving this kind of recurrences:

• Recursion Trees
• Master Theorem Method, if the recurrence has the form T(n) = aT(n/b) + f(n)

Merge Sort is a sorting algorithm that follows the divide - and - conquer approach to sort an array.

• Divide the n-element sequence to be sorted into two sub-sequences of n/2 length.
• Conquer, sort the two subsequences recursively using Merge Sort.
• Combine, merge the sorted subsequences to produce the sorted final array.

The Pseudocode of the algorithm is the following:

Analysis of Merge Sort running time: To analyze the running time of the Merge Sort algorithm we start analyzing the time required by each step:

• Divide, just computes the middle of the subarray, which takes constant time, therefore Θ(1).
• Conquer, recursively solve two subproblems, each of size n/2, therefore contributes 2T(n/2) to the running time.
• Combine, the merge procedure on a n-element subarray takes time Θ(n).

Adding them up: T(n) = Θ(1) + 2T(n/2) + Θ(n).

When we are considering the asymptotic growth of the function, Θ(1) can be omitted. To know the upper bound to this recurrence we can now apply one of the two methods above discussed and discover that: T(n) = O(n lg n).

Binary Search. Looking for a specific information in memory is a key operation in computing. There are several ways to carry out this operation, the simplest one is Selection Sort, which consists of simply scan through all the list and search for the object.

However, especially if the list is already sorted, there are some clever and faster ways like Binary Search, this algorithm implements the divide-and-conquer approach to reach the goal faster.  Binary search compares the target value to the middle element of the array: if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful or the remaining half is empty.  - Divide, compare the middle element with the searched one.  - Conquer, recursively search one subarray.  - Combine, trivial. 

Binary Search Worst Case Analysis:  We know that there are two ways to approach this kind of analysis:

• Recurrence Tree, for n items, log(2,n) steps are needed to fully reduce the input; as each step involves a fixed number of operations the algorithm is O(log n).
• Master Theorem Method, we can define the recurrence which describes the algorithm by analysing the three main steps: 
  • Divide, Θ(1)
  • Conquer, 1T(n/2) 
  • Combine, Θ(1)

Hence the recurrence is T(n) = 1T(n/2) + Θ(1). And therefore using the **case 2 **of master theorem we can see that T(n) = O(log n).

In Randomized Algorithms, instead of assuming a distribution of inputs, we impose a distribution, that is the random one, to enforce the property that every permutation is equally likely. For many problems a randomized algorithm is the simplest or the fastest or even both. For many randomized algorithms, no particular input elicits its worst-case behavior. Even your worst enemy cannot produce a bad input array, since the random permutation makes the input order irrelevant. The randomized algorithm performs badly only if the random-number generator produces an "unlucky" permutation. 

There are many ways of obtaining randomness, some natural ones (DNA mutations and Quantum mechanics) and artificial ones like pseudo-random number generators that generate sequences of number with a big enough period to not see the difference in most of the cases.

Randomized Algorithms belong to 2 Classes:  - Monte Carlo, algorithms that run for a fixed number of steps, but produce an output that is correct with a certain level of probability.  - Las Vegas, algorithms that produce always the correct output, but its running time is a random variable whose expectation is bounded by a polynomial. 

Karger Min - Cut Algorithm Min - Cut, given an undirected graph, a global min - cut is a cut (S, V - S) minimizing the number of crossing edges, where a crossing edge is an edge (u, v) s.t. u ∈ S and v ∈ V - S.

Graph Contraction, for an undirected graph G, we can construct a new graph G' by contracting two vertices u, v in G as follows:

• U and V become one vertex {u,v} and the edge (u, v) is removed;
• The other edges incident to u or v in G are now incident on the new vertex {u, v} in G'; Note: there may be multi-edges between two vertices. We just keep them.

Karger Min - Cut Algorithm, this algorithm is a randomized one, indeed it exploits the randomness to reach a min-cut. We apply contraction at random, by associating at each edge the same probability of being chosen. Hence, the probability of choosing vertices that are connected by multiple edges is higher.

The Pseudocode of the algorithm is the following:

Karger observed that by doing this procedure repeatedly, the chance to find a Minimum Cut is Ω(1/n^2). Clearly C is a cut, what is surprising is that with reasonably high probability C is the smallest one.

To see this: let's consider Cmin = |k|. Let's now consider the step of the algorithm were t vertices are left, then each vertex must have at least k edges, otherwise a lower cut could be found. From which we know that the number of edges is k/2 * t.

We can now calculate the probability that none of the k edges of the min cut are contracted in that step, which is:

Now we have to evaluate the probability that this edges survives till the last step:

If we want to increase the probability of success we can reuse the algorithm and the probability levels can be calculated from the fact that each event is independent.

Dijkstra's Algorithm is a greedy algorithm. Which is an algorithm that always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. Greedy algorithms do not always yield optimal solutions, but for many problems they do.

Dijkstra's Algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative. 

Through the Pseudocode we can analyze the behavior of Dijkstra's Algorithm.

• In the first line we initialize the graph setting the distance of the source vertex to 0 and infinity to all other vertices. 
• In the second line we initialize the set S to an empty set.
• In the third line the set Q is initialized and contains all the vertices of the graph, it is an invariant Q = V - S. 
• Then we define the main loop which runs until the set Q is empty: inside the loop, a vertex u is extracted from the min-priority queue and added to the set S. The vertex u has the peculiarity of being the vertex with the smallest distance. 
• Finally in lines 7-8 the relaxation of the edges takes place, which means that for each vertex in the neighborhood of u, let's call each of them v, their distance is updated if the path for reaching them is shorter passing through u. The loop runs until Q != 0, which means until all nodes of the graph have been visited.

 

Analysis of Dijkstra's Algorithm The running time of Dijkstra's algorithm depends on how we implement the min-priority queue.

If we consider Q as a linear array: EXTRACT_MIN takes O(V) time and there are |V| such operations. Therefore, a total time for EXTRACT_MIN in while-loop is O(V^2^). Since the total number of edges in all the adjacency list is |E|. Therefore for-loop iterates |E| times with each iteration taking O(1) time. Hence, the running time of the algorithm with array implementation is O(V^2^ + E) = O(V^2^).

If the graph is sufficiently sparse, we can improve the algorithm by implementing the min-priority queue with a** binary min-heap**:  EXTRACT_MIN operations takes O(lg V) time and there are |V| such operations. The binary heap can be build in O(V) time. Each DECREASE operation (in the RELAX) takes **O(lg V) **time and there are at most |E| such operations. The total running time is therefore O((V + E) lg V).  Which becomes O(E lg V) if all vertices in the graph is reachable from the source vertices.

Minimum Spanning Tree A Minimum Spanning Tree is an acyclic subset of a graph that connects all of the vertices and whose total weight is minimized. Since this subset is acyclic and connects all the vertices, it must form a tree, which we call a Spanning Tree since it "spans" the graph G. We call the problem of determining the tree the Minimum Spanning Tree Problem.

Two are the algorithms that we have seen able to solve the problem, both of them are greedy algorithms: Kruskal's Algorithm and Prim's Algorithm. In Kruskal's Algorithm, the set A (subset of some minimum spanning tree) is a forest whose vertices are all those of the given graph. The edge added to A is always a least-weight edge in the graph that connects two distinct components. While in Prim's Algorithm, the Set A form a single tree (Arborescence Tree). The edge added to A is always a least-weight edge connecting the tree to a vertex not in the tree. 

The proof of this algorithm can be found in the Cut Properly Theorem: 

The algorithm of Prim's can be explained through the following Pseudocode:

The Worst-Case Analysis of the algorithm tells us, that the asymptotic behaviour of the algorithm is: O (|V| log(|V|) + |E| log(|V|)) where |V| log(|V|) is the time needed to extract the next smallest node multiplied by the number of nodes, while |E| log(|V|) gives us the time needed to update the node cost multiplied by the number of edges.