The first test in this course will take place on Friday, February 20. It will cover material from the first four chapters as well as the lab and assignments. You can expect a mixture of different types of problems: definitions, short-answer essays, longer conceptual essays, and programming. Programming questions might, for example, ask you to use an abstract data type to accomplish some task or to write an implementation for an ADT. You should expect at least one question where you are given some code and asked to analyze its run time. You are not responsible for any details of C++ templates and the standard template library, but you should understand the basic concepts (which might be tested in definitions and essay questions).
Important terms and ideas for this test include:
algorithm implementation of an algorithm analysis of algorithms run-time efficiency worst-case, best-case, average case growth rate of a function "Big Theta" growth rates of common functions (power, exponential, logarithm) linear search and binary search "Big Omega" and "Big Oh" empirical testing of run times abstract data type implementation of an ADT ADT's in C++ C++ header (.h) files dynamic array implementation of stacks standard template library linked lists header node for a linked list tail pointer for a linked list doubly-linked list linked list implementation of list ADT priority queues heaps a heap as a full binary tree array representation of a heap heap implementation of priority queues using heaps for heapsort the "Heapify" algorithm the heap insert algorithm records fields in a record key field in a record sorting by key stable sort in-place sort the QuickSortStep algorithm using a stack instead of recursion comparison sort linear time sorting run-time analysis of sort algorithms comparing various sort algorithms |
selection sort
insertion sort
bubble sort
merge sort
heapsort
quicksort
radix sort
the stack ADT
push, pop, isEmpty
the queue ADT
enqueue, dequeue, isEmpty
the list ADT
begin, end, next, prev,
get, set, insert, remove;
"position" in a list
the priority queue ADT
insert, remove
|