Midterm Review
•	March 1st (first class after the break)
•	50 minutes (flexible, I will try to be here 10 minutes early and stay extra 10 minutes)
•	Four questions. Significant emphasis on programming. Minor syntax errors will be ignored.
•	Recursion
•	Simple examples, factorial, fibonacci, tower of Hanoi
•	When to use recursion and when not to use recursion.
•	See the board for recursion tree for factorial it is a chain, recursion not recommended.
•	See the board for recursion tree for fibobnacci it has duplicate calls, recursion definitely not recommended.
•	Every recursive function can be written iteratively, but sometimes iterative version as more difficult to follow.
•	Question: Draw recursion tree for a given recursive function.
•	Merge sort and Quick sort
•	Question: Given a list of numbers explain how these number are sorted using one of the sorts
•	Question: Worst-case and best-case time analysis
•	BNF: Given a grammar, draw derivation trees for a give string (Question)
•	Hashtables
•	ADT: Know all the operations
•	Question:, know how to create a hashtable for a given record. Completely understand assignment# 2.
•	Understand the design, implementation, and time analysis for descriptive questions.
•	Binary tree
•	Definition
•	Properties
•	Operations
•	Linked implementation
•	Contiguous implementation (no programming). Given an array show the binary tree. Given a binary tree show the array.
•	Question three types of programming questions
•	See LEC20.RTF
•	Important note: If you change the values ot t in the recursive function you need to pass t by reference. Syntax will look like f(BinaryTreeNode<T>*& t)
•	This is only necessary if you have new or delete operations on t. If you new and delete operations on t’s leftchild ot rightchild, you don’t need the &
•	Look at build for BXTree and Delete for BSTree
•	Binary expression trees
•	Evaluation of prefix expressions using BXTree
•	Evaluation of postfix and infix expressions using stacks
•	Question: Given an expression show how it will be evaluated
•	Binary search tree
•	Definition
•	Operations
•	How insertion, search and deletion (most important) work.