Problem:
Question 1: State the tree (insertion) sort, odd-even transposition sort, and quicksort algorithms in 3-4 sentences each, and estimate, with suitable but brief justification, their
(i) Average case time complexities and
(ii) Their worst-case space complexities. Use known properties of binary search trees in case of tree sort and intuitive arguments about the other two to justify average case scenarios.
Question 2: Write a C++ program that asks the user for an alphabetic character. The character can be either lowercase or uppercase.
Please describe the coding of the C++ program that asks the user for an alphabetic character. The character can be either lowercase or uppercase.