CSC 321: Data Structures
Spring 2024

Midterm Review

Tue, Feb 27
  • The test will be in-person, via Blueline.
  • You must bring a laptop to class (or use one of the lab machines).
  • It will be graded out of 100 points, but there will be 104 points available. So, you can miss 4 points and still be perfect!
Types of questions
  • factual knowledge: TRUE/FALSE, multiple choice
  • conceptual understanding: short answer, discussion
  • synthesis and application: explain/trace/modify code, evaluate the efficiency of a code segment, ...

    There is a practice mini-test in Blueline with sample questions. It does not count towards your class grade.
Study advice
  • review online lecture notes
  • review the online texts (if not mentioned in class, won't be on test)
  • look over quizzes, homework assignments
  • reference other sources for examples, different perspectives
Course material 
Java review
  class, object, fields, methods, private vs. public, parameters
  variables, primitive vs. objects, expressions, if, if-else, while, for
  object-oriented design: cohesion, coupling
  String, Math, arrays, ArrayList, generics
  interfaces, List, LinkedList, iterators
  searching and sorting, algorithm efficiency, recursion
  interfaces, inheritance, polymorphism

Data Structures
  Collection interface, many useful static methods in Collections  
  List interface (extends Collection)
    ArrayList (implements List): underlying array representation
      O(1) add/remove at end, O(N) add/remove from beginning/middle
      O(1) access, O(N) search
    LinkedList (implements List): underlying doubly-linked list representation
      O(1) add/remove at beginning/end, O(N) add/remove from middle
      O(1) add/remove if have access to location, O(N) access/search
  iterators
    Iterator interface: hasNext, next, remove
    ListIterator interface: hasPrevious, previous, add, set
    used by the enahnced for loop to traverse the list efficiently
  Stack class (extends Collection, implements List)
    FILO/LIFO list
    operations: push, pop, peek, empty
  Queue interface (extends Collection)
    FIFO/LILO list
    operations: add, remove, peek, empty
    implemented by LinkedList class
  linked structures
    nodes, references
    singly-linked lists, next references, front and/or back references
    doubly-linked lists, previous & next references, front & back
    dummy nodes
      
Algorithm Analysis
  best vs. average vs. worst case analysis
  big-Oh notation
    intuitive definition, formal definition
    rate-of-growth analysis
    big-Omega, big-Theta
  recurrence relations for analyzing recursion
    unwinding a recurrence relation
  searching
    sequential search: O(N) worst/average case, O(1) best case
    binary search: O(log N) worst/average case, O(1) best case
  sorting
    insertion sort: O(N2) worst/average case, O(N) best case
    selection sort: O(N2) worst/average/best case
    merge sort: O(N log N) worst/average/best case
    quick sort: O(N log N) average/best case, O(N2) worst case
    specialized sorts
      frequency list (if limited range of values): O(range * N)
      radix sort (if can compare by digit/char): O(maxLength * N)
  counting techniques
    rules: bijection, product, generalized product, sum, division
    binomial coefficient, pigeonhole principle
  proof techniques
    direct proof, proof by contradiction, proof by induction