Review (2/2)
•	Binary Trees
•	Two programming questions
•	Recursive (see midterm or creation of binary expression tree)
•	Iterative (see the LevelOrder)
•	If you understand the use of recursion and iteration, you will be able to get 60-70% of the marks.
•	Skills looking for:
•	Creating a descendant
template <class T>
class NewBin : BinaryTree<T>
{
};
•	Passing parameters by value, const reference, or reference
•	Proper declaration of a variable.
•	e.g. HashTable<courseRecord> H;
•	Proper use of all the operations
•	Use of recursion and iteration for BinaryTree and its descendants.
•	100 marks, nine questions, virtually all the material that didn’t appear in the midterm will be on the final.
•	Binary Search Trees
•	Insertion and deletions
•	No need to reproduce the code, but should understand it
•	See the board for an example
•	AVL tree
•	definition
•	Insertion (you will be expected to insert an item)
•	See the board for an example
•	Binary Expression Trees
•	Given a postfix expression, create a BXTree
•	Evaluate a BXTree
•	Evaluate a postfix expression
•	Convert infix to postfix
•	Heap sort
•	Graphs
•	How to represent a graph using an adjacency matrix?
•	Dijkstra’s algorithm (detailed execution)
•	B-Tree
•	m-way search trees: insertion, deletion, search, height
•	definition and height of a B-Tree
•	P, NP, NP-complete
•	What are these?
•	How to prove
•	P=NP,
•	P!=NP,
•	a given problem PI is NP-complete?
•	Divide and conquer, greedy algorithms
•	examples
•	pawan.lingras@stmarys.ca and lingras@sprint.ca