Algorithm Homework 1

Q1. We discussed two versions of the 3-sum problem: A "naive" implementation
(O(N^3)) and a "sophisticated" implementation (O(N^2 lg N)). Implement these
algorithms. Your implementation should be able to read data in from regular
data/text file with each entry on a separate line. Using Data provided
under resource (hw1-1.data.zip) to determine the run time cost of your implementations as function of input
data size. Plot and analyze (discuss) your data.

Q2. We discussed the Union-Find algorithm in class. Implement the three
versions: (i) Quick Find, (ii) Quick Union, and (iii) Quick Union with Weight
Balancing. Using Data provided here (hw1-2.data.zip, under resources)
determine the run time cost of your
implementation (as a function of input data size). Plot and analyze your
data. Note: The maximum value of a point label is 8192 for all the different
input data set. This implies there could in principle be approximately 8192 x
8192 connections. Each line of the input data set contains an integer pair (p,
q) which implies that p is connected to q.

Recall: UF algorithm should

// read in a sequence of pairs of integers (each in the range 1 to N) where N=8192

// calling find() for each pair: If the members of the pair are not already connected

// call union() and print the pair.

Q3. Recall the definition of "Big Oh" (where F(N) is said to be in O(g(N), when
F(N) < c (g(N)), for N Nc) . Estimate the value of Nc for both Q1 and
Q2. More important than the specific value, is the process and reasoning your
employ.

Q4: Farthest Pair (1 Dimension): Write a program that, given an array a[] of N
double values, find a farthest pair: two values whose difference is no smaller
than the difference of any other pair (in absolute value). The running time of
the program should be LINEAR IN THE WORST CASE.

Q5. Faster-est-ist 3-sum: Develop an implementation that uses a linear
algorithm to count the number of pairs that sum to zero after the array is
sorted (instead of the binary-search based linearithmic algorithm). Use the
ideas to develop a quadratic algorithm for the 3-sum problem.