Shreyas’ Notes

Introduction to Program Design

COMP 215

fall, sophomore year

waterfall method:

  1. requirements
  2. design
  3. implementation
  4. testing and debugging
  5. maintenance

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

properties:

programming language:

programming paradigms:

Taxonomy of Programming Languages §

abstraction: hiding details to focus on essentials

paradigms:

when is type checking performed?

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

Wrapper Classes §

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

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:

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.

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 §

  1. Requirements
  2. Design
  3. Implementation
  4. Testing and Debugging
  5. Maintenance

JUnit §

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.

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.

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:

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:

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 §

Wildcards §

List<?>

Bounded wildcards:

Maps §

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

operations:

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.

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.

var x = 5;

cons:

pros:

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

Sets §

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

operations:

Errors §

Exceptions §

Throwable hierarchy:

Operations:

Exception class:

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 §

Linked lists §

append and prepend are O(1)O(1). other common operations are O(n)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)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)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.rx.l < x < x.r

total preorder: x.l<xx.rx.l < x \leq x.r

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

Binary Heaps §

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

    ...
}

index math (assuming null at index 0):

remove (priority element elem):

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

Treaps §

self-balancing BSTs. combination of BSTs are heaps.

rotations :sparkles:

insert, remove and contains are O(logn)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;

    ...
}

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

Hash tables §

Memory and References §

Garbage Collection §

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

Objects:

Types of garbage collection:

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.