# Course Assessment

This course is assessed 80% by exam and 20% by course work. The exam questions will come from the material on this site. In particular, any of the lab exercises could come up as an exam question. The best way to revise is to do all the lab exercises.

## Assignment

The assignments for this course are a collection of Lab exercises. Each week there is a designated lab exercise or exercises that you must complete in order to get you mark.

The marks for lateness are as is follows:

1. week late: 60%
2. weeks late: 40%
3. weeks late: 20%
4. weeks late: 10%

 Lab 10 marks 6 marks 4 marks 2 marks 1 mark 1 9 Oct 16 Oct 23 Oct 30 Oct 13 Nov 2 16 Oct 23 Oct 30 Oct 13 Nov 20 Nov 3 23 Oct 30 Oct 13 Nov 20 Nov 27 Nov 4 30 Oct 13 Nov 20 Nov 27 Nov 4 Dec 5 13 Nov 20 Nov 27 Nov 4 Dec 11 Dec 7 20 Nov 27 Nov 4 Dec 11 Dec - 8 27 Nov 4 Dec 11 Dec - - 9 4 Dec 11 Dec 10 11 Dec

# Week 1 Sorting (2 Oct 2014)

## Lab Exercises for Week 1

Lab Exercise 1
Here is a program for doing a Bubblesort on the command line arguments.

```class Bubble1
{

static void Bubblesort(int [] a,  int N)
{
for (int i=N-1;i>0;i--)
for (int j=0;j<i;j++)
if (a[j] > a[j+1])
{
int temp = a[j+1];
a[j+1]=a[j];
a[j]=temp;
}

}

static void print(int [] a,  int N)
{

for (int i=0;i<N;i++) System.out.println(a[i]);

}

public static void main (String [] args)
{
int b[]=new int[args.length];
for (int i=0;i<args.length;i++) b[i]=Integer.parseInt(args[i]);
Bubblesort(b,args.length);
print( b, args.length);
}
}
```

Lab Exercise 2
Try it out. For example try: `java Bubble1 25 6 3 2`

Lab Exercise 3
Run Bubble1 for a few different inputs

Lab Exercise 4
Change Bubble1 so it sorts in ascending order.

Lab Exercise 5
Here is a program that reads from the file studentMarks.txt:

```import java.io.*;
import java.util.Scanner;

class Student
{
String name;
int mark;

Student (String s, int n)
{
name=s;
mark=n;;
}
public String toString()
{
return "name: " + name + "     mark: " + mark;
}
}

public   class studentMarks
{
public static void main (String[] args) throws Exception
{
Student[] students = new Student[10000];
Scanner s = new Scanner(new FileReader("studentMarks.txt"));
String z;
int i=0;
while (s.hasNext())
{
z =s.nextLine();
String[] results = z.split(",");
students[i]=new Student(results[0],Integer.parseInt(results[1]));
i++;
}
}
}
```
1. Write a program to print the results in descending order (Designated Exercise).
2. What is the median mark? Write a program to find out.

Lab Exercise 6
The student has two names; a first name and a family name. Sort the marks in ascending alphabetical order by family name.

Hint

```class alpha
{

static boolean before(String s, String t)
{
char [] S = s.toCharArray();
char [] T = t.toCharArray();
int ls=0;
int lt=0;

while (ls<S.length && lt<T.length)
{
if (S[ls] < T[lt]) return true;
if (S[ls] > T[lt]) return false;
ls++;lt++;
}
if (ls==S.length && lt==T.length) return true;
else return (ls==S.length);
}

static String bitAfterSpace(String s)
{
String t="";
char c=s.charAt(0);
int i=0;
while (s.charAt(i)!=' ')i++;
i++;
while (i < s.length()) {t+=s.charAt(i);i++;}
return t;
}

public static void main (String args[])
{
System.out.println(before(args[0],args[1]));
System.out.println(bitAfterSpace("Fred Bloggs"));
}
}
```

# Week 2 - Timing Java Programs (9 Oct 2014)

## Lecture

Watch this video about timing Java programs.
```
public class start
{

static void doSomething()
{

}

public static void main (String args[])
{
long x=System.nanoTime();
doSomething();
long y=System.nanoTime()-x;
System.out.println(y);
}
}
```
Watch this video about running the program `one`.
```public class one
{
static final int N=500000;
static int [] a= new int [N];

static void doSomething()
{

for (int j=0;j<N;j++) a[j]=j;
}

public static void main (String args[])
{

int k=0;
for (int i=1;i<500;i++)
{

long x=System.nanoTime();
for (int j=0;j<i;j++) doSomething();
System.out.println(i+" "+(System.nanoTime()-x));

}

}
}
```

Watch this video about using gnuplot on the output.

Watch this video (if you don't use Linux!).

```import java.io.*;

public class two
{
static final int N=50000;
static int [] a= new int [N];

static void doSomething()
{

for (int j=0;j<N;j++) a[j]=j;
}

public static void main (String args[]) throws Exception
{

PrintStream out =new PrintStream(new FileOutputStream(args[0]));

int k=0;
for (int i=1;i<500;i++)
{

long x=System.nanoTime();
for (int j=0;j<i;j++) doSomething();
out.println(i+" "+(System.nanoTime()-x));

}

}
}
```

```set terminal png
set output 'plot0.png'
plot 260000*x,"output1"
```

## Example Programs and Their Plots

### Loop within a Loop (quadratic)

Watch My video: How to time Java programs with quadratic time complexity and plot the curve.

```class quadratic
{
static  int f(int N)
{
int total=0;
for (int i=0;i<N;i++)
for (int j=0;j<N;j++)
total=total+i+j;
}

public static void main(String[] args)
{
for (int i=0;i<1000;i++)
{
long x=System.nanoTime();
f(i);
System.out.println(i+" "+(System.nanoTime()-x));
}
}
}
```

To create this output first run

```java quadratic > outQuad
```

The create a file called `plotQuad` containing:

```set terminal png
```

Then run (on igor):

```gnuplot plotQuad
```

The output will be in a file called `plotQuad.png`.

You might have to change the curve to make your's fit.

### Loop within a Loop within a loop (cubic)

```class cubic
{
static  int f(int N)
{
int total=0;
for (int i=0;i<N;i++)
for (int j=0;j<N;j++)
for (int k=0;k<N;k++)
total=total+i+j+k;
}

public static void main(String[] args)
{
for (int i=0;i<10000;i++)
{
long x=System.nanoTime();
f(i);
System.out.println(i+" "+(System.nanoTime()-x));

}
}
}
```
To create this output first run
```java cubic > outCubic
```

The create a file called `plotQuad` containing:

```set terminal png
set output "plotCubic.png"
plot "outCubic",0.75*x*x*x
```

Then run (on igor):

```gnuplot plotCubic
```

The output will be in a file called `plotCubic.png`.

You might have to change the curve to make your's fit.

### Fibonacci (exponential)

```class fib
{

static  int f(int N)
{
if (N<2) return 1;
return f(N-1)+f(N-2);
}

public static void main(String[] args)
{
for (int i=0;i<50;i++)
{
long x=System.nanoTime();
f(i);
System.out.println(i+" "+(System.nanoTime()-x));

}

}

}
```

To create this output first run

```java quadratic > outFib
```

The create a file called `plotQuad` containing:

```set terminal png
set output "plotFib.png"
```

That's

Then run (on igor):

```gnuplot plotFib
```

The output will be in a file called `plotFib.png`.

You might have to change the curve to make your's fit.

Watch this video on how to use gnuplot to save graphs as image files.

## Timing Bubble Sort

Watch this video.

```class Bubble
{

static int[] A = new int [1000000];

static void Bubblesort(int [] a,  int N)
{
for (int i=N-1;i>0;i--)
for (int j=0;j<i;j++)
if (a[j] > a[j+1])
{
int temp = a[j+1];
a[j+1]=a[j];
a[j]=temp;
}

}

static void init()
{
for (int i=0;i<1000000;i++) A[i]=i;

}

static void print(int [] a,  int N)
{
for (int i=0;i<N;i++) System.out.println(a[i]);

}

public static void main (String [] args)
{
for (int i=0;i<1000;i++)
{
init();
long x=System.nanoTime();
Bubblesort(A,i);
System.out.println(i+" "+(System.nanoTime()-x));
}
}

}
```
Watch this video.

## Lab Exercises for Week 2

Lab Exercise 1
Do all the experiments covered in the above lecture yourself (Designated Exercise).

Lab Exercise 2
For each of the examples - two.java, quadratic.java, cubic.java and fib.java, how long would it take in (years, days, hours minutes, seconds) if we increase the number of times to do outer loop to
1. 1000
2. 10000
3. 100,000
4. 1000000 (a million) (The population of New Cross)
5. 10 million (The population of London)
6. 100 million (Twice the population of the UK)
7. 1000 million (billion) (A quarter of the population of China)
Calculate the time (to the nearest second) just for the last time round the loop - not all the previous executions of the loop. You might need to write a program to convert seconds into years, days, hours, minutes and second. Explain your answers.

Find out how long it will be until all life on Earth will cease to exist (Google is your friend)! This might be because the Sun gets too hot or too cold or some other horrible thing! For `fib.java` only go as far as this time. After all, there is no point in running the program when nobody is alive to see the output. i.e. do not do the calculations once you have reached the time when all life on Earth will ceased to exist. Just say it's impossible!

Put your results in a table.

Lab Exercise 3

```class Bubble2
{
static int[] A = new int [1000000];

static void Bubblesort(int [] a,  int N)
{
for (int i=N-1;i>0;i--)
for (int j=0;j<i;j++)
if (a[j] > a[j+1])
{
int temp = a[j+1];
a[j+1]=a[j];
a[j]=temp;
}

}

static void init()
{
for (int i=0;i<1000000;i++) A[i]=i;
}

static void print(int [] a,  int N)
{
for (int i=0;i<N;i++) System.out.println(a[i]);
}

public static void main (String [] args)
{
int i=Integer.parseInt(args[0]);
init();
long x=System.nanoTime()();
Bubblesort(A,i);
System.out.println(i+" "+(System.nanoTime()-x));
}
}
```

Run Bubble2 for a few different inputs

Lab Exercise 4
Run Bubble2 for a few different inputs but replace `Time.getUserTine` with `System.nanoTime()`. What is the difference? Why?

Lab Exercise 5
Change Bubble2 so it prints the time in milliseconds.

Lab Exercise 6
Work out how long Bubble2 would take to sort
lab1
1000 items
lab2
10000 items
lab3
100000 items
lab4
1000000 (million) items
lab5
10000000 (10 million) items

```class microseconds
{
static long million=1000000;

static String time(long micros)
{
long fractionsOfASecond=micros%million;
long seconds=micros/million;
long fractionsOfAMinute=seconds%60;
long minutes=seconds/60;
long fractionsOfAnHour=minutes%60;
long hours=minutes/60;
long days = hours/24;
long fractionOfAYear = days%365;
long years= days/365;
String s= years + " years " +
fractionOfAYear + " days " +
fractionsOfADay + " hours " +
fractionsOfAnHour + " minutes " +
fractionsOfAMinute + "." + fractionsOfASecond + "seconds";
return s;
}

public static void main( String[] args)
{
long micros=Long.parseLong(args[0]);
System.out.println(time(Math.round(0.65* micros * micros)));
}
}
```

Lab Exercise 7
What is the time complexity of Bubble2?

# Week 3: Searching (16 Oct 2014)

## Lab Exercises for Week 3

Lab Exercise 1
Try this:

```import java.util.Random;
class linearSearch
{
static final int N=10000;
static int [] bigArray = new int[N];

static boolean search(int n, int [] a)
{
boolean found=false;
for (int i=0;!found&&i<a.length;i++) found=(a[i]==n);
return found;
}

public static void main( String [] args)
{
Random r= new Random();
for (int i=0;i<bigArray.length;i++)
bigArray[i]=r.nextInt(2*N);
for (int i=0;i<1000;i++)
{int z=r.nextInt(2*N);
System.out.println(search(z,bigArray));
}
}
}
```
What is its time complexity?

Lab Exercise 2

```import java.util.Random;
class binarySearch
{
static final int N=10000;
static int [] bigArray = new int[N];

static void Bubblesort(int [] a,  int N)
{

for (int i=N-1;i>0;i--)
for (int j=0;j<i;j++)
if (a[j+1]< a[j])
{
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}

}

static boolean binarySearch(int s, int [] a) //assumes a is sorted in ascending order
{
int hi=a.length-1;
int lo=0;
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
if      (a[mid] > s) hi=mid;
else if (a[mid] < s) lo=mid+1;
else  return true;
}
return false;
}

public static void main( String [] args)
{
Random r= new Random();
for (int i=0;i<bigArray.length;i++)
bigArray[i]=r.nextInt(N);
Bubblesort(bigArray,N);
for (int i=0;i<100;i++)
{int z=r.nextInt(2*N);
System.out.println(binarySearch(z,bigArray));
}
}
}
```
1. Run the code `on paper' for an array of length 4
2. Does this code work for both odd and even length arrays? Test it out on some fixed arrays (without random numbers)
3. What happens if we make N=100000?
4. What happens if we make N=1000000?
5. Why?

Lab Exercise 3
Here is the text of The Old Curiosity Shop by Charles Dickens and here is a list of all English Words.
1. Which words in the book are not in the English language? Hint:
```import java.io.*;
import java.util.Scanner;

{

static String[] words = new String[650655];
static String[] dickens = new String[230000];

static boolean find(String s)
{
for (int i=0;i<650655;i++)
if (s.equals(words[i])) return true;
return false;

}

public static void main (String[] args) throws Exception
{
int j=0;
int x; String str="";

{
if (Character.isLetter((char)x))
{
str+=(char)x;
{
str+=(char)x;
}
dickens[j]=str.toLowerCase();
str="";
j++;
}
else
{  str="";
str+=(char)x;
}

}

Scanner s = new Scanner(new FileReader("words"));
String z =s.next();
int i=0;
while (s.hasNext())
{
words[i] =s.next();

i++;
}
for (int k=0;k<j;k++)
if (!find(dickens[k])) System.out.println(dickens[k]);
}

}
```
• Does it run out of memory on your computer? If so, try it on mango.
• This is very slow. Speed it up by doing a binary search. To do this you have to adapt my `binary search` method to work on arrays of Strings. You can use the java String method `compareTo` (look it up in the Java API). (Designated Exercise).
• Is it faster?
• It gives duplicates. How can we remove them. Solution:
```import java.io.*;
import java.util.Scanner;
import java.util.*;
{

...

public static void main (String[] args) throws Exception
{
int j=0;
int x; String str="";

HashSet <String> wordsInDickens=  new HashSet <String>(); //Declare a set to store words

{
if (Character.isLetter((char)x))
{
str+=(char)x;
{
str+=(char)x;
}
wordsInDickens.add(str.toLowerCase()); // Store words in a Set
str="";
j++;
}
else
{  str="";
str+=(char)x;
}

}

....

for (String w  : wordsInDickens)
if (!find(w)) System.out.println(w);

}

}
```

2. What is the most common word in the book?

Solution -Try this:

```import java.io.*;
import java.util.*;

class Pair
{
String [] first;
String []  second;

Pair(String [] t  , String [] u)
{
first=t;
second=u;
}
}

public   class commonWordInBook
{

static String [ ]  mergeSort(String[] a, HashMap <String,Integer> m)
{
if (a.length <=1) return a;
else {
Pair p = divide(a);
return merge(mergeSort(p.first,m),mergeSort(p.second,m),m);

}
}

static Pair  divide(String [] a)
{
int n= a.length/2;
String b[] = new String[n];
String  c[] = new String[a.length-n];
for (int i=0;i<n;i++)b[i]=a[i];
for (int i=0;i<a.length-n;i++)c[i]=a[n+ i];
return new Pair(b,c);
}

static  String [] merge(String [] b, String [] c, HashMap <String,Integer> m)
{
String a[] = new String[b.length+c.length];
int i=0,j=0,k=0;
while (i<b.length && j<c.length)
{
if (m.get(b[i]) >m.get(c[j])) {a[k]=b[i];i++;}
else {a[k]=c[j];j++;}
k++;
}

while(i<b.length) { a[k]=b[i];i++;k++;}
while(j<c.length) {a[k]=c[j];j++;k++;}

return a;
}

public static void main (String[] args) throws Exception
{
int j=0;
int x; String str="";
HashMap <String, Integer> m = new HashMap <String, Integer>();

{
if (Character.isLetter((char)x))
{
str+=(char)x;
{
str+=(char)x;
}
String t=str.toLowerCase();
if (m.keySet().contains(t))
{
int q = m.get(t);
m.put(t,q+1);
}
else m.put(t,1);
str="";
j++;
}
else
{  str="";
str+=(char)x;
}

}

String [] allWords=  new String [m.keySet().size()];
int i=0;
for (String k:m.keySet())
{
allWords[i]=k;
i++;
}
String [] result= mergeSort(allWords,m);
for ( i=0;i<result.length;i++)
System.out.println(result[i]+ " " + m.get(result[i]));
}

}
```

3. What is the most common letter in the book?

# Week 4: Merge Sort (23 Oct 2014)

Watch

```class Pair
{
int [] first;
int []  second;

Pair(int [] t  , int [] u)
{
first=t;
second=u;
}
}

public class mergeSort1{

static int [ ]  mergeSort(int[] a)
{
if (a.length <=1) return a;
else {
Pair p = divide(a);
return merge(mergeSort(p.first),mergeSort(p.second));

}
}

static Pair  divide(int [] a)
{
int n= a.length/2;
int b[] = new int[n];
int c[] = new int[a.length-n];
for (int i=0;i<n;i++)b[i]=a[i];
for (int i=0;i<a.length-n;i++)c[i]=a[n+ i];
return new Pair(b,c);
}

static  int [] merge(int [] b, int [] c)
{
int a[] = new int[b.length+c.length];
int i=0,j=0,k=0;
while (i<b.length && j<c.length)
{
if (b[i] <c[j]) {a[k]=b[i];i++;}
else {a[k]=c[j];j++;}
k++;
}

while(i<b.length) { a[k]=b[i];i++;k++;}
while(j<c.length) {a[k]=c[j];j++;k++;}

return a;
}

public static void main(String[] args)
{
int [] s = {-4,2};
int [] t = {-5,3,8};
int [] a  = mergeSort(t);
for (int i=0;i<a.length;i++)
System.out.println(a[i]);
}
}
```

## Lab Exercises for Week 4

Lab Exercise 1
Sort the students by exam mark using merge sort.
Lab Exercise 2
Sort the words in the Old Curiosity Shop in ascending alphabetical order using mergersort.
Lab Exercise 3
Here is some code to plot bubbleSort:
```import java.util.Random;
class bubble3
{

static int [] randFill(int n)
{
Random r = new Random();
int [] z = new int [n];
for (int i=0;i<n;i++) z[i]=r.nextInt(n);

return z;
}

static void Bubblesort(int [] a)
{
int N=a.length;
for (int i=N-1;i>0;i--)
for (int j=0;j<i;j++)
if (a[j] > a[j+1])
{
int temp = a[j+1];
a[j+1]=a[j];
a[j]=temp;
}

}

public static void main (String [] args)
{
for (int i=0;i<5000;i++)
{
int b[]=randFill(i);
long x=System.nanoTime();
Bubblesort(b);
System.out.println(i+" "+(System.nanoTime()-x));
}
}
}
```
1. Do the same for mergsort
2. Plot mergesort against bubblesort.
3. Find the equation of mergesort when run on your computer. (Designated exercise)
Lab Exercise 4
Adapt merge sort so it throws away duplicates.
Lab Exercise 5
Prove that the time complexity for merge sort is n log n.

## QuickSort

Watch http://youtu.be/-uCWuJ1Lhjc

```import java.util.*;
class Pair
{
ArrayList <Integer> first;
ArrayList <Integer>  second;

Pair(ArrayList <Integer> t  , ArrayList <Integer> u)
{
first=t;
second=u;
}
}

public class quickSort
{
static ArrayList <Integer>  quickSort(ArrayList <Integer> a)
{
if (a.size() <=1) return a;
else {
Pair p = divide(a);
ArrayList <Integer> b =quickSort(p.first);
return b;
}
}

static Pair  divide(ArrayList <Integer> a)
{
int pivot=a.get(0);
ArrayList <Integer> b  = new  ArrayList <Integer> ();
ArrayList <Integer> c  = new  ArrayList <Integer> ();
return new Pair(b,c);
}

public static void main(String[] args)
{
ArrayList <Integer> b  = new  ArrayList <Integer> ();
System.out.println(quickSort(b));
}
}
```

Sort the words in the Old Curiosity Shop in ascending alphabetical order using quicksort.

# Week 5 Hashing (30 Oct 2014)

Watch:

Study this code:

```import java.io.*;
import java.util.*;

public   class hash
{

static ArrayList <String> [] words = new ArrayList [670000];
static String[] dickens = new String[230000];
static int step=11;

static int hash(String s)
{
long result=0;
int val=1;
for (int i=0;i<s.length();i++)
{
result+=s.charAt(i)*val;
val*=step	;
}
int z= (int) (result  % 670000);
return z>=0?z:z+670000;
}

static boolean find(String s)
{
int k=hash(s);
ArrayList <String> a =words[k];
for (int i=0;i<a.size();i++)
if (s.equals(a.get(i))) return true;
return false;

}

public static void main (String[] args) throws Exception
{
System.out.println(hash("aaronsburg's"));
int j=0;
int x; String str="";

{
if (Character.isLetter((char)x))
{
str+=(char)x;
{
str+=(char)x;
}
dickens[j]=str.toLowerCase();
str="";
j++;
}
else
{  str="";
str+=(char)x;
}

}

for (int k=0;k<670000;k++) words[k]= new ArrayList <String> ();

Scanner s = new Scanner(new FileReader("words"));
int i=0;
while (s.hasNext())
{
String z =s.next();
i=hash(z);
// System.out.println(z+ " " +i);

}
for (int k=0;k<j;k++)
if (!find(dickens[k])) System.out.println(dickens[k]);

}

}
```

## Lab Exercises for Week 5

Lab Exercise 1
How long is the longset arrayList in `words`? (Designated exercise)
Lab Exercise 2
How many empty elements are there in `words`?
Lab Exercise 3
What happens if we change `step` to 13,17,19,23? Do we end up with more or fewer collisions?
Lab Exercise 4
How would we change the data structure if we wanted definitions for every word in the dictionary?

# Week 6 Reading Week (6 Nov 2014)

Sort the words in the Old Curiosity Shop in ascending alphabetical order using quicksort.

1. A man puts one grain of rice on a square of a chess board, twice as many on the next etc. There are 64 squares on a chess board. How many grains of rice will be on the 64th square of the chess board?
1. less than 10 million
2. None of the above.

A man puts one grain of rice on a square of a chess board, twice as many on the next etc. There are 64 squares on a chess board. The number of atoms in the observable universe is about . Which of the following is true?

1. There are more grains of rice on the 64th square than the number of atoms in the observable universe.
2. There are more atoms in the observable universe than grains of rice on the 64th square.
3. There are exactly the same number of atoms in the observable universe as grains of rice on all the squares.
4. None of the above.

2. A telephone directory of a large town has 10 million entries. If it takes 1 second to look at each entry, how long in the worst case would it take to find Sebastian Danicic's telephone number if the directory is not sorted?

1. Less than one minute
2. Between one minute and two days
3. Between two days and a week
4. More than a week

3. A telephone directory of a large town has 10 million entries. If it takes 1 second to look at each entry, how long in the worst case would it take to find Sebastian Danicic's telephone number if the directory is sorted and we use a binary search?
1. Less than one minute
2. Between one minute and two days
3. Between two days and a week
4. More than a week

4. Considering is approximately 1000, and a million is a . Then is approximately:
1. A million, million
2. A million, million, million
3. A million, million, million, million
4. A million, million, million, million, million

5. In a game of chess there are about 30 legal moves in every position. A typical game of chess lasts about 40 moves. A game of chess is a sequence of moves. Roughly, how many different (40 move) games of chess are there?

6. Let Which of the following is true:
1. None of the above.

7. Which of the following functions will produce the largest values (asymptotically) as gets bigger:
1. None of the above.

8. The worst-case time complexity of Bubble sort is
1. None of the above.

9. The worst-case time complexity of merge sort is
1. None of the above.

10. If it take 5 nanoseconds to sort 10 elements using Bubble sort, roughly how long will it take to sort 20 elements?

1. 10 nanoseconds
2. 20 nanoseconds
3. 30 nanoseconds
4. None of the above.

11. What is the time-complexity of this function in terms of N?
```int f(int N)
{
int total=0;
for (int i=0;i<N;i++)
for (int j=0;j<N;j++)
total=total+i+j;
}
```

1. linear
3. exponential
4. None of the above.

12. What is the time-complexity of this function in terms of N?
```int f(int N)
{
if (N<2) return 1;

return f(N-1)+f(N-2);
}
```

1. linear
3. exponential
4. None of the above.

13. Here are two methods for computing :
```static int powerA(int x, int n)
{
int total=1;
while (n>0) {total=total*x;n--;}
}

static int powerB(int x, int n)
{
if (n==0) return 1;
int k=n/2;
int z=powerB(x,k);
int r=z*z;
if (n%2==0) return r;
return x*r;

}
```
Which one of the following is true
1. `powerA` is linear and `powerB` has quadratic time-complexity.
2. `powerA` is exponential and `powerB` has log(N) time-complexity.
3. `powerA` is quadratic and `powerB` has exponential time-complexity.
4. None of the above.

14. Here are two methods for computing :
```static int powerA(int x, int n)
{
int total=1;
while (n>0) {total=total*x;n--;}
}

static int powerB(int x, int n)
{
if (n==0) return 1;
int k=n/2;
int z=powerB(x,k);
int r=z*z;
if (n%2==0) return r;
return x*r;

}
```
Which one of the following is true
1. `powerA` is more efficient than `powerB`.
2. `powerB` is more efficient than `powerA`.
3. `powerB` has the same efficiency as `powerA`.
4. None of the above.

# Week 7 Introduction to Graphs (13 November 2014)

My introduction to Graphs and their application: http://youtu.be/ob-CjXjKpYk

See

## Lab Exercises for Week 7 (coursework 6)

1. Consider the following adjacency matrix of a graph:
```int [] [] a = {{1,0,0,1},{1,0,0,1},{1,1,0,0},{1,0,1,0}}
```
Draw a picture of the graph assuming the vertices are labelled 0-3.

2. Consider the following weighted directed graph

What is the length of the shortest path (in terms of distance) from 0 to 3?

3. Consider the following directed graph:

Write down a adjacency matrix representing it?

4. Consider the following directed graph

How many paths are there from 0 to 2?

5. Consider the following weighted directed graph

Is there a shortest path (in terms of distance) from 0 to 1?

6. Consider the following Java program
```import java.util.HashSet;
class it1
{

static HashSet <Integer> f (double [][] graph, int i)
{
HashSet <Integer> K= new HashSet <Integer>();
for (int j=0;j<graph.length;j++)
return K;
}
}
```
If `a` was the adjacency matrix representing the graph:

What would the output of executing the statement

```System.out.println(f(a,3))?
```
(Designated Exercise)

# Week 8: Finding Shortest Paths in Unweighted Graphs (breadth first search) (20 Novemver 2014)

```import java.util.HashSet;
import java.util.ArrayList;

public  class graph
{

graph (double [] [] a)
{
for (int i=0;i<a.length;i++)
for (int j=0;j<a.length;j++)
}

public HashSet <Integer> neighbours(int v)
{
HashSet <Integer> h = new HashSet <Integer> () ;
return h;
}

public  HashSet <Integer> vertices()
{
HashSet <Integer> h = new HashSet <Integer>();
return h;
}

ArrayList <Integer> addToEnd (int i, ArrayList <Integer> path) // returns a new path with i at the end of path
{
ArrayList <Integer> k;
k=(ArrayList<Integer>)path.clone();
return k;
}

public  HashSet <ArrayList <Integer>> shortestPaths1(HashSet <ArrayList <Integer>> sofar,  HashSet <Integer> visited, int end)
{

HashSet <ArrayList <Integer>> more = new HashSet <ArrayList <Integer>>();
HashSet <ArrayList <Integer>> result = new HashSet <ArrayList <Integer>>();
HashSet <Integer> newVisited = (HashSet <Integer>) visited.clone();
boolean done = false;
boolean carryon = false;
for   (ArrayList <Integer> p: sofar)
{
for (Integer z: neighbours(p.get(p.size()-1)))
{

if (!visited.contains(z))
{
carryon=true;
}
}
}
if (done) return result;
else
if (carryon) return shortestPaths1(more,newVisited,end);
else return new HashSet <ArrayList <Integer>>();
}

public  HashSet <ArrayList <Integer>> shortestPaths( int first, int end)
{
HashSet <ArrayList <Integer>> sofar = new HashSet <ArrayList <Integer>>();
HashSet <Integer> visited = new HashSet <Integer>();
ArrayList <Integer> starting = new ArrayList <Integer>();
if (first==end) return sofar;
return shortestPaths1(sofar,visited,end);
}

public static void main(String [] args)
{
double [ ] [] a = {
{0.0, 1.0, 1.0, 0.0},
{0.0, 0.0, 1.0, 1.0},
{0.0, 1.0, 0.0, 1.0},
{0.0, 1.0, 1.0, 0.0}
};
graph g = new graph(a);

for (int i=0;i<a.length;i++)
{for (int j=0;j<a.length;j++)
if (i!=j) System.out.println(i + " to " + j +": "+g.shortestPaths(i,j));
// System.out.println(g.cycles(i));
}

}
}
```

# The London Underground System

(See The London Tube Map)

Study the following files of data about the London Underground System:

• Some information about the stations: stations
```"id","latitude","longitude","name","display_name","zone","total_lines","rail"
```
Only the first four fields of every line will be used in this assignment. The last four are not needed.
```Only the first two fields of every line will be used in this assignment.
```
For example the first line 11,163,1 means that station 11 (Baker Street) and 163 (Marylebone) are adjacent. (Ignore the 1!)

Play with the following program:

```import java.io.*;
import java.util.Scanner;
import java.util.*;
class underground
{
static int N= 500;
static   double [][] edges = new double[N][N];
static TreeMap <Integer,String> stationNames = new TreeMap <Integer,String>();

static ArrayList<String> convert (ArrayList<Integer> m)
{
ArrayList<String> z= new ArrayList<String>();
return z;
}

static HashSet<ArrayList<String>> convert (HashSet<ArrayList<Integer>> paths)
{
HashSet <ArrayList <String>> k= new HashSet <ArrayList <String>>();
return k;
}

public static void main(String[] args) throws Exception
{
for(int i=0;i<N;i++)for(int j=0;j<N;j++) edges[i][j]=0.0;
Scanner s = new Scanner(new FileReader("edges"));
String z =s.nextLine();
while (s.hasNext())
{
z =s.nextLine();
String[] results = z.split(",");
edges[Integer.parseInt(results[0])][Integer.parseInt(results[1])]=1.0;
edges[Integer.parseInt(results[1])][Integer.parseInt(results[0])]=1.0;
}
z =s.nextLine();
while (s.hasNext())
{
z =s.nextLine();
String[] results = z.split(",");
stationNames.put(Integer.parseInt(results[0]),results[3]);
}

graph G= new graph (edges);
int st = Integer.parseInt(args[0]);
int fin = Integer.parseInt(args[1]);
System.out.println("Shortest path from "  +  stationNames.get(st) + "  to " + stationNames.get(fin)  + " is " + convert(G.shortestPaths(st,fin)));

}
}
```

(Note: These files are slightly out-of date. Some of the latest stations on the map are not in the file. Please just use the files given.)

## Lab Exercises for Week 8 (coursework 7)

1. A cycle (in a directed graph) starting from vertex v is a path of length greater than 1 which ends at v. Write a method

```public  HashSet <ArrayList <Integer>> cycles( Integer start)
```

for finding the set of shortest cycles from any vertex v. (Adapt `shortestPaths`) (Designated Exercise.)

2. Given the class `graph` above, write a method, which returns the set of all isolated vertices in the graph. An non-isolated vertex is one with at least one neighbours.

3. Play with the Underground Program

# Week 9 Dijkstra's Algorithm (Finding a Shortest Path in a weighted Graph) (27 November 2014)

Study Dijkstra's algorithm MIT Lecture 17 Video.

Here is my pseudo code for Dijkstra's Algorithm to find a shortest path from `start` to `end`:

```Set S = {start}; //S is the set of vertices to whom the shortest paths from start have already been found

HashMap <Integer,Double> Q = Map each Vertex to Infinity (Double.POSITIVE_INFINITY), except map start -> 0;
// Q.get(i) represents the shortest distance found from start to i found so far

ArrayList <Integer> []  paths;
For each i set path[i] to be the path just containing start.

while (Q is not empty)
{
let v be the key of Q with the smallest value;
//I've given you a method int findSmallest(HashMap <Integer,Double> t) for this
if (v is end and Q does not map v to infinitity) return paths[end];
let w be the value of v in Q;
for (each neighbour u of v) do
{
if (u  not in S)
{
let w1 be the the weight of the (v,u) edge + w;
if w1 < the value of u in Q, then do the following:
{
update Q so now the value of u is w1
update paths(u) to be paths(v) with u stuck on the end
}
}
remove v from Q;
}
}
```

## Lab Exercises for Week 9 (coursework 8)

1. Implement Dijkstra's Algorithm using my pseudo-code. i.e. put a function `dijkstra` into the `graph` class.

Here are some hints:

```int findSmallest(HashMap <Integer,Double> t)
{
Object [] things= t.keySet().toArray();
double val=t.get(things[0]);
int least=(int) things[0];
Set <Integer> k = t.keySet();
for (Integer i : k)
{
if (t.get(i) < val) {least=i; val=t.get(i);}
}
return least;

}
```

Fill in these bits:

``` public  ArrayList <Integer> dijkstra (int start, int end)
{
int N= ...;
HashMap <Integer,Double> Q = new HashMap <Integer,Double>();

ArrayList <Integer> [] paths = new ArrayList [N];
for (int i=0;i<N;i++)
{
Q.put(i,...);
paths[i]=new ArrayList <Integer>();
paths[i].....;
}
HashSet <Integer> S= new HashSet();
Q.put(start,....);
while (!Q.isEmpty())
{
int v = findSmallest(...);
if (v==end && ...) return ....;
double w = Q.get(...);
for(int u: neighbours(v))
if (...)
{
double w1= ....;
if (w1 < Q.get(u))
{
Q.put(u,...);
}
}
Q.remove(...);
}
return new ArrayList <Integer> ();
}
```

Test your implementation using the following test program

```class testDijk
{
public static void main(String [] args) throws Exception
{
int N=1000;
double edges[][]=new double[N][N];

for(int i=0;i<N;i++)for(int j=0;j<N;j++) edges[i][j]=0.0;
Scanner s = new Scanner(new FileReader("randomGraph"));
String z;
while (s.hasNext())
{
z =s.nextLine();
String[] results = z.split(",");
edges[Integer.parseInt(results[0])][Integer.parseInt(results[1])]=Double.parseDouble(results[2]);
}

graph G= new graph (edges);
System.out.println(G.dijkstra(Integer.parseInt(args[0]),Integer.parseInt(args[1])));
}
}
```

Use this randomGraph file.

When I run

`java testDijk 0 999`

I get,

`[0, 492, 665, 114, 452, 999]`

Do you?

(Designated Exercise)

2. What is the time complexity of Dijkstra's Algortihm.

## Lab Exercises for Week 10 (coursework 9)

1. Write a method for computing the length of a path. Find all the pairs of stations in the London underground system where the shortest path between them in terms of distance has more stations the the shortest path in terms of number of stations.

You will have to use the following method:

```static double realDistance(double lat1, double lon1, double lat2, double lon2)
{

int R = 6371; // km (change this constant to get miles)
double dLat = (lat2-lat1) * Math.PI / 180;
double dLon = (lon2-lon1) * Math.PI / 180;
double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(lat1 * Math.PI / 180 ) * Math.cos(lat2 * Math.PI / 180 ) *
Math.sin(dLon/2) * Math.sin(dLon/2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
double d = R * c;
return d;

}
```
For finding the distance in Km between any two points on the Earth's surface with given latitude and longitude. The latitude and longitude of each station is given in the stations file. You will have to use this to compute the adjacentcy matrix for the weighted graph representation of the underground map. We need the ad[i][j] to be the distance from station i to station j now.

(Designated Exercise)

# Weeks 10 and 11: Functional Programming in Scala (4 and 7 Dec 2014)

In order to learn more about Lists we are going to use a new language called Scala. Scala is based on Java. There seem to be some good jobs in Scala at the moment! Please install Scala on your computer. If you can't manage it the usen Scala on mango.doc.gold.ac.uk. https://www.coursera.org/course/progfun Please read through: http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html

We usually give Scala programs the .scala extension.

To compile a Scala program type

```scalac one.scala
```

and to run it type

```scala one
```

Here is an example Scala program

```object HelloWorld
{
def main(args: Array[String])
{
System.out.println("Hello, world!")
}
}
```

Now look at this example:

```object add2 {

{
x+y
}

def main(args: Array[String])
{
}
}
```

The Scala function heading: `def add(x:Int,y:Int):Int` is equivalent to ` int add(int x, int y):Int` in Java. -`x+y` in Scala is equivalent to `return x+y` in Java. Notice the equal sign. We must have this if the function returns something. We do not have `void` in Scala. We just have no return type and no equals sign.

So the same program in Java would be:

```class add2 {

static int add(int x, int y)
{
return x+y
}

public static void main(String [] args)
{
}
}
```

### Declaring Variables

```class add2 {

static int add(int x, int y)
{
return x+y
}

public static void main(String [] args)
{
int a=5;
int b=3;
}
}
```

In Scala is:

```object add2 {

{
x+y
}

def main(args: Array[String])
{
var a:Int=5
var b:Int=3
}
}
```

Notice in Scala we write `x:Int`instead of `int x` as we do in Java. Also the return type of the function is written following the parameter list after a colon.

## Playing with Lists

1. try:
```object list1
{
def main(args:Array[String])
{
var k:List[Int]=Nil
println(k)
println(1::k)
println(1::2::Nil)
println((1::2::Nil).tail)
println((1::2::Nil).tail.tail)
println((1::2::3::3::2::Nil).length)
var s:List[String]= List("aaa","bbb");
println(s);
}
}
```

2. try:
```object list3
{
def main(args:Array[String])
{
println(Nil.tail);
}
}
```
This crashes. Why?

3. So does:
```object list4
{
def main(args:Array[String])
{
}
}
```

```object list4
{
def main(args:Array[String])
{
println((x::Nil).tail.tail);
}
}
```
why?

5. try
```object list5
{
def main(args:Array[String])
{
println(Nil.isEmpty);
}
}
```

## Defining your own Functions on Lists

1. try
```object list6
{
def main(args:Array[String])
{
println((1::Nil).isEmpty);
}
}
```

2. Try:
```object list7
{
def double(k:List[Int]):List[Int]=
{
if (k.isEmpty) Nil
}

def main(args:Array[String])
{
println(double(List(2,3,4,1)));
}
}
```

3. Try:
```object list8
{
def double(k:List[Int]):List[Int]=
{
if (k.isEmpty) Nil

}

def treble(k:List[Int]):List[Int]=
{
if (k.isEmpty) Nil
}
def main(args:Array[String])
{

println(double(List(2,3,4,1)));
println(treble(List(2,3,4,1)));
println(treble(double(List(2,3,4,1))));
println(double(treble(List(2,3,4,1))));
}
}
```

## Anonymous functions

try things like:

```scala> ((x:Int) => 2*x)(3)
res3: Int = 6

scala> ((x:String) => x.length()+1)("hello")
res4: Int = 6

scala> ((x:String) => x.length()+1)("goodby")
res5: Int = 7

^

scala> ((x:Int,y:String) => y.length()+y)(3,"goodbye")
res7: String = 7goodbye

scala> ((x:Int,y:String) => y.length()+x)(3,"goodbye")
res8: Int = 10
```

## Now the power! Higher Order Functions

1. ```object list21
{

def map(k:List[Int], f: Int => Int):List[Int]=
{
if (k.isEmpty) Nil
}

def main(args:Array[String])
{
println(map(List(2,3,4,1), (y:Int) => 2*y));
}
}
```

2. Even more powerful:
```class mappy [T,U]
{
def map [T,U] (k:List[T], f: T => U):List[U]=
{
if (k.isEmpty) Nil
}
}
```

```object list31
{
def main(args:Array[String])
{
println(new mappy [Int,Int].map(List(2,3,4,1), (y:Int) => 2*y));
println(new mappy [String,Int].map(List("hello","Sebastian","how", "are", "you"), (y:String) => (y.length())));
println(new mappy [String,Int].map(List("hello","Sebastian","how", "are", "you"), (y:String) => (y.charAt(0))));
println(new mappy [String,String].map(List("hello","Sebastian","how", "are", "you"), (y:String) => (y.substring(1,3))));
}
}
```

## Calling Scala from Java

```class mappy [T,U]
{

def map [T,U] (k:List[T], f: T => U):List[U]=
{
if (k.isEmpty) Nil
}

def map [T:ClassManifest,U:ClassManifest] (k:Array[T], f: T => U):Array[U]=
{
var z=k.toList;
val x= map(z,f);
x.toArray;
}

map(a,(y:Int)=>x+y)

}
```

```class test

{
public static void main (String [] args)
{
int [] a ={1,2,3};
mappy <Integer,Integer> m = new mappy <Integer,Integer>();
for (int i=0;i<b.length;i++) System.out.println(b[i]);
}

}

javac -cp /usr/share/java/scala-library.jar:. test.java
java -cp /usr/share/java/scala-library.jar:. test
```

## MergeSort in Scala

mergeSort.scala:

```class mergeSort [T] {

def first[T] (k:List[T],n:Int):List[T]=
if (k.isEmpty || n==0) Nil

def remaining[T] (k:List[T],n:Int):List[T]=
if (k.isEmpty || n==0) k
else remaining(k.tail,n-1);

def merge [T](k1:List[T],k2:List[T],p:(T,T) => Boolean):List[T]=
if (k1.isEmpty) k2
else if (k2.isEmpty) k1

def mergeSort [T](m:List[T],p:(T,T)=> Boolean):List[T]=
{
val z= m.length/2
if (m.length<2) m
else merge(mergeSort(first(m,z),p),mergeSort(remaining(m,z),p),p)
}

def ascendMergsSortInt(m:Array[Int]):Array[Int]=
{
var z = m.toList;
mergeSort(z,(i:Int,j:Int) => i<j).toArray
}

}
```

list2.java:

```import java.util.Random;
class list2
{
static final int N=1000000;

public static void main(String[] args)
{
Random r = new Random();
int [] a = new int[N];
for (int i=0;i<a.length;i++) a[i]=r.nextInt(1000000);
mergeSort <Integer> m = new mergeSort <Integer>();

a=m.ascendMergsSortInt(a);
for (int i=0;i<a.length;i++) System.out.println(a[i]);

}
}
```

Compile the scala program:

```scalac mergeSort.scala
```

compile the java program:

```javac -cp /usr/share/java/scala-library.jar:. list2.java
```

run the java program:

```java -Xss35m -cp .:/usr/share/java/scala-library.jar:. list2
```

## Lab Exercises for Week 11

Lab Exercise 1
Write a function for finding the longest list in a list of lists.
Lab Exercise 2
Write a function for converting a String of characters into a list.
Lab Exercise 3
Write a function which returns the revere of a list. (Hint:To reverse a non-empty list, we reverse the tail and stick the head on the other end.)
Lab Exercise 4
Write a function using the above which checks whether a String is a palindrome.
Lab Exercise 5
Find a list of all the palindromes in the English language. (Designated Exercise)
Lab Exercise 6
What is the longest palindrome?
Lab Exercise 7
Write a function which finds a list of all permutations of a String. Remove duplicates.
Lab Exercise 8
Write a function which returns the list of students who got an 'A'. ( A mark of 70 or over). Sort the list in descending order of mark.

s.danicic@gold.ac.uk
Sebastian Danicic BSc MSc PhD (Reader in Computer Science)
Dept of Computing, Goldsmiths, University of London, London SE14 6NW
Last updated 2014-12-04