Final Review

Materials

  1. Homeworks: same types of problems

  2. Slides

  3. Course note hosted on github: Checklist of topics

  4. Textbook: skip the details not listed in the slides or course note

  5. Visualizations: make sure that you understand how algorithms work on paper

  6. Code examples: help you understand how to algorithms work

  7. Projects: not too helpful to final but you can find common mistakes in your code

Problem Types

  • True/False questions

  • Multiple choices

  • Multiple answers

  • Fill in the blanks

  • Matching

  • Coding questions

    • There will be 1 or 2 coding questions. They are only for simple algorithms that can fit in a short method. A simple algorithm should be less then 20 lines of code as a Java method. Most of the algorithms are too long to be coded in exam and will only tested on how they work on paper.

    • They can also be a question on describing the interface of an ADT (only list public methods) or framework of a data structure (both private and public members).

    • I will not focus on the use of Java features like generic, interface, inheritance, etc. You may see these features though. The coding questions will only test your understanding of the algorithm rather than your Java skills but you certainly need to use correct Java code to write your answers.

General Questions

  • For an ADT

    • What is the interface/API? Required and optional parts.

    • What are the implementations? Pro and con of each implementation.

    • What are the applications of the ADT? Required in certain algorithms or data structures? Used to solve certain problems?

  • For a data structure

    • Typical Java implementation: Usually a Java class

    • What are the components? Required and optional operations.

    • Is there any variation of the data structure? Pros and cons of each variation.

    • What are the applications of the data structure? Required in certain algorithms or data structures? Used to solve certain problems?

  • For an algorithm

    • Typical Java implementation: a Java class, a method in a Java class or a static method in a Java class (correspond a standalone function)

    • What is the problem that the algorithm is trying to solve?

    • What ADTs or data structures are required by the algorithm?

    • Is this algorithm part of a data structure?

    • What is the time complexity of the algorithm? What is the space complexity of the algorithm? Big-O notation only.

List of algorithms

  • Must know details (how it works on paper)

  • Search in sequential data structures

    • Linear search

    • Binary search

  • Sorting algorithms

    • Selection sort

    • Insertion sort

    • Merge sort

    • Quick sort

      • Partition using Hoare’s scheme, first element as pivot, no initial shuffling

  • Heap data structure

    • add

    • remove

    • Percolate up

    • Percolate down

    • Heapify

    • Heap sort

  • BST

    • Insert

    • Search

    • Delete - use successor to replace the node to be deleted

  • Red-black tree

    • Adjustment in insert

      • How to handle

        • Right-leaning red - left rotation

        • Left-left red - right rotation

        • Left-right red - left rotation + right rotation

        • Both children red - recolor

  • Hash table

    • Variations on collision resolution

      • Separate chaining

      • Linear probing (simplest open addressing)

    • Insert with collision resolution

      • Linear probing

  • Graph

    • Interconversion of graph representations and graph diagrams

      • Adjacency matrix

      • Adjacency list

    • Graph traversal

      • DFS

      • BFS

    • Shortest path: Dijkstra’s algorithm

Topics

  • Basic concepts

    • ADT - not language dependent

    • Data structure - usually language dependent

    • Algorithm

    • Relationship of ADT, data structure, and algorithm

      • Data structure is the implementation of ADT

      • ADT is the interface/API/abstraction of data structures

      • Algorithm can be part of a data structure

      • Algorithm may require certain ADTs or data structures to work

  • Algorithm analysis

    • Purpose

    • Asymptotic notation

      • Big-O notation: worst case/upper bound, most commonly used

      • Big-Omega notation: best case/lower bound

      • Big-Theta notation: average case/exact bound

    • Time complexity

      • Constant time complexity: \(\Theta(1)\)

      • Linear time complexity: \(\Theta(n)\)

        • Linear search, sum, max, min, average, etc.

        • Loops on N that reduce by 1 in each iteration

      • Logarithmic time complexity: :\(\Theta(\log n)\)

        • Binary search

        • Loops on N that reduce by half in each iteration

        • Recursion on N that reduce by half in each recursion (binary search)

      • Quadratic time complexity: \(\Theta(n^2)\)

        • Simple sorting algorithms like bubble sort, selection sort, insertion sort

        • Loops on N that reduce by 1 in each iteration

        • Nested loops on N that reduce by 1 in each iteration

      • Loglinear time complexity: :\(\Theta(n \log n)\)

        • Divide and conquer algorithms like merge sort and quick sort

        • Loops on N that reduce by half in each iteration and nested loops on N that reduce by 1 in each iteration

        • Recursion on N that reduce by half in each recursion and nested recursion call work on on N that reduce by 1 in each recursion

  • Sequential ADTs

    • Stack ADT

      • LIFO

      • push/pop/peek/isEmpty

    • Queue ADT

      • FIFO

      • enqueue/dequeue/peek/isEmpty

    • Linked-list data structure

      • Node class

      • add/remove at the beginning/end in the implementation of Stack and queue

      • variation:

        • singly/doubly linked-list

        • with/without tail reference

    • Analysis of all operations of stack and queue

      • Time complexity

      • Space complexity

  • Sorting algorithms

    • Role

      • a method in a sequential data structure

      • a standalone static method that takes a sequential data structure as input

    • Categories

      • Comparison based sorting algorithms (general purpose sorting algorithms)

        • Bubble sort

        • Selection sort

        • Insertion sort

        • Merge sort

        • Quick sort

      • Non-comparison based sorting algorithms

        • Counting sort

        • Radix sort

      • Simple sorting algorithms

        • \(\Theta(n^2)\) time complexity

        • Selection sort

        • Insertion sort

      • Fast sorting algorithms

        • :\(\Theta(n \log n)\) time complexity

        • Merge sort

        • Quick sort

      • Divide and conquer sorting algorithms

        • Merge sort

        • Quick sort

        • Hybrid sorting algorithms

          • Use divide and conquer algorithms for large subsequences

          • Use simple sorting algorithms for small subsequences

    • Analysis

      • Time complexity

        • worst case

        • average case

        • best case

      • Space complexity

        • \(\Theta(1)\) space complexity: in-place sorting algorithms like bubble sort, selection sort, insertion sort, quick sort, etc.

        • \(\Theta(n)\) space complexity: not-in-place algorithms like merge sort,

          counting sort, radix sort, etc.

      • In-place or not

  • Heap data structure

    • Stored in an array (array list)

    • Logically a complete binary tree

    • Heap property

      • min heap: the value of a node is smaller than or equal to the values of its children

      • max heap: the value of a node is larger than or equal to the values of its children

    • Behaviors

      • add: add a new element to the end of the array and percolate up/swim

      • remove: overwrite the root with the last element of the array, remove the last element of the array, and percolate down/sink

      • peek

      • isEmpty

      • percolate up/swim (private)

      • percolate down/sink (private)

      • heapify (private)

    • Applications

      • Priority queue

      • Heap sort

      • Dijkstra’s shortest path algorithm

      • Prim’s minimum spanning tree algorithm

      • Find the kth largest element in an array

    • Time complexity analysis

      • add/remove/peek/isEmpty: :\(\Theta(\log n)\)

      • percolate up/swim: :\(\Theta(\log n)\)

      • percolate down/sink: :\(\Theta(\log n)\)

      • heapify: \(\Theta(n)\) or :\(\Theta(n \log n)\)

  • Heap sort

    • Repeatedly remove the root of the heap and add it to the end of the array until the heap is empty

    • Improved version of insertion sort

    • Time complexity: :\(\Theta(n \log n)\)

  • Priority Queue ADT

    • Behaviors

      • enqueue

      • dequeue

      • peek

      • isEmpty

    • Implementations

      • Heap data structure

      • Array

        • sorted

        • unsorted

      • Time complexity analysis

        • Heap implementation: :\(\Theta(n \log n)\)

  • Symbol table/map/dictionary ADT

    • Key-value pairs

      • Key

        • unique, allows equality comparison

        • comparable

        • immutable

    • Behaviors

      • put

      • get

      • delete

      • contains

      • size

      • isEmpty

    • When values are ignored, symbol table ADT degrades to a set ADT

    • Implementations:

      • Sorted array/list

      • Unsorted array/list

      • Binary search tree

      • Hash table

  • Tree

    • concepts

      • Node

      • Edge

      • Parent/child relationship

      • Ancestor/descendant relationship

      • Sibling relationship

      • Root node

      • Leaf node

      • Internal node

      • Degree

      • Path

      • Distance

      • Height of a tree

      • Depth of a node

      • Ordered tree/Unordered tree

    • Hierarchy

      • Binary tree: degree 2 ordered tree

        • Heap

        • Binary search tree

          • Self-balancing binary search tree

            • AVL tree

            • Red-black tree

            • B-tree

  • Binary search tree

    • binary tree with order property

      • left subtree contains only nodes with keys less than the key of the root node

      • right subtree contains only nodes with keys greater than the key of the root node

      • left and right subtrees are also binary search trees

    • Behaviors

      • put

      • get

      • delete

      • traversal (in-order)

      • size

      • isEmpty

    • Time complexity analysis

      • put/get/delete

        • depends on the depth of the tree

        • average :\(\Theta(\log n)\)

        • worst case \(\Theta(n)\)

      • size/isEmpty: \(\Theta(1)\)

    • Applications

      • Symbol table

      • Priority queue

      • Binary search

  • Self-balancing BST

    • 2-3 Trees

      • 2-node: one key, two children

      • 3-node: two keys, three children

      • 4-node: three keys, four children (temporary)

      • always a perfectly balanced tree

      • insert

    • Red-black BSTs (left-leaning) to implement 2-3 trees

      • Not a perfectly balanced tree

      • Left-leaning by definition

      • Behaviors

        • search/contains/get - same as BST

        • Insert

          • insert like normal BST with a red link

          • adjust

            • left rotation

            • right rotation

            • recolor (split)

  • Graph

    • Concepts

      • Vertex/Node

      • Edge

      • Adjacent

      • Direction

      • Path

      • Connected

      • Cycle

      • Distance

      • Weight

      • Degree

    • Types/Properties

      • Directed/Undirected

      • Cycle/Acyclic

      • Weighted/Unweighted

      • Connected/Unconnected

      • Dense/Sparse

    • Representations

      • List of edges

      • Adjacency matrix

      • Adjacency list

      • Pros and cons

    • Time complexity analysis

      • \(V\), \(E\)

      • Different among various representations

  • Graph traversal

    • Similar to that of tree traversal

    • Depth-first search (DFS)

      • Recursive implementation

      • Iterative implementation (Stack ADT)

    • Breadth-first search (BFS)

      • Iterative implementation (Queue ADT)

  • Minimal spanning tree of a graph

    • Concepts

      • Spanning tree

      • Minimal spanning tree (MST)

      • Weighted graph

      • Weight of a spanning tree

    • Algorithms (greedy algorithms)

      • Prim’s algorithm - grow from starting vertex

      • Kruskal’s algorithm - grow forests from edges with smallest weights and combine to a tree

      • Further details are optional in this course

  • Shortest paths in graph

    • Dijkstra’s algorithm

      • Single-source shortest path

      • Weighted graph with non-negative weights

      • Requires a priority queue ADT