CSC 321: Data Structures
Fall 2015

Midterm Review

Thu, Oct 8
  • 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
    Suppose that a class for modeling a queue has been implemented using an underlying List data structure. Would the choice of List type, either ArrayList or LinkedList, affect the efficiency of the queue methods? Explain your answer.
  • 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?
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
  GUI building

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
    Stack class (extends Collectio, 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
    if limited range of values, sort via frequency list: O(range * N)
    if can compare by digit/char, radix sort: O(maxLength * N)