UNLV CS 477/677 Spring 2011 First Examination

Date: Thursday, February 17, 2011, 4:00 PM.

1. Asymptotic classes: O, Omega, and Theta notation.
2. Recurrences.
   1. Anti-derivative method. Sample question. Answer to sample question.
   2. Master Theorem.
   3. Substitution. Sample question. Answer to sample question.
3. Well-known sorting algorithms. Sample questions. Answer to sample questions.
   1. Bubblesort.
   2. Insertion sort.
   3. Selection sort.
   4. Mergesort. Sample question. Answer to sample question.
   5. Quicksort. Sample question. Answer to sample question.
   6. Polyphase mergesort. Sample question. Answer to sample question.
   7. Heapsort. Sample question. Answer to sample question.
4. Order statistics. (Finding the k^th smallest item in a set of n items, without sorting.)
5. Elementary data structures. Sample questions.
   1. Linked lists.
   2. Doubly linked lists.
   3. Cicular linked lists.
   4. Stacks.
   5. Queues.
   6. Heaps.
6. Hashing.
7. Abstract data types (ADT). Sample questions. Answer to sample questions.
   1. Stack.
   2. Queue.
   3. Search Structure.
   4. Array.
8. Huffman's algorithm.