Johns Hopkins · EN.601.226 · Spring 2022

Java and Object-Oriented Design

Overview

• Parts of a Java Class · OO Terminology · Data Structure · Algorithm · Searching · Recursion · Other Java Notes

Inheritance and Polymorphism

• Polymorphism

ADTs and Interfaces

• Abstract Class · Abstract Data Type: · Interfaces · Documentation

Generics and Unit Testing

• Generics · Testing

Java Exceptions

• Robust Methods · Testing Exceptions · Throwing Exceptions · Exception Hierarchies · Custom Exceptions

Iterators and Inner Classes

• Enhanced For Loop · Iterator Design

Linked List

• Implementation

Analysis

RAM Model

• RAM: A hypothetical computer

Asymptotic Growth Rate

Asymptotic Analysis

• Asymptomatic Bounds

Quadratic Sorts

• Selection Sort · Insertion Sort · Bubble Sort

Lists, Stacks, Queues and Sets

Stack

• Access · Dynamic array stack · Amortized Analysis

Queue

• Array Implementation · Other Restricted Data Structures

Positional List

• Singly Linked List · Double Linked List · Position Interface · List · Position Exception · Node is-a Position · Sentinel Nodes

Set ADT

• Efficiency · Iterator · Ordered Set · Set-theoretical Operations.

Trees and Maps

Binary Search Tree

• Implementation

Trees and Tree Traversal

• Level-order traversal · In-order traversal · Pre-order traversal · Post-order traversal · Tree Terminology · Perfect Binary Tree · Consideratios

Map ADT and Balanced BSTs

• Map Interface · Array-based implementation · OrderedMap ADT Interface · BinarySearchTreeMap · Efficiency · Balanced BST · Height is O(lgN)

AVL Tree

• Right Rotation · Left rotation · When to rotate · AVL Tree Explained

Priority Queue

• PriorityQueue ADT · Implementation · Heap Order Property · Ranked Array Representation · Best Operation · Insert Operation · Remove operation · PQ Constructors

Treap

• Treap Analyss

Hashing and Sorting

Hash Table

• Motivation · Hash Function · Java's hashCode() · Collisions · Chaining · Linear Probing · Quadratic Probing · Other Probing Strategy

Heapsort

• The Original Sort · Improved Sort: · In-Place Sorting

Merge Sort

• The Merge Process · Merge Sort: Big Picture · Optimization

Quicksort

• The Big Picture · Partition · Quicksort Implementation · Analysis · Pivot · Java Sorts · Stable Sorting

Graphs

Graph Basics

• Directed vs Undirected · Abstraction · Representation

Graph Search

• Neighborhood · Path · Breadth-First Search · Depth-First Search · Discovered vs Visited

Shortest Path

• Find Path · Find Distance · Find Shortest Path · Weighted Graph

Minimum Spanning Tree

• Acyclic Graph · Spanning Tree · Algorithms to Solve MST Problem

Union-Find

• Improvment: Weighting · Improvement: Path Compression. · Runtime · Kruskal's Runtime

Review

Midterm 1 Cheatsheet