CSC 321: Data Structures
Fall 2017

Midterm Review

Thu, Oct 12
  • The test will include extra points (Mistakes Happen!), e.g., 103 or 104 points, but graded on a scale of 100.

Types of questions
  • factual knowledge: TRUE/FALSE, multiple choice
    TRUE or FALSE: When searching for an item in a list, the best case performances for both sequential search and binary search occur when the item is at the front of the list.
  • conceptual understanding: short answer, discussion
    In general, sorting a list of N comparable items requires an O(N log N) algorithm. However, we discussed two specialized sorts, frequency lists and radix sort, that can do better but only if the data has certain properties. Describe one (1) of these specialized sorts and the properties the data must have in order to allow for improved efficiency.
  • synthesis and application: explain/debug/analyze algorithm/code, trace/modify algorithm/code
    One way to determine if a list of numbers has any duplicate values is to first sort the list, then traverse it looking for adjacent identical values. Complete the definition of a method that implements this approach (you may use Collections.sort for the sorting step). What is the Big-Oh complexity of your method?
  • Fall 2015 Midterm Exam
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	
    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
    sequential search: O(N) worst/average case, O(1) best case
    binary search: O(log N) worst/average case, O(1) best case
    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