Review
•	Recursion: Trace a recursive function using recursion tree
•	You can try variations of the following program
#include <iostream.h>
void function(char ch, int n)
{
        if(n > 0)
        {  function(ch-1,n-1); cout << ch; function(ch+1,n-1); }
}

void main(void)
{         function('m',4);  cout << endl; }
•	See the board for the example
•	In the exam, you must draw the recursion tree. Guessing the output carries no marks.
•	Recursion
•	Situations suitable and unsuitable for recursion
•	Suitable
•	Divide and conquer (Mergesort, Quick sort, Strassen, Binary Search)
•	Postponing the work (Hanoi)
•	Unsuitable
•	Recursion tree is a chain (factorial)
•	When there are duplicates in the recursion tree (Fibonacci)
•	BNF
•	Context free grammars
•	All the modern programming languages have CFG
•	Given a grammar draw the derivation tree
•	See LEC5.DOC.
•	You will be given a different grammar. You will be expected to identify, terminal symbols, non-terminal symbols, and draw derivation (parse) tree for a string. You must answer questions based on given grammar.
•	Hash Table
•	Definition of the ADT and corresponding C++ class definition
•	You must know all the member functions
•	Understand the code, but memorize the header. There is the possibility of an information sheet (if Cherno brings it to me on time, it will be on the web). I will attach a copy of the information sheet to the exam. YOU DO NOT BRING YOUR OWN INFORMATION SHEET.
•	Binary tree
•	Very important for difficult programming questions
•	One recursive, one iterative
•	Do not reproduce an existing function
•	Recursive: Look at the question from midterm
•	Iteration: Do the level order in reverse (per level), that is items are printed from right to left per level