Question 1:
Quick sort:
•	Choose a pivot
•	Rearrange the array and partition it so that every element in the left segment is smaller than the pivot and every element in the right segment is larger than the pivot
•	Recursively process left and right segments
•	Recursion stops when the length of the array segment is less than or equal to one

Partition:
•	Let us assume that the first element is the pivot
•	start an i-pointer from second element
•	start a j-pointer from the last element
1.	i-pointer keeps on incrementing until the element it is pointing to is greater than pivot
2.	j-pointer keeps on decrementing until the element it is pointing to is less than or equal to pivot
•	When I and j pointers stop we swap the elements an repeat steps 1 and 2, until the pointers cross or meet
•	See the illustration from the board

Question 2:
::::::::::::::
numtree.h
::::::::::::::
#ifndef NUMTree_
#define NUMTree_
#include "binary.h"

class NumTree: public BinaryTree<int>
{
        void build(BinaryTreeNode<int> *, int n);
        public:
        void build(int n);
};
#endif
::::::::::::::
numtree.cpp
::::::::::::::
#include <string.h>
#include <stdlib.h>
#include "numtree.h"
void NumTree::build(int n)
{
        if(n >= 1)
        {
                root = new BinaryTreeNode<int>;
                build(root, n);
        }
}
void NumTree::build(BinaryTreeNode<int>* t, int n)
{
        t->data = n;
        n /= 2;
        if(n >= 1)
        {
                t->LeftChild = new BinaryTreeNode<int>;
                build(t->LeftChild,n);
                t->RightChild = new BinaryTreeNode<int>;
build(t->RightChild,n);
        }
}

Question 3:
#include “course.h” // no marks deducted
#include “hashtable.h” // no marks deducted
void main(void)
{
	HashTable<CourseRecord> Q3;
}

course.h
#include “compare.h” // no marks deducted
struct CourseRecord
{
	char Number[7];
	char Title[36];
	char desc[201];
	int hash();
};

CourseRecord::hash()
{
	int sum = 0;
	for(int j = 0; j < 7; j++)
		sum = sum + (Number[j] - ‘0’);
	return sum;
}

bool operator==(const CourseRecrod& l, const CourseRecrod& r)
{
	return (!strcmp(l.Number,r.Number));
}
Question 4:
# ifndef LEAF_
# define LEAF_
# include "bstree.h"

template <class T>
class LeafTree : public BSTree<T>
{
        int leaves(BinaryTreeNode<T>* t);
        public:
        int leaves(){return leaves(root);}
};

template <class T>
int LeafTree<T>::leaves(BinaryTreeNode<T>* t)
{
        if(!t) return 0;
        if(!t -> LeftChild && !t->RightChild) return 1;
        return leaves(t->LeftChild) + leaves(t->RightChild);
}
#endif