We can implement a queue, Q$,$ using two stacks S$1$ and S$2.$

$($a$)$ Use pseudo code to describe the inQueue method $($insert an item into

Q$).3\%$

$($b$)$ Use pseudo code to describe the deQueue method $($delete the first

one from $Q$

$($c$)$ What is the worst case cost required for deQueue. $5\%$

$($d$)$ What is the amortized cost for deQueue. $6\%14\%$

$(1)$ Use Dynamic programming technique to solve the set$-$partition problem.

See the problem definition below.

$($Define the object function, write the recursive relation, give the initial condition, illustrate the table,

indicate where the answer is$,$ and estimate the time complexity and space complexity.$)$

$(2)$ Is the algorithm in part$(1)$ a polynomial time algorithm? Explain.

Set$-$partition problem:

Given a set $S$ of $n$ positive integers, $S=\{s_1,s_2,s_3,$dots,$s_n\},$

is there a partition of $S$ into two disjoint subsets A and $S-$A such that

${\displaystyle \underset{s_i\text{i}\text{n}\text{A}}{\overset{?}{}}}{s}_i={\displaystyle \underset{s_i\text{i}\text{n}\text{S}-A}{\overset{?}{}}}{s}_i?10\%$

$(1)$ Give a Huffiman binary coding tree for the following data: ABCATDABEBAAAAAABEB.

Compute the total number of bits to send this message.

$(2)$ Give a Huffiman ternary coding tree for the data in part $(1)\mathrm{.}14\%$

$(1)2\%$ Describe the Bellman$-$Ford algorithm for solving the shortest path problem.

$(2)1\%$ State the time complexity. Is it a polynomial time algorithm?

$(3)4\%$ Consider the graphs containing negative weight cycles. Can Bellman$-$Ford algorithm find a

shortest path between two nodes? Explain or prove.

$(4)3\%$ Is there a polynomial time algorithm to find a negative weight cycle? Explain or prove.

$(5)4\%$ Is there a polynomial time algorithm to find the largest negative weight cycle? Explain or prove.

$($A negative weight cycle such that the absolute value of its total weight is maximum..$)$When we implement a binary search tree, we need to define a class or a

struct for node. In a node, we have three fields, one for data, and two

pointers leftChild and rightChild. If we have a binary search tree of

$n$ nodes, show that there must be $n+1$ unused pointer fields, regardless

the tree looks like. $7\%$