CMSC132

CMSC131 Review⌗

Data Privacy⌗

• Data should be as private as possible
• Instead of getters and setters, write methods that use the class’s data in the class itself

Object Copying⌗

Reference Copy⌗

• Simply copy reference, same object
• fast, but not a real copy

Shallow Copy⌗

• Copy the object, but not any objects it refers to
• middling, and a somewhat decent copy

Deep Copy⌗

• Copy the object and everything it ever refers to
• Slow, but deep

Initialization⌗

Initialization Blocks⌗

• Block of code in a class but not in a method used to initialize static or nonstatic fields of the class
• Can contain complex initialization including loops
• Executed once per object

Static Initialization Blocks⌗

• Block of code in a class but not in a method used to initialize static or nonstatic fields of the class
• Can contain complex initialization including loops
• Executed once per ckass

Enumerated Types⌗

• Fixed set of values
• Have the methods values(), valueOf(), and compareTo()

Comparable Interface⌗

• Requires the compareTo() method
• Returns a value that represents their comparison
  • A.compareTo(B) < 0 if A<B
  • A.compareTo(B) = 0 if A=B
  • A.compareTo(B) > 0 if A>B
• Imposes a natural ordering

Inheritance⌗

• A subclass (child class) can inherit fields and methods from a superclass (parent class) while still having its own unique fields and methods
• Java only permits single inheritance
• All classes inherit from Object in Java
• If a subclass’s constructor does not call some form of super(), a call to super() with no parameters will be made even if no such constructor exists

Polymorphism⌗

• A subclass can be stored with a super class reference because a subclass is a superclass
• This can be as deep as wanted

Testing types of objects⌗

• ref instanceof class will check if ref is a class or any of its children classes
• ref.getClass() = class.getClass()= will check if ref is class only
• instanceof will be fine if ref is null, but getClass will not
• Avoid these, and use Overriding

Visibility⌗

• From a superclass reference, only fields and methods visible from that superclass can be accessed even if the object is a subclass

Casting⌗

• Downcasting is valid only when the actual object is of that type, otherwise you get a ClassCastException
• Upcasting is always valid as long as the type is valid in the hierarchy
• Type never changes, just how it’s treated

Overriding⌗

• Testing types of objects and then Casting is bad style, instead you should override methods and fields to have different behavior
• Overriding methods have the same name and signature (other than access modifiers) of a superclass method
• The type of the object (not reference) at runtime determines which method will run
  • This is called dynamic dispatch

Privacy⌗

• Subclass can only be more or as restrictive on override fields or methods than its parent class
• protected allows only subclasses to access the thing

super⌗

• subclasses can use super.method() to call the superclass version of an override method
• They can do the same with fields, although its confusing because it shadows the superclass field
• If x doesn’t exist in super.x or super.x(), a syntax error will be raised

Deep Inheritance⌗

• Class inherit from the closest place where defined above

final⌗

• Cannot be overridden
• private methods are therefore final
• A final class can’t be extended or its methods overridden
• Helps with security

Object⌗

• Everything inherits from here
• Therefore, every object is guaranteed to have these methods

Interfaces⌗

• These are contracts of constants and methods to define
  • Can technically have default and static methods as of Java 8
• Classes can implement interfaces (and multiple of them)
• As such, classes that implement an interface can be stored in that a reference of that interface’s type

OOP Design⌗

• Nouns -> Class, Verbs -> Methods, Adjectives -> Interfaces
• Too many classes can mean more complexity, but too little can mean not enough flexibility or abstraction
• subtype: either a subclass of a type or implements that type
• Inheritance is nice, but sometimes we want composition (has a relationship)
  • Go for composition first, if not inheritance
  • inheritance is more restrictive (only one subtype per parent type)
• Types of Inheritance
  • Extension: Add new functionality
  • Limitation: Restrict behavior to a certain subset
  • Combination: Mix multiple classes and their behaviors

Abstract Classes⌗

• Fix the solution of having useless parent classes that only serve to group together child calsses
• If a method is designated as abstract, then children classes must implement it
  • If a method is abstract, its class must also be abstract
• Abstract classes can’t be instatiated, but can be a reference

Errors⌗

• Errors cause program incorrectness

Compile Errors⌗

• Errors in what you type (or say)

Runtime Errors⌗

• Something that’s impossible or illegal to execute

Logic Errors⌗

• Errors in what you mean
• The algorithm itself it flawed

Testing⌗

• We can run specific, pre-computed cases to check our results

Code Coverage⌗

• How much code was tested?
• Line/Statement Coverage: what percentage of lines/statements were run?
• Branch Coverage: what percentage of conditions were tested (case-by-case basis)?
• Path Coverage: what percentage of all possible execution sequences were tested?

Error Handling⌗

• We have to handle an error somehow instead of just dying, right?
• We can tell the caller by returning an error code

Exceptions⌗

• However, error codes can make things complex in terms of return types
• In this case, we throw an Exception
• In Java, Exceptions are objects that extend Throwable

Checked Exceptions⌗

• These must be handled because they’re fairly easy to deal with and fairly common
• Exception

Unchecked Exceptions⌗

• These are more serious and aren’t easy to recover from, and don’t need to be caught
• Automatically caught by the JVM
• RuntimeException and Error

throw⌗

• Generates an exception of the given type

throws⌗

• This propagates the exception to the method’s caller
• Put in the method signature and details what exception it is throwing

Try/Catch Blocks⌗

• Methods can handle an exception themselves
• Order of execution:
  • Leave try block and go to first match catching block
  • Execute catch block
  • Execute finally
    • If nothing matched, go to caller

• finally

  • Always executes, no matter what
  • Even if no catch block matches and control goes to caller, finally still executes

Generics⌗

• Removes a concrete type from the code, and replaces it with some stand in type variable

Type Parameters⌗

• In Java, use <T> to specify a type parameter

Generic Classes⌗

• Put a Type Parameter next to the class
• When instantiation, provide a concrete class as an argument for the type parameter

Generic Methods⌗

• For methods, simply use the Type Parameter inplace of a regular type
• You should use these when the return type or other variable depend on a method specific type

Generic Variables⌗

• Simply use the Type Parameter inplace of a regular type

Bounded Type Parameters⌗

• You can use the extends keyword to limit the type to be a subtype of a given type
• You can use the super keyword to limit the type to be a supertype of a given type
• You will be able to call methods that are visible from the given type due to inheritance

Wildcard Type Parameters⌗

• Issue: Generic<S> is not a subclass of Generic<T> even if S is a subclass of T
• ? stands for any type
• You can combine this with Bounded Type Parameters to limit to a subclass

Quirks of Generics⌗

• Can’t instantiate an object of the generic type
• Must use T[] data = (T[]) new Object[size]; to create array (cast Object array to type T[])

Type Erasure⌗

• Make nothing type-specific and do a ton of casting implicitly

Inner Classes⌗

• We want access to a class’s fields for one other class but its bad to make it public
• Inner Class: A class defined inside another that can access all fields and methods despite access modifies (and vice-versa)
• Inner class has a link to its outer class object
• Static Inner class has no link to its outer class object

Lists⌗

• Sequential group of elements with a one-to-one relation
• The head is the first one in the list, the tail is the last

Linked List⌗

• A list has nodes which store data and a reference to the next node
• Insertion
  • Create a new element, set it’s next to current’s next, and then set current’s next to itself.
• Deletion
  • Set prev’s next to current’s next.
• Linked lists are nice but try not to iterate through too often (i.e. getting the size)
• Variations
  • Dummy head node
    • Simplifies special cases by having a permanent head node that doesn’t change
  • Circularly Linked Lists
    • List loops around
  • Doubly-Linked Lists
    • Node links backward
    • Must update references in both prev and next
  • Tail Reference
    • We store a reference to the tail to avoid travel all the way down

Arrays Vs. Linked Lists⌗

• Linked Lists have easy insertion and deletion any where
• Arrays can do easy indexing and less memory
• Linked lists can’t really index easily and take more memory
• Arrays need a lot of reshaping and moving for common operations

equals⌗

• Must do 5 things
  1. Take a parameter of type Object
  2. Check if parameter is not null
  3. Check if parameter is an object of the class
  4. Cast parameter to object of the class
  5. Compare fielss
  6. Bonus: if subclass call super.equals()

Recursion⌗

• Solve a problem with a method that repeatedly calls itself
• Every method gets its own space on the runtime stack
• Every iterative method can be done with recursion
• To do it well:
  • Check the base case works properly
  • Break the problem into repeated steps
  • Make sure to merge them
• Auxiliary methods are often needed to pass other parameters or helper variables

Tail Recursion⌗

• Recursive step is the last performed
• Very easy to transform it into a loop

Recursion Vs. Iteration⌗

• Iteration is often more efficient
• Recursion has a higher overhead but can be much easier to write, maintain and debug, and work well with certain data structres

Polymorphic Lists⌗

• A list is made of multiple List objects that store a reference to another List objects where List is an interface and the concrete classes are EmptyList or NonEmptyList
• Uses overriding and interfacing to avoid checking for null and dealing with the end of lists

Iterators⌗

• Classes that can be iterated over must implement Iterable<T>
• Iterable<T> specifies one method iterator() that returns an Iterator<T>
• Iterator<T> itself is a interface that specific a few methods
• Make it an inner class for ease of access
• for-each loops automatically handle iterator
  • Just give it something iterable

Design Patterns⌗

• Descriptions of reusable patterns that are best practices

Types⌗

• Creational: Best way to create objects
• Structural: Best way to collect objects
• Behavioral: Best way to allow object interaction

Iterator Design Pattern⌗

• Move through a collection of objects
• Easy to do it without knowing any specifics

Adapter Design Pattern⌗

• Convert existing interfaces to new ones

Singleton Design Pattern⌗

• Only one instance of a class is created and used globally
• Saves memory

Factory Design Pattern⌗

• Abstract which class in what case
• When you cannot anticipate what subclasses will be created

Decorator Design Pattern⌗

• Attach responsibilities/functionality to objects

Marker Interface Design Pattern⌗

• Mark class with interface and no need for field

Java Collections Framework⌗

• Contains a bunch of things to store data
• Collection Interface is the main things all data collection classes implement
• Collections class has a bunch of static helper methods

Stacks⌗

• Restricted list where elements can be only added/remove from one end (LIFO)
• Common operations are push, pop, peek, isEmpty

Implementations⌗

Array⌗

• stackTop is used to mark the top of a stack (increment after pushing)
• Can either be number of elements or index of top element (increment before pushing)

Queues⌗

• Restricted list where elements can only be accessed/removed at one end and added at the other (FIFO)
• Common operations are enqueue, dequeue, isEmpty

Implementations⌗

Linked List⌗

• Add elements to back of list and remove elements from head
• Not other way around because otherwise more iteration

Array⌗

• We’ll inch along the array, so treat it as circular
• Use modulus to go around the array

Algorithm Analysis⌗

Benchmarking⌗

• Real-life tests
• Accurate but not general and according to machine

Asymptotic Analysis⌗

• It’s intrinsic efficiency based on input size
• Find it’s asymptotic efficiency (for really big numbers)
  • It’s less about being exact, but more about getting it’s “category” of growth
  • Order is \(1\), \(log(n)\), \(n\), \(nlog(n)\), \(n^2\), \(n^3\), \(n^k\), \(k^n\), \(n!\), \(n^n\)
  • Big-O is an upper bound of the number of operations
  • Critical sections is the piece of code that defines the running time (the thing that gets run the most)
  • Sum of \(n\) consecutive integers is \(\frac{n*(n+1)}{2}\)

Trees⌗

• A tree contains data in a hierarchy where one node can have many children
• Depth measures distance from root
• Height is max depth

Binary Tree⌗

• Tree with at most two children per element

Algorithms⌗

• Deletion

  • Search for X
  • If X is a leaf, remove it
  • else
    • Replace X with largest value in left subtree
    • Or Replace X with smallest value in left subtree

Balanced vs. Degenerate⌗

• Balanced: Mostly Triangular, height is \(O(log(n))\)
• Degenerate: Spaghetti, height is \(O(n)\)

Tree Traversals⌗

Depth First⌗

• Preorder

  • root, left, right

• Inorder

  • left, root, right

• Postorder

  • left, right, root

Breadth First⌗

• Traverses nodes by depth (one level at a time)

Binary Search Tree⌗

• Binary Tree but where all elements in the left subtree are smaller than the root and sall element in the right subtree are greater than the root
• Searches can then narrow down half the elements at a time by going either left or right

Polymorphic Binary Search Tree⌗

• Like polymorphic list but EmptyTree is a singleton

Heaps⌗

• Perfect tree is a perfect triangle
• Complete is perfect until last row
• Heap is a complete tree but every parent is less than or equal to its childen (min heap)
• Common operations are insert, getSmallest

Insertion⌗

• add X to end of heap
• Repeatedtly switch with parent while less than parent

getSmallest⌗

• Move last X to top
• Repeatedely swap with child while smallest greater than child

Implementations⌗

Array⌗

• Flatten tree to array
• parent is \(\lfloor \frac{i-1}{2} \rfloor\)
• left child is \(2i+1\)
• right child is \(2i+2\)

Priority Queues⌗

• Queues where elements are sorted by priority value
• Implemented by using a max heap

Comparator Interface⌗

• Allows for making different sorting orders
• Has two methods: compare(T o1, T o2) and equals(Object obj)
• compare compares two objects of type T

Java I/O⌗

Hashing⌗

• Take a certain space of data and randomly compress it into a smaller, fixed space of integers
• Math.abs(compressionFn(hashFn(key)))
  • compressionFn compresses into hash table space
  • hashFn transforms into a hash

Collision Handling⌗

Chained Hashing⌗

• Each element in the table is a bucket/linked list

Linear Probing⌗

• Keep going if place occupied
• When searching, need to search until null found and not a place where an element has been deleted

Double Hashing⌗

• Use a secondary hash function to determine the next jump distance
• Math.abs(compressionFn(h1(key) + h2(key)))
• Follow linear probing procedure

Good Qualities⌗

• Uniform scattering
• Closed values get sparsely scattering
• Fast

Hash Code Contract⌗

• If a.equals(b), then \(a.hashCode() == b.hashCode()\) but nothing else (not even the inverse)

Sets⌗

• No relationship between stored elements
• No duplicates

Types⌗

HashSet⌗

• Basic, nothing special

LinkedHashSet⌗

• In order of insertion

TreeSet⌗

• In increasing order

Maps⌗

• Each value is associated with a key and accessed with it

Types⌗

HashMap⌗

• basic, nothing special

LinkedHashMap⌗

• both keys and values in order of insertion

TreeMap⌗

• both keys and values in increasing order

Implementations⌗

Hashing⌗

Binary Search Tree⌗

Two parallel arrays⌗

Graphs⌗

• Vertices connected by edges
• Path is a connected sequence of vertices
• Cycle is a path that starts where it ends
• Common operations: add/remove vertices/edges, change edge weight, get cost of edge, check for vertex/edge, traverse

Traversals⌗

Breadth First⌗

• By depth from starting, in vertex value order for a certain depth

Iterative Depth First⌗

• Follow one path all the way and back up
• push things onto stack, so it ends up reversing vertex visiting order

Recursive Depth First⌗

• Follow one path all the way and back up
• Keep calling on the first children, so in increasing order

Implementations⌗

Adjacency Matrix⌗

• Store matrix of n by n vertices
• Edges are a non-zero value at a given index

Adjacency Map/Set⌗

• Each vertex has a entry and contains other vertices that it’s connected to

Dijkstra’s Algorithm⌗

• For each vertex, find the vertices its connected to and check if the smallest known cost to get there is greater than the one just checked, if so, make that the new path
• Process vertex with smallest cost

Concurrency⌗

• Multiprocessing: true simultaneous execution, because of hardware
• Multitasking: switching really fast to simulate simultaneous execution

Thread⌗

• They share heaps but not runtime stack
• Execute the exact same program
• Thread.sleep() sleeps the current thread (sleep is static)
• Always call start to actually create a thread

Process⌗

• They don’t share heap or runtime stack
• Don’t have to execute same program

Using Threads⌗

Creating Threads⌗

• Extend Thread
  1. Create a class
  2. Put processing in run method
  3. Create objects
  4. Call start
• Or implement Runnable (better)
  1. Create class
  2. Put processing in run
  3. Create instances
  4. Create =Thread=s to run them
  5. Call start

Thread States⌗

• New
• Waiting
• Runnable
• Blocked
• Finished

Thread Lifecycle⌗

1. Instantiate
2. Run
3. May wait
4. Join

Synchronization⌗

• Multiple threads trying to modify the same share variable can cause a data race
• We can coordinate the threads (synchronization)

Lock⌗

• Entity that can only be held by one thread at a time
• Every object has a lock
• Can be used by a synchronized block or the synchronize keyword on a method that prevent an instance of a class from running more than one of those at a time
• Avoid deadlock where no thread can get a lock it needs to proceed (mexican standoff)
• Make sure operations that need to be atomic are synchronized, otherise it could be interrupted, even if it doesn’t seem like it

Case Analysis⌗

• Best Case
• Worst Case
• Average Case (normal average, or weighted average aka expected cost)
• Amortized Cost
  • Average running time per operation
• Big-O is upper bound
• Big-Omega is lower bound
• Big-Theta is tightest bound

Sorting⌗

Descriptors⌗

• Stable: keeps relative order
• In-place: doesn’t need more than a constant amount of extra memory
• External

Bubble Sort⌗

• Bubble element to end one at a time

Insertion Sort⌗

• Pick next element and insert into sorted part

Selection Sort⌗

• Pick min and swap to front

Tree Sort⌗

• Put into tree and then inorder traversal

Heap Sort⌗

• Put into max heap and then getLargest repeatedly

Quick Sort⌗

• Pick pivot and separate list into smaller than and greater than pivot and the recurse

Merge Sort⌗

• Divide list in half repeatedly until one element and then interleave into sorted order

Counting Sort⌗

• Count number of each element and then reserve that many spots

Radix Sort⌗

• Sort by least significant to most significant (builds relative order)

Sort Efficiency⌗

Complexity Categories⌗

• P: Deterministic Polynomial time
• Exponential: Exponential Time
• Decidable: Can be solved
• Undecidable: Can’t be solved
• NP: Can be solved in polynomical time but god knows how

Algorithm Designs⌗

Recursive⌗

Backtracking⌗

Divide and Conquer⌗

Dynamic⌗

• Remember solutions to past subproblems

Greedy⌗

• Choose best local choice rather than best global choice

Brute Force⌗

Branch and Bound⌗

• Prune bad solutions based on best so far

Heuristic⌗

• Rule of thumb

Efficiency⌗