#Programming Exercises

##For Algorithms: Design and Analysis, Part 1 (Prof. Tim Roughgarden)

###1: InversionCounter Applies a divide and conquer recursive algorithm (based on Merge-Sort) to count the inversions in an unsorted array.

###2: QuickSorter Sorts an array using QuickSort and counts the number of comparisons needed using three different variations to choose a pivot.

###3: RandomContraction Finds the Min-Cut of a graph using the RandomContraction algorithm.

###4: KosarajuSCC Uses Kosaraju's algorithm to find strongly connected components in a graph.

###5: Dijkstra Applies Dijkstra's algorithm using a heap to find the shortest path from a vertex to all other vertices of a graph.

###6: TwoSumHashTable Uses a hash table to compute the number of target values t in a given interval such that there are distinct numbers x,y in the input file that satisfy x+y=t

###7: HeapMedianMantainer Implements the "Median Maintenance" algorithm