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