1. How many comparisons between names are made if the merge sort algorithm and 12.8) is applied to the list Alice, Bob, Carol, and David? How many are required if the list is Alice, Bob, Carol, David,...

1.
How many comparisons between names are made if the merge sort algorithm and 12.8) is applied to the list Alice, Bob, Carol, and David? How many are required if

the list is Alice, Bob, Carol, David, and Elaine?

2.
How does a universal Turing machine function? Explain with an example.

3.
Design an algorithm for finding integer solutions for equations of the form
x2 +
y2 =
n,

where
n
is some given positive integer. Determine the time complexity of your algorithm.