15-110 Fall 2010 Quiz 1
10 Minutes

* No calculators, no notes, no books, no computers.
* Show your work.  Correct answers without supporting calculations will not receive full credit.

1.       (30 pts) Convert 42 from decimal to binary.

2.       (20 pts) Binary search requires at most how many guesses to guess a number between 1 and 20?

3.       (30 pts – 5 pts each) True/False (circle one)

A.      If a binary number is even, then its leftmost digit must be a 1.

    TRUE       FALSE

B.      Most computers represent numbers internally using decimal (base 10) digits.

    TRUE       FALSE

C.      Selectionsort requires O(NlogN) steps.

    TRUE       FALSE

D.      For large values of N, log₂N is much smaller than N

    TRUE       FALSE

E.       When looking for a  name in an unsorted list, it is generally faster to use linear search than it is to first sort the list with mergesort and then use binary search on the sorted list.

    TRUE       FALSE

F.       The sum 1 + 2 + … + N is O(N)

    TRUE       FALSE

4.       (20 pts) Short Answers (Sorting)

A.      (10 pts) In this trace of selectionsort, which are the next two elements to be swapped?

B.      (10 pts) In this trace of mergesort, what is the next element to be copied into the temp list?

5.       Bonus/Optional (up to 5 pts)

A.      (2.5 pts) About how many digits are required to represent a number N in base 13?

B.      (2.5 pts) Any positive integer less than 1 billion can be represented using only one digit in base 1 billion.  Briefly, why can’t we use this as the basis for an efficient way to represent numbers?