Index of /~bernhard/317/assign4

      Name                    Last modified       Size  Description


[DIR] Parent Directory        14-Jun-2009 22:48      -  
[TXT] braid1000               24-May-2009 21:03    27k  
[TXT] braid10000              24-May-2009 21:03   326k  
[TXT] braid100000             24-May-2009 21:03   3.8M  
[TXT] braid1000000            24-May-2009 21:03  43.2M  
[TXT] complex1000             24-May-2009 21:03    54k  
[TXT] complex10000            24-May-2009 21:03   618k  
[TXT] complex100000           24-May-2009 21:03   6.9M  
[TXT] complex1000000          24-May-2009 21:03  76.6M  
[TXT] maxFlowResults.txt      12-Jun-2009 15:02     2k  
[TXT] simple1000              24-May-2009 21:03    41k  
[TXT] simple10000             24-May-2009 21:03   447k  
[TXT] simple100000            24-May-2009 21:03   4.7M  
[TXT] simple1000000           24-May-2009 21:03  51.3M  

COMP317B Design and Analysis of Algorithms

Assignment 4, due Friday June 5th, 5pm

It is recommended that you complete this assignment with a partner.
This assignment has three parts of equal worth.

----------------------------------------------------------------------

Q1: Dynamic programming

Use dynamic programming to design a O(N^2) algorithm for finding
the length of the longest strictly increasing subsequence of a
sequence of integers; e.g. longest(2,1,3,5,1,3) = 3; with 2,3,5 and 1,3,5
as possible subsequences. 

Use the following Java snippet to produce random sequences of size n:

public int[] randomIntSequence(int n) {
   Random r = new Random(n);
   int[] sequence = new int[n];
   for(int i = 0; i < n; i++) sequence[i] = r.nextInt(n);
   return sequence;
}

n=5 produces 2,2,4,4,1, which has a longest subsequence of size 2.
n=50000 should return 433. 

To make sure that your implementation is of the correct
complexity, time runs for 50000,100000,200000, and 400000, repeat
each run 5 times, take the median, and produce a log-log plot of n
vs. runtime in seconds.

----------------------------------------------------------------------

Q2: Master method

Use the Master method to determine the complexity of a recursive
algorithm with the following recurrence equation: 

 T(n) = 3*T(n/4) + n*log(n)

Show and explain your work.

-------------------------------------------------------------------

Q3: the Ford-Fulkerson algorithm

Implement the Ford-Fulkerson algorithm to compute the maximum
flow for a given weighted directed acyclic graph (WDAG). 
Implement either depth-first or breadth-first search for
finding augmenting pathes.

Implement a Java class that will read in a 
description of the WDAG from a text file
and then compute and output the maximum flow.
The name of the file will be supplied as the
first argument: "java MaxFlow <WDAGFileName>"

<WDAGFileName> will have a very simple format:
each line describes one edge as
<from> <to> <capacity>

The source node will always be called SOURCE and the
target node will always be called TARGET. One of the
examples from the lecture would be described as:

SOURCE N1 50
SOURCE N2 50
N1 N2 1
N1 TARGET 50
N2 TARGET 50
 
Verify your implementation using this example and the
other slightly more complex WDAG from the lecture.

There is a list of testfiles provided in this directory:

braid1000
braid10000
braid100000
braid1000000

simple1000
simple10000
simple100000
simple1000000

complex1000
complex10000
complex100000
complex1000000

Measure the runtime of your code for these larger files.
Report the median of three runs for each setting.
Terminate any runs that take more than 5 minutes.