Soft Dev 3

Home > Preview

The flashcards below were created by user finmcoul on FreezingBlue Flashcards.


  1. Byte Streams
    • A byte stream manages bytes of raw binary data
    • The classes that handle such streams are in two hierarchies– InputStream and its descendant– OutputStream and its descendants
    • System.out and System.err are PrintStreams,– ... which is a subclass of FilterOutputStream, – ... which is a subclass of OutputStream and by default map to the same window on screen. – They have print and println methods
    • System.in is a generic InputStream, but is usually mapped into a stream that offers more functionality
  2. Character Streams
    • A character stream is designed to deal with 16-bit Unicode characters
    • Input is handled by the class Reader and its descendants
    • Output is handled by the class Writer and its descendants
  3. Reading from Keyboard
    • To read from the keyboard you can use the java.util.Scanner class– with System.in as parameter
    • Within a line it works on tokens :
    • – sc.hasNext() checks if there are more tokens
    • – String s = sc.next(); // next (string) token
    • – String s = sc.nextLine(); // the full line
    • – int i = sc.nextInt(); // next int token
  4. Reading a Text File 
    • We will first discuss how to read a text file
    • To read a file we must:
    • – open the stream to the file
    • – read the data item by item into variable(s)
    • – close the stream to the file
    • To read/write text we use character streams
    • To achieve this we use a FileReader which is a subclass of an InputStreamReader
  5. Exceptions
    • An exception is an unexpected event occurring during execution of a program
    • Many of the IO methods throw an exception– for example, if the given file name does not exists– in most cases they throw an IOException
    • This is especially the case for input streams
    • Any method using these classes must either– be declared to throws IOException, or– must catch and handle the exception itself
    • An uncaught exception terminates the running program
  6. Reading A Text File Code
    • public void readTextFile(String filename){ try{ FileReader fr = new FileReader(filename);
    • BufferedReader br = new BufferedReader(fr);
    • String line;
    • while(br.ready()){ line = br.readLine();
    • System.out.println(line);
    • } // end of while loop br.close();
    • } // end of try clause
    • catch(Exception e){ // this will catch any exception System.out.println(e.getMessage());
    • } // end of catch clause
    • } // end of method
  7. Using Tokens
    • readLine() returns the complete line of the text file
    • We can use a StringTokenizer to separate each of the tokens in this line
    • By default this is each word– i.e. white space as delimiter– but other delimiters can be specified
    • For example, we can count the number of words in a file
  8. Counting Words Code
    • public int count(String filename) throws Exception{
    • FileReader fr = new FileReader(filename);
    • BufferedReader br = new BufferedReader(fr);
    • String line;
    • StringTokenizer st;
    • int count = 0;
    • while(br.ready()){ line = br.readLine();
    • st = new StringTokenizer(line);
    • while (st.hasMoreTokens()){
    • st.nextToken();
    • count++;
    • } // end inner while loop
    • } // end of outer while loop br.close(); return count;} // end of method
    • The wrapper is the parse part
  9. Wrapper Classes
    • Sometimes we want to convert a string to a primitive type– e.g. if we want to read in a price of something, then we may want to use an int
    • A wrapper class wraps such a primitive type.
    • Examples include Character, Integer and Double
    • These have method to convert a string to the primitive type they wrap, e.g:18int val = Integer.parseInt(string);
    • double d = Double.parseDouble(another_string)
  10. Writing Text Files
    • Writing a string into a text file is similar to reading a file
    • Create a BufferedWriter object using a FileWriter object– the FileWriter accepts a filename as argument
    • Write the given string to the BufferedWriter object
    • close the stream
  11. Writing Text Files Code
    • public void writeTextFile(String filename,String content){
    • try{ FileWriter wr = new FileWriter(filename);
    • BufferedWriter bw = new BufferedWriter(wr);
    • bw.write(content);
    • bw.close(); }
    • catch(Exception e){ System.out.println(e.getMessage()); }}
  12. Serialising Objects
    • Data files are of bytes (binary) rather than characters
    • We can save an entire object to a file
    • When an object is saved, all referenced objects are also written to the file
    • This object (and all objects referenced) must be serialisable, i.e. the class has to implement the java.io.Serializable interface (and that’s all extra code you have to add to this class):
    • import java.io.Serializable;
    • public class MyClass implements Serializable { .... }
  13. Writing Objects To File
    • To write a serialisable object to a file you can use an ObjectOutputStream.
    • FileOutputStream fos = new FileOutputStream(filename);
    • ObjectOutputStream oos = new ObjectOutputStream(fos);
    • oos.write(object);
    • oos.close();
  14. Reading Objects
    • To read a serialisable object to a file you can use an ObjectInputStream. 
    • To write the object you can use the readObject() method
    • readObject() returns an Object (which all objects inherits)– you must then cast this object to the correct type
    • FileInputStream fis = new FileInputStream(filename);
    • ObjectInputStream ois = new ObjectInputStream(fis);
    • MyClass m = (MyClass) ois.readObject();
    • ois.close();
  15. Measuring Time Code
    • We measure the program in the worst possible running time
    • long before = System.currentTimeMillis();
    • program(n);
    • long after = System.currentTimeMillis();
    • long time = after - before;
  16. Big Oh Notation
    • In Big-Oh we try to write the functions in the simplest terms
    • The following rules are used to simplify terms– drop lower-order terms– drop constant factors
    • For our example: 6N+5– we drop the lower-order term 5 (left with 6N)– we drop the constant 6 (left with N)– meaning it is expressed by the linear function O(N)
  17. Abstract Data Types (ADT)
    • An Abstract Data Type (ADT) is an abstraction of a data type specifying– data stored– operations– error conditions
    • Example coffee shop:–
    • Data is money, coffee, customer
    • Operations are: take_order(customer), make(coffee), ...
    • Error conditions: no_money, no_coffee, ...
  18. Stack ADT
    • • The data is the type of elements stored•
    • Main operations: push(object) - adds object to the top of the stack–
    • pop() - remove and returns element at the top
    • Auxiliary operations– top() - return element at top 
    • size() - return number of elements– isEmpty() - check if empty 
    • Error conditions: pop/top of empty stack
  19. Stack Interface
    • public interface Stack {
    • public int size();
    • public boolean isEmpty();
    • public Object top() throws StackException;
    • public void push(Object element);
    • public Object pop() throws StackException;}
  20. Generics Stack Interface in Java
    • We can re-implement our stack using generics
    • Instead of using an Object we now use a generic type <E>
    • public interface Stack<E> {
    • public int size();
    • public boolean isEmpty();
    • public E top() throws StackException;
    • public void push(E element);
    • public E pop() throws StackException;}
  21. The Queue ADT
    • The data is the type of elements stored
    • Main operations– elements enter a queue at the rear and are removed from the front–
    • enqueue(object) - adds object to the rear of the queue 
    • dequeue() - remove and returns element at the top
    • Auxiliary operations– front() - return the front element 
    • size() - return number of elements
    • isEmpty() - check if empty
    • Error conditions: dequeue/front of empty queue
  22. The Queue ADT Interface
    • We use generics to represent the Queue interface
    • The type Object is replaced by the E and the casting is no longer needed
    • Similarly to stacks, we throw a QueueException when accessing an empty queue public interface Queue<E> {
    • public int size();
    • public boolean isEmpty();
    • public E front() throws QueueException;
    • public void enqueue(E element);
    • public E dequeue() throws QueueException;}
  23. Length of Queue
    (capacity - front + rear) % capacity
  24. Autoboxing and Unboxing
    • We have previously learned about wrapper classes for the Java primitives such as Integer and Character
    • Java will automatically convert a primitive to it’s wrapper class when required, and this is called autoboxing. E.g.: Integer i = 1;Character c = ‘c’;
    • The dual, i.e. converting a wrapper class to it’s primitive is called unboxing, and is automatically applied when the wrapper class is:-
    • passed as an argument expecting the primitive
    • assigned to a value expecting the primitive
    • public Integer myfun(int arg){ .... }Integer i = 10; // autoboxing
    • int x = myfun(i) // unboxing (twice)
  25. The Comparable Interface
    • • Using Generics we can generalise this algorithm to any class which have a key we can compare with
    • • Comparable is an interface (in java.util) containing one method:public interface Comparable<T>{public int compare(T o);}
    • • This method should give a natural order of the objects compared, and returns:
    • a negative number if this < o
    • 0 if they are considered the same
    • a positive number if this > o
  26. Comparator Interface
    • public interface Comparator<T>{public int compare(T o1,T o2);}
    • This method should give a natural order of the objects compared, and returns:
    • –a negative number if o1 < o2
    • – 0 if they are considered the same
    • – a positive number if o1 > o2
  27. Big Oh Notations
    • Bubble/insertion sort - o(N^2)
    • selection sort - o(N^2)
    • Binary search - o(Log N)
    • Merge Sort - o(n log n) is a divide and conquer algorithm
    • Quick sort - o(n log n)
  28. Binary Search Method
    • Requires sorted list
    • • Step cases?
    • – smaller than means search bottom half
    • – greater than means search top half
    • public Person binarySearch(int age,int first,int last) throws NotFoundException{ if (middle_age == age) // success case return arr[middle];
    • else if (age < middle_age) // bottom half return binarySearch(age,first,middle-1) else // top half return binarySearch(age,middle+1,last) }}
  29. Recusive Methods
    • A recursive method is a method that calls itself
    • The parameters are changed for each call, and in the method we separate between two types of cases
    • The base case is where the method does not call itself
    • The step case are values where the method call itself
  30. A Generic Linear Search
    • • To generalise we –replace the Person class with a generic D (for data), –and the age int with a generic K (for key) We need to compare an element with a key
    • • This can be achieved with the compareTo method in the Comparable interface
    • Meaning that D must implement Comparable<K>– using Generics we can write this using the extends keyword
  31. Generic Liner Search Code
    • public class LinearSearch<D extends Comparable<K>,K>{
    • public D linearSearch(D[] arr,K key) throws NotFoundException{
    • for(int i = 0; i < arr.length; i++){
    • if(arr[i].compareTo(k) == 0) return arr[i]; }
    • throw new NotFoundException ("No element found"); }}
  32. Insertion Sort
    • Is the inverse of the bubble sort
    • All items on the left of the current item being compared
  33. Insertion Sort
    • public static void insertionSort(int [] list)
    • {// iterates throw the array
    • for(int i = 0; i < list.length; i++)
    • { int cur = list[i]; // select current elements
    • int j = i - 1; // start at element before current element
    • // find the correct place and move each element forward
    • while(j >= 0 && list[j] > cur) list[j+1] = list[j--];// add the element to the correct place list[j+1] = cur; }
  34. Insertion Sort Using Generics
    • public class InsertionSort<E extends Comparable<E>> {
    • public void insertionSort(E[] list)
    • {// iterates throw the array
    • for(int i = 0; i < list.length; i++)
    • {E cur = list[i]; // select current elements
    • int j = i - 1; // start at element before current element
    • // finds the correct place and move each element forward
    • while(j >= 0 && cur.compareTo(list[j]) < 0)
    • list[j+1] = list[j--];// add the element to the correct place
    • list[j+1] = cur; } }}
  35. Quick-Sort
    • Quick-Sort is another Divide-and-Conquer algorithm
    • 1. Divide: select an element x from S which is called the pivot (often the last element of S).
    • Divide S into 3 sub-lists:
    • • L storing elements of S less than x
    • • E storing elements of S equal to x
    • • G storing elements of S larger than x
    • 2.Recur: Recursively sort L and G
    • 3.Conquer: Put back elements in the order of first elements of L, then elements of E, then elements of G.
  36. Hash Maps and Hash Tables
    • A hash map is a map implemented using a hash table. It consists of
    • • a hash function h
    • • an array (called table) of size N
    • The hash function h turns a key into a value between 0 and N-1
    • It is used to compute the index of the array in which to store the value
    • Sometimes h will compute the same value for different keys
    • Dealing with these cases are called collision handling
  37. Collision handling
    • Ways of handling collisions are separate chaining and linear probing:–
    • Separate chaining: Each element of the array can store multiple elements.
    • •E.g. an array of ArrayLists. When there is a collision, multiple elements are store at the same index
    • –Linear probing: When there is a collision the next free index of the array is used.
  38. Sets and Operations
    • Union of two sets A and B, written A ∪ B, which are all the elements in A or B
    • Intersection, written A ∩ B, which are all elements in A and also in B
    • Subtraction, written A B, which are all elements in A but not in B–
    • Subset, written A ⊆B, which holds (returns a boolean) if all elements of A are also in the set B, 2
  39. Singly Linked Lists
    • Consists of a sequence of nodes containing links to the next node and the element of that node
    • The list has a head and a tail pointer that point to the first and last node of the  list
    • The last element of the list points to null
  40. Singly Linked List - Add At Head
    • Allocate a new node
    • 2. Insert new element
    • 3. Have new node point to old head
    • 4. Update head to point to new node
  41. Singly Linked List - Add At Tail
    • Allocate a new node
    • 2. Insert new element
    • 3. Have new node point to null
    • 4. Have old last node point to new node
    • 5. Update tail to point to new node
  42. Singly Linked List - Remove Head
    Move the header pointer to the new head node and allow the computer to deal with the old head
  43. Singly List - Remove From Tail
    • Move the tail pointer to new node
    • Have the new node point to null
  44. Doubly Linked Lists
    • Consist of a sequence of nodes, each node has
    • a link to the previous node,
    • a link to the next node
    • and the element it holds
    • and has a header and trailer node instead of pointer
  45. Circularly Linked Lists
    • Consists of a list of singly linked nodes
    • Last node links to first node
    • Has a cursor node that points to current node
  46. Tree Terminology
    • Root: node without parent 
    • Internal node: node with at least one child 
    • External node (a.k.a. leaf ): node without children 
    • Ancestors of a node: parent, grandparent, grand-grandparent, etc.
    • Descendant of a node: child, grandchild, grand-grandchild, etc
  47. PreOrder Transversal Of Trees
    • Algorithm preOrder(v)
    • visit(v)
    • for each child w of v preorder (w)
  48. Post Order Transversal
    • Algorithm postOrder(v)
    • for each child w of v
    •     postOrder (w)
    • visit(v)
  49. Inorder Trasversal
    • Algorithm inOrder(v)
    • if hasLeft
    •    (v)inOrder
    • (left (v))visit(v)
    • if hasRight (v)
    • inOrder (right (v))
  50. Binary Trees
    • Each internal node has at most two children (exactly two for properbinary trees)
    •  The children of a node are an ordered pair
  51. BinaryTree ADT
    •  The BinaryTree ADT extends the Tree ADT, i.e., it inherits all the methods of the Tree ADT
    •  Additional methods:
    •  position left(p)
    •  position right(p)
    •  boolean hasLeft(p)
    •  boolean hasRight(p)
    •  Update methods may be defined by data structures implementing the BinaryTree ADT
  52. Priority Queue ADT
    •  A priority queue stores a collection of entries
    •  Each entry is a pair (key, value)
    •  Main methods of the Priority Queue ADT
    •  insert(k, x) inserts an entry with key k and value x
    •  removeMin() removes and returns the entry with smallest key
    •  Additional methods
    •  min() returns, but does not remove, an entry with smallest key
    •  size(), isEmpty()

Card Set Information

Author:
 finmcoul
ID:
 218957
Filename:
 Soft Dev 3
Updated:
2013-05-14 11:32:16
Tags:
F27SG
Folders:

Description:
Software Development 3
Show Answers:

What would you like to do?

Home > Flashcards > Print Preview