112 Final Review Topics

The final is cumulative.  Read the Midterm 1 and Midterm 2 review pages for a list of topics covered before the second midterm.

Topic areas:

Lectures (1 – 10, priority queues (ch 11), hash tables (ch 12), templates, standard template library, Appendix A)
All assignments
All labs in which I did a lecture
Solving problems (some you will not have seen before)

The rest of this page contains those topics not on the Midterm 1 and Midterm 2 review pages.

Overview:
This will be a hard exam.

There is a lot of material, in order to be ready to move on, you need to be able to bring it all together.

I will ask some questions that will require you to solve a problem instead of just regurgitating material from the lecture and the textbook. In other words you will have to solve problems I have not done in class.  For example:

Averaging the elements in a linked list

Finding the largest element in a tree

Moving an element in a doubly-linked list


Exam Topics from Lecture:


Object Orientation
public/protected/private
inheritance
virtual functions
pure virtual functions

Algorithmic Complexity
vocabulary
run time complexity
worst case analysis
average case analysis
order of magnitude
big-O notation

what is the run-time complexity of the given code

sorting
you do not have to recall the sorting algorithms but given the algorithm you should be able to explain how it works and its run-time complexity

Trees
vocabulary
node
edge
root
parent/child
sibling
height
binary search tree

implementing tree functions (both recursive and non-recursive)
search in a tree (both an ordered binary search tree and a non-ordered tree)
inserting into a tree
removing from a tree

Hast Tables
basic idea of how they work
run-time complexity for insert and lookup
concept of a hash function
what to do if there is a collision (two data have the same hash value)
Exam Topics from Labs:

All lab related questions will be on labs before the second midterm.
See  Midterm 1 and Midterm 2 review pages.


Exam Topics from Assignments:

p6: shapes -- inheritance
programs using inheritance

p7: train -- trees
inserting into a tree
searching into a tree
lookup in a tree