CS2100 Lecture Notes

Week 2

8 types

reference

Scanner is a conveyor belt

PRIMITIVE

REFERENCE

when have a null, pointed to bootstrap location bootstrap is a location that's activated after booting system NullPointerException

Predetermined packages

to get these class, use an import statement

only 4 ways to control a program

  1. sequence (line 1 -> 2 -> 3 -> ...)
  2. conditional statement (if, else, switch statement)
  3. loops

"y = x++" is different from "y = ++x",

do while is used for data validation

Strings come from a string pool, Java minimizes the string they have to allocate

Week 3

Comparison

Inheritance

Object provides the default constructor

.equals()

How to write an equal method yourself

Inheritance

Week 5

Substitutability Principle

Polymorphism requirements

An example of abstract class

/* public or private */ abstract class ClassName {
// class body
}

Interface (接口)

public interface TimeKeeper {
    public int getTime();

    public int setTime();
}

An interface is an agreed-upon means of connection between classes

Using (implementing) interfaces

Polymorphism via interfaces

Standard Java interfaces

Interface hierarchies

Comparable interface

Implementing comparable

Comparator

Function objects

Comparator

Implementing Comparators

import java.util.Comparator;

public class CmpDogByBreedAndName implements Comparator<Dog> {
    public int compare(Dog d1, Dog d2) {
        /* Customized comparator */
        int retval = d1.getBreed().compareTo(d2.getBreed());
        if (retval != 0) {
            return retval;
        }
        /* String's default compareTo method */
        return d1.getName().compareTo(d2.getName);
    }
}

KEY POINT

Abstract class - what a class is, what kind of data is stored
Interface - what it can do

Week 6

Frameworks

Java Collections Framework (JCF)

Collection interface

List interface

import java.util.Collection;

public interface List<E> extends Collection<E> {
    public boolean add(int index, E obj);

    public E get(int index);

    public int indexOf(E obj);

    public boolean remove(int index);

    public E set(int index, E obj);

    List<E> subList(int from, int to); /* Not suggested */
}

Implementing a List using ArrayList (time complexities)

Vectors

Vector performance

Vectors are a generic data type

import java.util.ArrayList;
import java.util.Vector;

Vector<Integer> list1 = new Vector<Integer>();
ArrayList<Double> list2 = new Vector<Double>();

A size value stores the number of data elements - always <= capacity

Generic type (泛型)

Generics ensure type safety

import java.util.List;

public class ArrayList<E> extends AbstractList<E> implements List<E> {

}

import java.util.ArrayList;

public static <T extends Comparable<T> T> largestValue(ArrayList<T> arrList) {

}

import java.util.LinkedList;

LinkedList<E>;

Abstract Model of a List Object

LinkedList

How LinkedList works

head =0;
tail =0;

Node

Node class

  public class ListNode<T> {
    /* Data being stored in this node */
    private T data;
    /* reference to the next node in the list */
    protected ListNode<T> next;

    public ListNode(T data) {
        this.data = data;
        this.next = null;
    }

    /* getter */
    public T getData() {
        return this.data;
    }
}

Other types of LinkedLists

Doubly linked list

Inserting a node into a single Linked List

  import org.w3c.dom.Node;

Node bob = new Node("bob");
bob.next =harry.next;
harry.next =bob;

Iterator

Stacks

LinkedList implementation

Queue

The radix sort

Comparing algorithms

Analysis of algorithms

Measuring efficiency

The order of performance O

T(n) = O(f(n))

Week 9

Analysis of algorithms (continued)\ Choose critical section of code\ Natural of input may change\ If searching a list and want to find where the first item is can be located three different places which can lead to three cases\ Upper bound corresponds to the worst case\ Exception is an object that describes an unusual and erroneous situation\ Separates into normal execution flow and exception execution flow\ An error is also an object in Java but usually represents an unresolvable situation\ Error out of memory disk error\ Error handling is about controlling program flow\ Java has predefined exception that can occur\ Deals with three-way

If an exception is ignored by the program, program terminates

Call stack trace

Types of errors/exceptions

Types of exception

Unchecked

Checked

Throws goes on to the end of a method header that might throw exceptions\ Throw new exception is the exception that you wanna throw\ Only have to have throws if there’s no try/catch block\ Debugging

Syntax error

Runtime errors

Log errors

What is recursion?

Recursive data structures

import java.util.Random;

int a = new Random().nextInt(2);

means that a now takes an integer randomly generated when 2 is the upper bound.

Common recursive problem

Trees!

In a List, nodes have a link to a next node\ In a doubly-linked list, nodes have links for next and previous nodes\ Trees work like a form of list that can have any number of links to other nodes\ A given tree may define a structure e.g.: up to 2 nodes, or up to 3 nodes

General tree definition

Binary trees

Traversing a tree

pre-order -> prefix post-order -> postfix

pre-order

public abstract preOrder(t) {
    if (t != null) {
        // access the root item of t (visit)
        preOrder(t.leftTree);
        preOrder(t.rightTree);
    }
}

status update

Sets

Note

Maps

HashTables

Use contiguous memory to store all the information\ put in the key and have the hash function that gives us the location\ the finding of location is O(1)

given a key -> send it into a hash function -> use result as index into hash table -> handle any collisions

bucket: an array of values

count: the number of values in the hash_map

just take the key and use it as index

return

Hashing: transforming a key into an index

a hash function: an easily computable operation on the key that returns an integer which is then converted into an index in the array buckets

Java doesn't have unsigned int

collisions

when doing chaining, remember that the last added element comes to the front

load factor - table performance when load factor = 1 -> number of indexes =

Hash tables Collisions: open addressing