Q$1(30)$: Compute the list of all permutations of $[$a$,$ b$,$ c$,$ d $]$ using the Johnson$-$Trotter

algorithm. Show your work.

Q$2(30)$: For each of the following problems: design a reduction algorithm that solves the problem.

Prove the time efficiency class of your algorithm. Hint: Your algorithm should use a hash table

or sorting algorithm.

$($a$)$ input: two lists $L$ and $R,$ each representing a set of distinct elements

output: a list $S$ representing $LR$