Question 1:

i. Convert the following decimal numbers to base 4, and then to base 6

a) 2236

b) 1372.628 (answer should include 5 places for fractional values)

ii. Perform the following arithmetic operations

a) EBA3816 + 3BC2316

b) 54318 - 5638

c) 1101012 110012

Question 3:

Let ???? = {???? |1 < ???? < 12}. For any positive integer ???? we define the set ???????? by ???????? = {???? ????|???? ???????? divisible by ????}

i. Give the sets ????3, ????4 and ????5 explicitly in terms of their elements.

ii. Give ????2 ????1.

iii. Write down the Cartesian product ????5 ????3 in terms of its elements.

iv. Give the power set of ????3

v. By using set theorem, membership table, Venn Diagram, and arbitrary elements, establish the following for all sets X, Y, and Z: (???? ????) (???? ????) = ???? ????

Question 4:

Answer i to v using the list below: 9, 3, 7, 5, 2, 1

i. Sort the list using Insertion Sort algorithm. How many comparisons will be performed? Give the intermediate list after each iteration.

ii. Sort the list using Quicksort algorithm, using the first element as a pivot. Give the intermediate list after each iteration. Underline the pivot elements, and use an asterisk (*) to mark the elements in their final positions. How many comparisons are needed in this case?

iii. Sort the list using Bubble Sort algorithm. How many comparisons and exchanges were performed when the list was finally sorted? Show the list obtained at each step.

iv. Using the Selection Sort algorithm, arrange the list in ascending order. What is the total number of comparisons made when the list was finally sorted? Present the intermediate list obtained during the sorting process.

v. Arrange the list in increasing order using Merge Sort algorithm. Show the number of sublists created at each depth and the intermediate lists during the merging process. What is the total number of comparisons made when the list is finally sorted?

Question 5 - Big O

Use the definition of Big-O notation to show that:

i. ????(????) = ????3 7???? 5 is O(a^3)

ii. ????(????) = (???? + 3)(2????^2 + 3???? + 1) is O(n^3)