Computer Science 269

CSC 269 Study Guide for Final Examination

  1. Be familiar with the notation of asymptotic complexity, i.e., O, Omega, and Theta, and be able to answer simple questions concerning them.
  2. There will be some snippets of code where I will ask you to give the time complexity.
  3. Be prepared to reproduce one or more small sections of C++ code that you turned in for programming assignments.
  4. Be able to describe the following searching and sorting algorithms in detail:
    1. Linear search.
    2. Binary search.
    3. Selection sort.
    4. Insertion sort.
    5. Heapsort.
    6. Mergesort.
    7. Polyphase mergesort.
    8. Quicksort.
  5. Be prepared to discuss implementations of priority queues that we went over in class in detail, in particular:
    1. Array and linked list implementation of a stack.
    2. Array and link list implementation of a queue.
    3. Array implementation of a heap.
  6. Be prepared to discuss each of the implementations of a search structure that we went over in class in detail, in particular:
    1. Unsorted list.
    2. Binary search tree, with or without balancing.
    3. B-tree, and its variations.
    4. Hash Table, closed or open.
  7. Be famliar with trees and graphs, including various forms of traversal.
  8. Kruskal's algorithm.
  9. Union/find.
  10. Topics about arrays, including row-major order and column-major order.