2. (10 pts.) Counting: For all 3 problems below, Julia has EXACTLY 6 hours to binge-watch some episodes for various shows.  You must show work that supports your final answer to get any credit.  You can either upload your work as a scan/picture OR just type it in using a text-based approach (i.e. nCk for n Choose k, nPr for n Permute r, 3^2 for 3 squared, etc.)

2.1. Assuming that for a given show she always watches episodes in sequential order (never out of order), how many orderings exist for her to watch 8 half-hour episodes from show A and 2 one-hour long episodes from show B (assuming she can switch back and forth between shows as she pleases).

2.2. Now assume she (strangely!) is willing to watch the episodes of the same show in ANY order (not sequentially). How many orderings exist of the ten total episodes described  in the previous part of the problem.

2.3. Assume she again watches episodes in (sequential) order. There are two unique shows (C and D…forget about A and B for this question) where one has at least 12 half-hour long episodes and the other has at least 3 two-hour long episodes which     she can watch in any (mixed) order. How many orderings exist of the episodes that she will watch?

3. (10 pts.) Number Theory - Show your work in the same manner and with the same requirements as the previous problem.

3.1. Find the gcd(396,168) using Euclid's algorithm (showing your work and demonstrating your  understanding of the algorithm .

3.2. Find the smallest two integer such that 396x + 168y = gcd(396,168) demonstrating you understand the method taught in class.

4. (10 pts.) Trees and Recursion.  Given a binary tree of non-negative integers, write a recursive function that returns TRUE if the sum of all nodes in the left and right subtree of EACH node is an even number.  If the sum of nodes in the left and right subtree of even 1 node is odd, return false.  Non-existent nodes have an implicit value of 0. Also, an empty  tree should return `true`.  No loops are allowed so you must use recursion.

Complete your code in the linkedeventree.cppand submit that file. A portion is reproduced below.

// You may NOT change this struct definition

struct Node {

int val;

Node *left, *right;

};

// You may NOT change this function prototype

bool evenTree(Node* root);

// You may add any prototypes of helper functions here

// Now implement the evenTree function and any necessary helpers

// -------------------- YOUR CODE HERE  ------------------

5. Hashing (10 pts.)

Consider a hash table that uses open-addressing (some form of probing) and the same table structure (vector of HashItem pointers) from homework 6 as well as a similar HashItem structure (reproduced below for your benefit).  Now write a function that will compute how many buckets of the hash table would be empty if chaining / closed-addressing had been used instead (for the same table size).

You do not necessarily need to convert the table to use chaining, simply calculate how      many locations / buckets would be empty. Your function must run in Theta(m) time where `m` is the table size. You may declare other arrays / data structures as needed.

Complete your code in the linkedchains.cppand submit that file. A portion is reproduced below.

// HashItem definition used by the hash table

template 

struct HashItem {

typedef std::pair ItemType;

ItemType item;

bool deleted;

};

/**

* @brief FUNCTION YOU NEED TO WRITE

* Computes the number of empty buckets that would exist if

* the hash table used chaining rather than open-addressing (probing). *

* @param [in] table Hash table of pointers to HashItems. An entry

*  is occupied if the pointer is non-NULL

* @param [in] h Hash function that supports operator()(Key) and returns

*   an unsigned integer of arbitrary size

* @return the number of buckets/chains that would be empty had chaining

*   been used rather than open-addressing

*/

template

size_t numEmptyIfChaining(const std::vector< HashItem* >& table, Hash h);