Problem $1$ Construct the Huffman code $($i$.$e$,$ the optimum prefix code$)$ for the alphabet

$\{$a$,$ b$,$ c$,$ d$,$ e$,$ f$,$ g$\}$ with the following frequencies:

Symbols a b c d e f g

Frequencies $50202725298555$

Also give the weighted length of the code $($i$.$e$,$ the sum over all symbols the frequency

of the symbol times its encoding length$).$

Problem $2$ We are given an array A of length n$.$ For every integer i in $\{1,2,3,,$ n$\},$

let bi be median of the sub$-$array A$[1..$i$].($If the sub$-$array has even length, its the median

is defined as the lower of the two medians. That is$,$ if i is even, bi is the i$/2-$th smallest

number in A$[1..$i$].)$ The goal of the problem is to output b$1,$ b$2,$ b$3,,$ bn in O$($n log n$)$

time.

For example, if n $=10$ and A $=(110,80,10,30,90,100,20,40,35,70).$ Then b$1=$

$110,$ b$2=80,$ b$3=80,$ b$4=30,$ b$5=80,$ b$6=80,$ b$7=80,$ b$8=40,$ b$9=40,$ b$10=40.$

Hint: use the heap data structure.

Problem $3$ In the interval covering problem, we are given n intervals $($s$1,$ t$1],($s$2,$ t$2],$

$,($sn$,$ tn$]$ such that S

i in $[$n$]($si$,$ ti$]=(0,$ T $].$ The goal of the problem is to return a

smallest$-$size set S $\{1,2,3,,$ n$\}$ such that S

i in S $($si$,$ ti$]=(0,$ T $]\mathrm{.}01020304050607080901001101201301401501601245376$

Figure $1$: An instance of the interval covering problem.

$1$

Your Group Id

$82313$

For example, in the instance given by Figure $1.$ The intervals are $(0,60],(0,35],(40,120],$

$(55,140],(60,120],(100,160],(130,160].$ Then we can use $3$ intervals indexed by $1,4,7$

to cover the interval $(0,160].$ This is optimum since no two intervals can cover $(0,160].$

Design a greedy algorithm to solve the problem. it suffices for your algorithm to run

in polynomial time. To prove the correctness of the algorithm, it is recommended that

you can follow the following steps:

$$ Design a simple strategy to make a decision for one step.

$$ Prove that the decision is safe.

$$ Describe the reduced instance after you made the decision.