The marks for lateness are as is follows:
| 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 |
Algorithms are Taking over the World
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);
}
}
java Bubble1 25 6 3 2
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++;
}
}
}
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"));
}
}
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"
Watch My video: How to time Java programs with quadratic time complexity and plot the curve continued ....
Watch My video: How to time Java programs with quadratic time complexity and plot the curve continued ....
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;
return total;
}
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 set output "plotQuad.png" plot "outQuad",0.75*x*x
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.
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;
return total;
}
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.
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" plot "outQuad",(2**x)*0.00017
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.
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.
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!
Choose either your machine, igor or mango to do your experiments.
Put your results in a table.
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
Time.getUserTine with System.nanoTime().
What is the difference? Why?
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 fractionsOfADay=hours%24;
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)));
}
}
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?
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));
}
}
}
import java.io.*;
import java.util.Scanner;
public class readCuriosity
{
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;
BufferedReader b = new BufferedReader(new FileReader("pg700.txt"));
int x; String str="";
while ((x=b.read())!=-1)
{
if (Character.isLetter((char)x))
{
str+=(char)x;
while ((x=b.read())!=-1 && Character.isLetter((char)x))
{
str+=(char)x;
}
dickens[j]=str.toLowerCase();
str="";
j++;
}
else
{ str="";
while ((x=b.read())!=-1 && !Character.isLetter((char)x));
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]);
}
}
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).
import java.io.*;
import java.util.Scanner;
import java.util.*;
public class readCuriosityNoDuplicate
{
...
public static void main (String[] args) throws Exception
{
int j=0;
BufferedReader b = new BufferedReader(new FileReader("pg700.txt"));
int x; String str="";
HashSet <String> wordsInDickens= new HashSet <String>(); //Declare a set to store words
while ((x=b.read())!=-1)
{
if (Character.isLetter((char)x))
{
str+=(char)x;
while ((x=b.read())!=-1 && Character.isLetter((char)x))
{
str+=(char)x;
}
wordsInDickens.add(str.toLowerCase()); // Store words in a Set
str="";
j++;
}
else
{ str="";
while ((x=b.read())!=-1 && !Character.isLetter((char)x));
str+=(char)x;
}
}
....
for (String w : wordsInDickens)
if (!find(w)) System.out.println(w);
}
}
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;
BufferedReader b = new BufferedReader(new FileReader("pg700.txt"));
int x; String str="";
HashMap <String, Integer> m = new HashMap <String, Integer>();
while ((x=b.read())!=-1)
{
if (Character.isLetter((char)x))
{
str+=(char)x;
while ((x=b.read())!=-1 && Character.isLetter((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="";
while ((x=b.read())!=-1 && !Character.isLetter((char)x));
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]));
}
}
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]);
}
}
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));
}
}
}
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);
b.add(a.get(0));
b.addAll(quickSort(p.second));
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> ();
for (int i=1;i<a.size();i++) if (a.get(i) < pivot) b.add(a.get(i)); else c.add(a.get(i));
return new Pair(b,c);
}
public static void main(String[] args)
{
ArrayList <Integer> b = new ArrayList <Integer> ();
for( int i=0;i<args.length;i++) b.add(Integer.parseInt(args[i]));
System.out.println(quickSort(b));
}
}
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;
BufferedReader b = new BufferedReader(new FileReader("pg700.txt"));
int x; String str="";
while ((x=b.read())!=-1)
{
if (Character.isLetter((char)x))
{
str+=(char)x;
while ((x=b.read())!=-1 && Character.isLetter((char)x))
{
str+=(char)x;
}
dickens[j]=str.toLowerCase();
str="";
j++;
}
else
{ str="";
while ((x=b.read())!=-1 && !Character.isLetter((char)x));
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);
words[i].add(z);
}
for (int k=0;k<j;k++)
if (!find(dickens[k])) System.out.println(dickens[k]);
}
}
words? (Designated exercise)
words?
step to 13,17,19,23?
Do we end up with more or fewer collisions?
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?
is approximately 1000, and a million is a 
.
Then is approximately:
Which of the following is true:
gets bigger:
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;
return total;
}
int f(int N)
{
if (N<2) return 1;
return f(N-1)+f(N-2);
}
:
static int powerA(int x, int n)
{
int total=1;
while (n>0) {total=total*x;n--;}
return total;
}
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
powerA is linear and powerB has quadratic time-complexity.
powerA is exponential and powerB has log(N) time-complexity.
powerA is quadratic and powerB has exponential time-complexity.
:
static int powerA(int x, int n)
{
int total=1;
while (n>0) {total=total*x;n--;}
return total;
}
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
powerA is more efficient than powerB.
powerB is more efficient than powerA.
powerB has the same efficiency as powerA.
See
My video on implementing graphs in java
My shortest paths algorithm in Java
My shortest paths algorithm in Java...continued
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.
What is the length of the shortest path (in terms of distance) from 0 to 3?
Write down a adjacency matrix representing it?
How many paths are there from 0 to 2?
Is there a shortest path (in terms of distance) from 0 to 1?
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++)
if (graph[i][j]>0) K.add(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)
import java.util.HashSet;
import java.util.ArrayList;
public class graph
{
double [] [] adj;
graph (double [] [] a)
{
adj= new double [a.length][a.length];
for (int i=0;i<a.length;i++)
for (int j=0;j<a.length;j++)
adj[i][j]=a[i][j];
}
public HashSet <Integer> neighbours(int v)
{
HashSet <Integer> h = new HashSet <Integer> () ;
for (int i=0;i<adj.length;i++) if (adj[v][i]!=0) h.add(i);
return h;
}
public HashSet <Integer> vertices()
{
HashSet <Integer> h = new HashSet <Integer>();
for (int i=0;i<adj.length;i++) h.add(i);
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();
k.add(i);
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;
newVisited.add(z);
if (z==end) {done=true; result.add(addToEnd(z,p));}
else more.add(addToEnd(z,p));
}
}
}
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>();
starting.add(first);
sofar.add(starting);
if (first==end) return sofar;
visited.add(first);
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));
}
}
}
Study the following files of data about the London Underground System:
"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>();
for (Integer i:m) z.add(stationNames.get(i));
return z;
}
static HashSet<ArrayList<String>> convert (HashSet<ArrayList<Integer>> paths)
{
HashSet <ArrayList <String>> k= new HashSet <ArrayList <String>>();
for (ArrayList <Integer> p:paths) k.add(convert(p));
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;
}
s = new Scanner(new FileReader("stations"));
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)));
}
}
public HashSet <ArrayList <Integer>> cycles( Integer start)
for finding the set of shortest cycles from any vertex v.
(Adapt shortestPaths) (Designated Exercise.)
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.
Watch Dijkstra's Algorithm and Dijkstra's Algorithm again!
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;
add v to S;
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;
}
}
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();
S.add(...);
Q.put(start,....);
while (!Q.isEmpty())
{
int v = findSmallest(...);
if (v==end && ...) return ....;
double w = Q.get(...);
S.add(...);
for(int u: neighbours(v))
if (...)
{
double w1= ....;
if (w1 < Q.get(u))
{
Q.put(u,...);
paths[u]= addToEnd(...);
}
}
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)
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)
Also see http://www.scala-lang.org/documentation/. http://www.scala-lang.org/docu/files/ScalaByExample.pdf
http://www.codecommit.com/blog/scala/roundup-scala-for-java-refugees
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 {
def add(x:Int,y:Int):Int=
{
x+y
}
def main(args: Array[String])
{
System.out.println(add(1,2))
}
}
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)
{
System.out.println(add(1,2))
}
}
class add2 {
static int add(int x, int y)
{
return x+y
}
public static void main(String [] args)
{
int a=5;
int b=3;
System.out.println(add(a,b))
}
}
In Scala is:
object add2 {
def add(x:Int,y:Int):Int=
{
x+y
}
def main(args: Array[String])
{
var a:Int=5
var b:Int=3
System.out.println(add(a,b))
}
}
Notice in Scala we write x:Intinstead of int x as we do in Java.
Also the return type of the function is written following the parameter list after a colon.
http://www.tutorialspoint.com/scala/scala_lists.htm
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).head)
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);
println(s.tail.head);
}
}
object list3
{
def main(args:Array[String])
{
println(Nil.tail);
}
}
This crashes. Why?
object list4
{
def main(args:Array[String])
{
println(Nil.head);
}
}
object list4
{
def main(args:Array[String])
{
println((x::Nil).tail.tail);
}
}
why?
object list5
{
def main(args:Array[String])
{
println(Nil.isEmpty);
}
}
object list6
{
def main(args:Array[String])
{
println((1::Nil).isEmpty);
}
}
object list7
{
def double(k:List[Int]):List[Int]=
{
if (k.isEmpty) Nil
else 2*k.head::double(k.tail)
}
def main(args:Array[String])
{
println(double(List(2,3,4,1)));
}
}
object list8
{
def double(k:List[Int]):List[Int]=
{
if (k.isEmpty) Nil
else 2*k.head::double(k.tail)
}
def treble(k:List[Int]):List[Int]=
{
if (k.isEmpty) Nil
else 3*k.head::treble(k.tail)
}
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))));
}
}
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
object list21
{
def map(k:List[Int], f: Int => Int):List[Int]=
{
if (k.isEmpty) Nil
else f(k.head)::map(k.tail,f)
}
def main(args:Array[String])
{
println(map(List(2,3,4,1), (y:Int) => 2*y));
}
}
class mappy [T,U]
{
def map [T,U] (k:List[T], f: T => U):List[U]=
{
if (k.isEmpty) Nil
else f(k.head)::map(k.tail,f)
}
}
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))));
}
}
class mappy [T,U]
{
def map [T,U] (k:List[T], f: T => U):List[U]=
{
if (k.isEmpty) Nil
else f(k.head)::map(k.tail,f)
}
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;
}
def mapAddxToArray(a:Array[Int],x:Int):Array[Int]=
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>();
int [] b =m.mapAddxToArray(a,5);
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.scala:
class mergeSort [T] {
def first[T] (k:List[T],n:Int):List[T]=
if (k.isEmpty || n==0) Nil
else k.head :: first(k.tail,n-1);
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
else if ( p(k1.head, k2.head)) k1.head :: merge(k1.tail,k2,p)
else k2.head :: merge(k1,k2.tail,p)
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