CS180 FINAL

What is meant by recursion?

1. A self reference

2. Methods can call themselves

3. Data structures can reference themselves

Why does recursion work?

1. The method doesn’t always call itself

2. Data structure doesn’t always link to another copy of itself

3. Always at least 1 base case of itself

4. Base case and recursive case

Key tasks of recursion

• Base: what can be done w/o recursive call

• Recursive: Same but “smaller”

How is recursion implemented?

• (stack handles method calls)

• When method called, params & local vars “pushed” onto call stack

• Each recursive method call has own params & local vars

• When method returns, previously executing method (below it on the stack) picks up where it left off

LinkedList brief overview

• outer class has head and tail nodes

• private nested Node class has String value and Node link

• isEmpty is when head and tail are null

• add appends to tail of list

What are Trees and why are they used?

• hierarchal w/ one-to-many links

• good for efficient searching and sorting

root node

no parents

leaf node

no children

interior node

neither root or leaf

Trees are either or

empty (root == null) OR node with links to 0+ trees

binary tree

• each node references at MOST/MAX 2 other trees

How to conduct binary search

• key at each node

1. key in left child of root is smaller than root

2. key in right child of root is bigger than root

3. each child is also a binary search tree

inorder traversal

left subtree, root, right

preorder traversal

root, left subtree, right subtree

postorder traversal

root, right subtree, left subtree

Difference between regular data structure vs dynamic

• organizes, stores and retrieves info in a program

• memory use grows/shrinks to store info

ArrayList

• array that grows as elements are added

allocate new instances of ArrayList

ArrayList a = new ArrayList();

add __ to end of ArrayList

a.add(“__”);

replace ArrayList element at index x with __

a.set(x, “__”);

get ith index of ArrayList and print it

System.out.println(a.get(i));

What types can ArrayList hold? What about LinkedList?

single; 2+

components of LinkedList class

• outer LL class

  • implements getters/setters

  • keeps “head pointer” to head of LL

  • keeps “size” variable to track the size

• inner LL class

  • implements individual nodes

  • each node linked to another, except last

adding to LL

• create backwards

• variable head points to “head node”

• create new node with link field pointing to current “head node”

• update head with new node just created

adds String _ to LL

void add(String _)

creates and returns array with all elements

String[] to Array()

ADT

• abstract data type

• description of behavior of data type (class) w/o specifying implementation of behavior

• user of data type unaware, cannot assume implementation details

• ADT implementer has max flexibility

LIFO

• Last In First Out, stack

  • push element on

  • pop element off

  • isEmpty to check

FIFO

• First In First Out, queue

  • put element at end

  • get next from front

  • isEmpty to check

What can you use stack for?

• undo operations

• manage storage of local variables for methods being executed

• RPN

What can you use queue for?

• file sent to printer

• threads/processes waiting for access to CPU or core

• network packets waiting for transmission

HashMap

• stores values referenced by a key

• “dictionary” data structure: maps keys to values

• HashMap<K,V>

  • K: type of key, V: type of value

abstract classes

• can’t be instantiated

• methods can be unimplemented (like interface) or for default behavior

• can be extended from/to smth else, can contain fields

dynamic binding

methods selected at runtime based on class of object referenced, not class of variable that holds object reference

abstract methods

• provide only header (no body), class also declared abstract

• methods in interface implicitly declared abstract

• when subclassing

  • generally provide method bodies for abstract methods

  • if abstract methods remain, subclass still abstract and must be declared so

time-slicing

run each program around a few hundred millisecs

benefit of multiple cores

• running 2 cores at ½ speed is equivalent to running 1 core at 1/full speed

• slower cores consume less energy and generate less heat

threads

• multiple cores can speed up one program

  • can have multiple parts/threads running simultaneously

  • if database spread over 3 files, run 3 threads on 3 cores to run 3x faster

sequential vs concurrent execution

sequential:

• single thread of execution weaves through program

• simple PC(program counter) identifies current instruction being executed

concurrent:

• multiple threads running simultaneously

• multiple PCs active (1 per thread)

imports Thread class with run() method

import java.lang.*;

allows creation/manipulation of threads

Thread t = new Thread();

starts thread referenced by t

t.start();

join with/wait for running thread t

t.join();

called by start() in different thread

t.run();

How does start() method interact with run() method for Threads?

Code doesn’t call run directly. Start() calls run() as part of new thread sequence

how to create threads

• make sure class implements Runnable interface

• implement void run()

• create new thread

How can threads be unpredictable

• can be interrupted

  • time slicing threads prevents one from hogging CPU

  • high-priority activities (I/O) can interrupt

• threads don’t proceed at same rate

• coordinating threads is challenging

synchronized

• keyword, allows 2+ threads to use common object to avoid race conditions

• only 1 thread can be inside statement block at a time

Thread states

• new thread: created but not yet started

• runnable: started and available to run

• not runnable: sleeping or waiting for I/O

• terminated: returned from run(0

  • t.sleep(n): current thread sleeps for n milliseconds

  • t.yield(): gives up CPU to let another run

IP/internet protocol

identifies hosts (servers, workstations, laptops) w/ unique address

DNS/domain name system

maps domain names (ex. email address) to IP addresses

TCP/transmission control protocol

identifies ports on hosts for network connection

socket

• IP address + TCP port

• 2 sockets make a network connection

client-server connection

• server is process waiting for connection

• client is process that connects to server

  • process can be both at different times

  • once connected, they can both read/write data to each other

  • communicate thru socket

objects and networking

• uses ObjectOutputStream and ObjectInputStream

  • OOS generates “header” of info that must be read

  • requires flush to make sure OIS not blocked

models TCP/IP socket

new Socket(“email_address”, __)

getOutputStream and getInputStream

used by Server to identify connected client

Exception Class hierarchy

Exception; IO (FileNotFound); Your; Runtime (Arithmetic, IndexOutOfBounds, NullPointer)

Unchecked definition and classes

• Program/Java Virtual Machine error, no recovery so crashes

• Runtime and subclasses

Checked definition and classes

• user error, must encapsulate in try catch or throw, recoverable

• all other classes

how many classes and interfaces can a class extend/implement

classes can extend 1 other class, but implement 1+ interfaces

object class methods

• clone() //make copy

• equals(Object e) //compares for equality

• toString() //returns String, called by print

what is constructor chaining

all constructors up inheritance chain can initialize object under construction

what does default constructor have and why

super() calls 0-arg constructor in superclass

overloading

• same class

• two methods with same name

• different signatures

overriding

• superclass and subclass

• two methods with same name

• same signatures

how to check equality for objects

s1.equals(s2)

• NOT == (only addresses)

keywords that change control flow

if, switch, while, for

A || B vs A && B vs A ^ B

• A or B

• A and B

• A xor B (combo)

generally, what should be access mods for methods, fields, and constants

• methods: public

• fields: private

• constants (final): public

arraylist syntax (non empty)

ArrayList<String> list = new ArrayList<String>()

arraylist syntax (empty)

ArrayList<String> list = new ArrayList<>();

buffer

• holds info for speed/efficiency

• remember to close file/flush buffers when done

• write and read order must be the same

static vs transient

• for the class

• for instance variables, good if need to be regenerated anyways

what classes can you use to write/read to file

• PrintWriter

• FileReader, BufferedReader, Scanner

exception messages

• e.getMessage() //gets associated text message

• e.printStackTrace() //prints current call stack

finally keyword

executed after all try-catches, guaranteed to execute

import for JOptionPane class and other imports

import javax.swing.*;

simple GUI methods

• showMessageDialog()

• showInputDialog()

• showConfirmDialog()

• showOptionDialog

gui message types

plain, error, information, warning, question

what other import is needed for complex guis

import java.awt;

EDT and what import do you need

• event dispatch thread

• own thread for Java GUI

• SwingUtilities.invokeLater(Runnable method);