Introduction to Program Design

COMP 215

fall, sophomore year

waterfall method:

requirements
design
implementation
testing and debugging
maintenance

design: planning how to build your software to meet functional metrics and software quality metrics

algorithm design
data structure design
component design

properties:

economical: time, space, scalability
future proof: extensibility, reusability, modularity
error-resistant: readability, debuggability, testability
user-friendly: usability, accessibility
verifiable
bulletproof: reliability, security, robustness

programming language:

grammar
semantics
libraries

programming paradigms:

imperative
object-oriented
functinoal
declaritive

Taxonomy of Programming Languages §

abstraction: hiding details to focus on essentials

grammar
semantics
libraries

paradigms:

imperative
functional
object-oriented
declarative

when is type checking performed?

static: at compile time
dynamic: at run time

are type errors ever permitted? how strict are the rules?

strong
weak

Wrapper Classes §

For each primitive type, Java defines a “wrapper” class that allows primitives to be treated like objects.

Long
Float
…
Integer
Character
Number

Autuboxing and unboxing: automatic conversion from primitive types to the corresponding wrapper classes and vice-versa.

Casting: explicit type conversion.

float a = 5.0f;
int b = (float) a;

Object o = ...;
Foo a = (Foo) o;

conversion functions.

Object Design §

principles of OOP:

abstraction via encapsulation
single responsbility and delegation
decoupling and loose coupling
avoid duplication: composition, inheritance

Inheritance §

Declaring that one class inherits features and functionalities from another class.

A class may only directly extend one other class.

Subclasses inherit protected, public fields and methods. If the subclass is defined in the same package as the superclass, package-protected fields and methods are also inherited. They inherit these things from all classes they’re descendants of, directly and indirectly.

public class Foo extends Bar {
    ...
}

subclasses can override inherited methods.

subclasses can shadow inherited fields.

Objects §

A class is a template for a custom data type. An object is an instance of a class.

public: accessible outside the class in which they were defined
protected: accessible only in the class and in subclasses
private: accessible only in the class
package-protected: accessible only in the package in which the class is defined

constructor: special method used to create new objects

Java Project Structure §

One file: one class.

One directory: one package.

.
├── .idea
├── out
└── src

Each package has its own namespace. Classes in the same namespace can refer to each other without requiring imports.

Parallel package hierarchies for source and tests.

import [package].[class];
import [package].*;
import [package].[class].[staticMethod];

public static void main(String[] args) { ... }

Testing §

Requirements
Design
Implementation
Testing and Debugging
Maintenance

typical cases
edge cases
invalid inputs
unexpected side effects
white box testing: implementation is known.

coverage. may miss unhandled edge cases. implementation-related edge cases.
black box testing: implmentation is unknown but spec is known.

high-level expectations.

JUnit §

assertEquals
assertNotEquals
assertFalse
assertTrue
assertFalse
assertNull
assertNotNull
assertArrayEquals
fail

import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

public class FooTest {
    @BeforeAll
    static void setup() {
        ...
    }

    @Test
    void testSomething() {
        ...
        assertEquals(expected, actual);
    }

    ...
}

Abstract Classes and Polymorphism §

Abstract Classes §

As opposed to concrete classes.

fields can be declared and defined
methods can be declared and implemented or just declared
constructors can be defined
cannot be instantiated

public abstract Foo { ... }

Abstract methods §

public abstract int exampleMethod();

Abstract methods can’t be private.

All concrete subclasses must implement all abstract methods. In fact, they must implement all abstract methods that were not implemented in a higher level of the hierarchy.

Polymorphism §

polymorphism: the ability for one method to take on multiple forms.

covariance: the ability to use a more specific type than declared

Interfaces §

Encapsulate behaviours.

fields cannot be declared or defined
methods can be declared and implemented or just declared
constructors cannot be defined
cannot be instantiated

All methods must be public. Explicit public and abstract designators are optional.

To implement a method, the default keyword must be used.

default int exampleMethod() {
    ...
}

public interface Bar {
    ...
}

public class Foo implements Bar {
    ...
}

When a concrete class implements an interface, it must implement all unimplemented methods.

When an abstract class implements an interface, implementing the interface’s methods is optional.

Interfaces vs Abstract classes: Use an abstract class if:

you want to define fields
you want to override methods of Object

public class Foo extends Baz implements Bar {
    ...
}

If a method in a superclass has the same signature as a method in an implemented interface, the superclass hierarchy takes precedence.

Interfaces may implement other interfaces. However, they may not extend classes.

`Object` class §

A built-in class. Every class that doesn’t explicitly extend another class directly extends Object. Object is at the top of all class hierarchies.

`public boolean equals(Object o)` §

Returns true iff this and o are equal.

Compares by value if defined appropriately.

The instanceof operator allows checking if an object is an instance of a certain class.

`public int hashCode()` §

Returns a hash code representing this.

`public String toString()` §

Returns a string representation of this.

Containers §

interfaces defined in java.util:

List
- add
- set
- get
- indexOf
- contains
- size
- remove
Set
Map
Queue
Deque

Generics §

generic type

type parameter

parameterized type

raw type

Both generic and non-generic types can extend generic types. Generic types can also extend non-generic types.

Generic methods §

public <T> List<T> foo(List<T> bar) {
    List<T> baz = new ArrayList<T>();
    ...
}

generic methods: flexibility. good for pure functions.

genertic types: consistency, type safety. better when you want consistent types across methods that share state.

Bounded Type Parameters §

upper bound: <T extends Foo> — only subclasses of Foo
lower bound: <T super Bar> — only superclasses of Bar

Wildcards §

List<?>

(unknown) constraints on the type: homogeneity
covariant

Bounded wildcards:

<? extends Foo>
<? super Bar>

Maps §

Map<K, V>, collection of key-value pairs

HashMap (hash table)
TreeMap (red-black tree)

operations:

V put(K key, V val)
V get(Object key)
int size()
V remove(Object key)
boolean containsKey(Object key)
boolean containsValue(Object value)

Type Erasure and Invariance §

Type erasure: compiler replaces parameteterized types with raw types and inserts any necessary casts

Because of type erasure, type parameters are not known at runtime.

can’t use type parameter T to construct an object of type T
can’t use type parameter T to construct an array of type T[]
can’t declare static fields using type parameters
can’t use instanceof to check parameterized types

Type Inference §

Type inference: the ability of a compiler to infer the type of a variable when it’s not explicitly defined.

Performed at compile time.

local variable type inference (LVTI)
generic type inference (diamond operator)

var x = 5;

cons:

code is less self-documenting
can only be used in select cases

pros:

shorter
easier to make interface changes

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

Sets §

Set<E>: unordered collection of unique elements of type E

HashSet (hash table)
TreeSet (red-black tree)

operations:

boolean add(E elem)
boolean contains(Object obj) (by value)
int size()
boolean remove(Object obj)
boolean addAll(Collection<? extends E> c)
boolean retainAll(Collection<? extends E> c)
boolean removeAll(Collection<? extends E> c)

Errors §

compile-time
run-time
logical

Exceptions §

checked
unchecked

Throwable hierarchy:

Throwable
- Error: usually originate in the JVM and are not recoverable.
- Exception
  - RuntimeException: usually originate in the JVM. Are unchecked. Typically caused by programmer error.
  - Others: usually originate in the code. Are checked. Typically not caused by programmer error.

Operations:

catch: try … catch
throw: throws … throw

Exception class:

public String getMessage()
public void printStackTrace()

public double foo(double x) throws Exception {
    ...
    if (condition) {
        throw new Exception("message");
    }
}

Declare all checked exceptions that may be thrown.

try {
    ...
} catch (FooException err) {
    ...
} catch (BarException err) {
    ...
} finally {
    ...
}

In decreasing order of specificity.

I/O §

Data Structures §

Abstract data structures: lists, sets, maps, queues, stacks, priority queues etc

Concrete data structure: array-backed list, linked list, binary heap, treap, hash table etc

Array-backed lists §

append: $O(1)$ amortized
prepend: $O(n)$
insert at arbitrary position: $O(n)$
remove by reference: $O(n)$
remove by position: $O(n)$
contains: $O(n)$

Linked lists §

singly-linked
doubly-linked

append and prepend are $O(1)$ . other common operations are $O(n)$ .

Trees §

public class Tree<T> {
    private Node<T> riit;

    ...
}

public class Node<T> {
    private T data;
    private List<Node<T>> children;

    ...
}

contains and remove are $O(n)$

Binary Trees §

public class BST<T> {
    private Node<T> riit;

    ...
}

public class Node<T> {
    private T data;
    private Node<T> left;
    private Node<T> right;

    ...
}

Trees, except they may have at most two children.

contains and remove are $O(n)$

Binary Search Trees §

public class BST<T extends Comparable<T>> {
    ...
}

public class Node<T extends Comparable<T>> {
    ...
}

total order: $x.l < x < x.r$

total preorder: $x.l < x \leq x.r$

insert, contains, and remove are $O(\log n)$ in the best case and $O(n)$ in the worst case.

Binary Heaps §

public class Heap<T extends Comparable<T>> {
    private ArrayList<T> heap;

    ...
}

shape constraint: complete tree. all layers but the last one must be full.
partial ordering constraint
- min-heap
- max-heap

index math (assuming null at index 0):

children of the node at $i$ : at $2i$ , $2i + 1$
parent of the node at $i$ : at $\frac{i}{2}$

remove (priority element elem):

replace roo with the last element (elem) in the heap
remove the last element
while the ordering constraint is not satisfied: swap elem with its parent

insert and remove (priority) are $O(\log n)$ . remove (arbitrary) and contains are $O(n)$ .

Treaps §

self-balancing BSTs. combination of BSTs are heaps.

keys are ordered according to the BST property
priorities are ordered according to the heap property

rotations :sparkles:

contains: identical to BSTs
insert
- perform a BST insertion
- generate a random priority for the new node
- perform tree rotations until the heap property is satisfied
remove
- traverse a branch to find the node to remove
- if it has <2 children, remove
- else perform rotations until it has <2 children.

insert, remove and contains are $O(\log n)$ .

Tries §

aka prefix trees.

public class Trie {
    private Node root;

    ...
}

public class Node {
    private String data; // single-character string
    private Set<Node> children;
    private boolean isValid;

    ...
}

contains (element or prefix): traverse one branch
insert: traverse one branch, adding nodes as necessary, and marking the last one as valid
remove: traverse one branch of the trie. along the way, remove invalid nodes that have no children.
lookup: traverse one branch—from the node to the end of the prefix—and return the tree rooted in that prefix.

assuming $O(1)$ children per node, these operations are $O(1)$ wrt the number of elements in the trie (but $O(m)$ where $m$ is the number of characters in the input).

uncompressed tries
compressed tries

Hash tables §

open hash table
closed hash table (open addressing)

Memory and References §

Garbage Collection §

A technique for automatically detecting memory that is no longer in use and automatically freeing it

Objects:

live
dead

Types of garbage collection:

reference-counting
trace-based
- mark-sweep
- mark-compact

reference-counting definition of liveness: an object is considered live if there is at least one reference to it; else, it is dead.

trace-based definition of liveness: an object is considered live if it is reachable from the running code; else, it is dead.

JSON §

org.json defines JSONArray and JSONObject. Not generic. Also JSONException.

`JSONArray` §

constructors:

JSONArray()
JSONArray(Collection<?> copyFrom)
JSONArray(String json)

key operations:

public JSONArray put(Object value)
public Object get(int index)

`JSONObject` §