Difference between revisions of "SET08112"

From Progzoo
Jump to: navigation, search
(→‎Problem 3 - Who's missing?)
 
(15 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
==SET08112 ArrayList Interface Tutorial==
+
==SET08112 - Algorithms and Data Structure==
−
In this tutorial you will use the ArrayList and the HashMap or TreeMap to solve some common problems.
+
*[[ArrayList Tutorial]]
−
You will use methods such as:
+
*[[Recursion Tutorial]]
−
* java.util.Collections.sort
+
*[[Finite State Machines Tutorial]] and [[Finite State Machine|FSM from lecture]]
−
* add
+
*[[Assessment 2011 Tornado]]
−
* get
+
*[[Recursive Descent Parsers]]
−
 
+
*[[Tree Tutorial]]
−
==Problem 1 - Sort a List==
+
−
<question className="SortStudents" title="Using Sort" copyfile="students.txt">
+
−
The file  from http://www.dcs.napier.ac.uk/~cs66/SET08112/tut2/students.txt  contains a list of students:
+
−
ADAMS, ROBERT
+
−
HASTIE, MARTIN
+
−
OTHIENO, JUDITH
+
−
ANDERSON, ROSS
+
−
...
+
−
Create a programme SortStudents.java that reads in this file and outputs the students in Alphabetical order.
+
−
*You can use an ArrayList to hold the students.
+
−
*ArrayList&lt;String> names = new ArrayList&lt;String>();
+
−
*You can use [http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#sort%28java.util.List%29 java.util.Collections.sort] to sort the ArrayList  
+
−
<hint>
+
−
Add this line after you have filled the ArrayList but before you print it.
+
−
java.util.Collections.sort(names);
+
−
</hint>
+
−
<prog>
+
−
import java.util.ArrayList;
+
−
import java.io.BufferedReader;
+
−
import java.io.FileReader;
+
−
+
−
public class SortStudents{
+
−
  public static void main(String[]argv) throws Exception{
+
−
    ArrayList&lt;String> names = new ArrayList&lt;String>();
+
−
    String line;
+
−
    BufferedReader fh
+
−
      = new BufferedReader(new FileReader("students.txt"));
+
−
    while (null!=(line=fh.readLine()))
+
−
      names.add(line);
+
−
    for (String s:names)
+
−
      System.out.println(s);
+
−
  }
+
−
}
+
−
</prog>
+
−
<answer>
+
−
import java.util.ArrayList;
+
−
import java.io.BufferedReader;
+
−
import java.io.FileReader;
+
−
+
−
public class SortStudents{
+
−
  public static void main(String[]argv) throws Exception{
+
−
    ArrayList&lt;String> names = new ArrayList&lt;String>();
+
−
    String line;
+
−
BufferedReader fh
+
−
= new BufferedReader(new FileReader("students.txt"));
+
−
    while (null!=(line=fh.readLine()))
+
−
      names.add(line);
+
−
    java.util.Collections.sort(names);
+
−
    for (String s:names)
+
−
      System.out.println(s);
+
−
  }
+
−
}
+
−
</answer>
+
−
</question>
+
−
 
+
−
==Problem 2 - List Routes==
+
−
<question className="SortStudents" title="Using Sort" copyfile="year1.txt">
+
−
The file year1.txt contains a list of all students in year one. Each line contains the name of the student and the name of the route (programme) they follow separated by a tab.
+
−
Brando, Marlon BSC (HONS) DIGITAL MEDIA F/T
+
−
Bridges, Jeff BSC (HONS) INTERACTIVE MEDIA DESIGN F/T
+
−
Brody, Adrien BENG (HONS) COMPUTER SECURITY AND FORENSICS F/T
+
−
 
+
−
Write a program to read in this file and output a list of routes with no duplicates.
+
−
You can use a program very similar to the one above – but this time:
+
−
*Use <code>line.split("\t")</code> to get the route
+
−
*Use <code>name.contains(st[1])</code> to add the route '''only''' if it is not already in the ArrayList
+
−
*You do not need to sort before output
+
−
 
+
−
<prog>
+
−
import java.util.ArrayList;
+
−
import java.io.BufferedReader;
+
−
import java.io.FileReader;
+
−
+
−
public class SortStudents{
+
−
  public static void main(String[]argv) throws Exception{
+
−
    ArrayList&lt;String> names = new ArrayList&lt;String>();
+
−
    String line;
+
−
    BufferedReader fh
+
−
      = new BufferedReader(new FileReader("year1.txt"));
+
−
    while (null!=(line=fh.readLine())){
+
−
      String [] st = line.split("\t");
+
−
      names.add(st[1]);
+
−
    }
+
−
    for (String s:names)
+
−
      System.out.println(s);
+
−
  }
+
−
}
+
−
</prog>
+
−
<answer>
+
−
import java.util.ArrayList;
+
−
import java.io.BufferedReader;
+
−
import java.io.FileReader;
+
−
+
−
public class SortStudents{
+
−
  public static void main(String[]argv) throws Exception{
+
−
    ArrayList&lt;String> names = new ArrayList&lt;String>();
+
−
    String line;
+
−
    BufferedReader fh
+
−
      = new BufferedReader(new FileReader("year1.txt"));
+
−
    while (null!=(line=fh.readLine())){
+
−
      String [] st = line.split("\t");
+
−
      if (!names.contains(st[1]))
+
−
        names.add(st[1]);
+
−
    }
+
−
    for (String s:names)
+
−
      System.out.println(s);
+
−
  }
+
−
}
+
−
</answer>
+
−
</question>
+
−
==Problem 3 - Who's missing?==
+
−
<question className="SortStudents" title="Using Sort" copyfile="students.txt present.txt">
+
−
The file present.txt contains those students from students.txt who attended a particular tutorial. We want a list of all those students who were not present.
+
−
Brody, Adrien
+
−
Irons, Jeremy
+
−
Spacek, Sissy
+
−
 
+
−
How to do this…
+
−
*Create an array list called present
+
−
*Open the file present.txt and add every line to the ArrayList present
+
−
*Open the file student.txt
+
−
*For each line in the file – if that student is not in present print the name.
+
−
if (!present.contains(line)) System.out.println(line);
+
−
<prog>
+
−
import java.util.ArrayList;
+
−
import java.io.BufferedReader;
+
−
import java.io.FileReader;
+
−
+
−
public class SortStudents{
+
−
  public static void main(String[]argv) throws Exception{
+
−
    ArrayList&lt;String> names = new ArrayList&lt;String>();
+
−
    String line;
+
−
    BufferedReader fh
+
−
      = new BufferedReader(new FileReader("present.txt"));
+
−
    while (null!=(line=fh.readLine())){
+
−
      names.add(line);
+
−
    }
+
−
  }
+
−
}
+
−
</prog>
+
−
<answer>
+
−
import java.util.ArrayList;
+
−
import java.io.BufferedReader;
+
−
import java.io.FileReader;
+
−
+
−
public class SortStudents{
+
−
  public static void main(String[]argv) throws Exception{
+
−
    ArrayList&lt;String> names = new ArrayList&lt;String>();
+
−
    String line;
+
−
    BufferedReader fh
+
−
      = new BufferedReader(new FileReader("present.txt"));
+
−
    while (null!=(line=fh.readLine())){
+
−
      names.add(line);
+
−
    }
+
−
    fh.close();
+
−
    fh = new BufferedReader(new FileReader("students.txt"));
+
−
    while (null!=(line=fh.readLine())){
+
−
      if (!names.contains(line)) System.out.println(line);
+
−
    }
+
−
  }
+
−
}
+
−
</answer>
+
−
</question>
+
−
 
+
−
==Problem 4 - Count Routes==
+
−
<question className="CountRoutes" title="Count Routes" copyfile="year1.txt">
+
−
Use the file year1.txt to print a list of all the routes in alphabetical order. We also want a count of how many students are in each route.
+
−
BENG (HONS) COMPUTER NETWORKS AND DISTRIBUTED SYSTEMS F/T 10
+
−
BENG (HONS) COMPUTER SECURITY AND FORENSICS F/T 28
+
−
BENG (HONS) COMPUTING F/T 22
+
−
BENG (HONS) EMBEDDED COMPUTER SYSTEMS F/T 1
+
−
...
+
−
 
+
−
How to do this:
+
−
*See the section “Use Map to aggregate” from the lecture
+
−
*You can use two passes to process get the answer.
+
−
**On the first pass run over the list and put the value 0 against every route you encounter.
+
−
**On the second pass use put to add 1 to each route you encounter.
+
−
*It is better to use a single pass:
+
−
**For each route if the key exists then +1 of the value, if the key does not exist then put 1.
+
−
<prog>
+
−
import java.util.HashTable;
+
−
import java.io.BufferedReader;
+
−
import java.io.FileReader;
+
−
+
−
public class CountRoutes{
+
−
  public static void main(String[]argv) throws Exception{
+
−
    HashTable&lt;String,Integer> routes = new HashTable&lt;String,Integer>();
+
−
    String line;
+
−
    BufferedReader fh
+
−
      = new BufferedReader(new FileReader("present.txt"));
+
−
    while (null!=(line=fh.readLine())){
+
−
      names.add(line);
+
−
    }
+
−
  }
+
−
}
+
−
</prog>
+
−
<answer>
+
−
import java.util.ArrayList;
+
−
import java.io.BufferedReader;
+
−
import java.io.FileReader;
+
−
+
−
public class SortStudents{
+
−
  public static void main(String[]argv) throws Exception{
+
−
    ArrayList&lt;String> names = new ArrayList&lt;String>();
+
−
    String line;
+
−
    BufferedReader fh
+
−
      = new BufferedReader(new FileReader("present.txt"));
+
−
    while (null!=(line=fh.readLine())){
+
−
      names.add(line);
+
−
    }
+
−
    fh.close();
+
−
    fh = new BufferedReader(new FileReader("students.txt"));
+
−
    while (null!=(line=fh.readLine())){
+
−
      if (!names.contains(line)) System.out.println(line);
+
−
    }
+
−
  }
+
−
}
+
−
</answer>
+
−
</question>
+

Latest revision as of 09:37, 2 March 2012

SET08112 - Algorithms and Data Structure

Retrieved from "http://progzoo.net/mw/index.php?title=SET08112&oldid=9931"