$1.(10$ points$)$ Consider the problem of scheduling $\backslash ($ n $\backslash )$ jobs of known durations $\backslash ($ t$\_\{1\},$ t$\_\{2\}\backslash$ldots $\backslash )...$ for execution by a single processor. The jobs can be executed in any order, one job at a time. You want to find a schedule that minimizes the total time spent by all the jobs in the system. $($The time spent by one job in the system is the sum of the time spent by this job in waiting plus the time spent on its execution.$)$ Design a greedy algorithm for this problem.

Consider $4$ jobs with durations $\backslash ($ t$=[4,3,2,1]\backslash ).$

Now, calculate the waiting times and total time spent for each job:

$-$ Job $1$: Waits $0$ time, executes for $4$ units, total time $\backslash (=4\backslash )$

$-$ Job $2$: Waits $4$ time units, executes for $3$ units, total time $\backslash (=4+3=7\backslash )$

$-$ Job $3$: Waits $\backslash (4+3=7\backslash )$ time units, executes for $2$ units, total time $\backslash (=7+2=9\backslash )$

The total time spent by all jobs $\backslash (=4+7+9+10=30\backslash )$

a$.(10$ points$)$ Code implementation

b$.(5$ points$)$ Screenshot

$2.(15$ points$)$ Apply Prim's algorithm to the following graph.

a$.(10$ points$)$ Code implementation

b$.(5$ points$)$ Screenshot $3.(15$ points$)$ Apply Kruskal's algorithm to find a minimum spanning tree of the following graphs.

a$.(10$ points$)$ Code implementation.

b$.(5$ points$)$ Screenshot

$4.(15$ points$)$ Solve the following instances of the single$-$source shortest$-$paths problem with vertex a as the source.

a$.(10$ points$)$ Code implementation.

b$.(5$ points$)$ Screenshot

$5.(15$ points$)$

a$.(5$ points$)$ Construct a Huffman code for the following data:

b$.(5$ points$)$ Encode $\backslash ($ A B A C A B A D $\backslash )$ using the code of question $($a$).$

c$.(5$ points$)$ Decode $100010111001010$ using the code of question $($a$).$

$6.(15$ points$)$ Given two integers k and n $,$ find all possible combinations of k unique positive integers from the set $\backslash (\backslash \{1,2,\backslash$ldots$,9\backslash \}\backslash )$ that sum up to n$.$ Each combination must consist of distinct integers, and the integers within each combination must be in ascending order. Write a function combinationSum$3$ that takes in two parameters, k and n $,$ and returns a list of lists, where each inner list represents a valid combination of integers.

a$.(10$ points$)$ Code implementation.

b$.(5$ points$)$ Screenshot for $1)\backslash (\backslash$mathrm$\{$n$\}=7,\backslash$mathrm$\{$k$\}=3$ ; $2)\backslash$mathrm$\{$n$\}=9,\backslash$mathrm$\{$k$\}=3\backslash ).$

$7.(15$ points$)$ Given a sequence nums, that may contain duplicate numbers, return all unique permutations of the sequence in any order. Write a function permuteUnique that takes a list of integers and returns a list of lists, where each inner list represents a unique permutation of the input sequence.

a$.(10$ points$)$ Code implementation.

b$.(5$ points$)$ Screenshot for $1)$ nums $\backslash (=[1,1,2]\backslash )$; $2)$ nums $\backslash (=[1,2,3]\backslash ).$