15-110 Fall 2010 Homework 1
Due Sunday, 29-Aug, at 4pm (no late submissions accepted!)

Read these instructions first!

· Include your name, AndrewID, and section clearly on the top of each file in your assignment.

· Place all your solutions in a single file named Hw1 (with whatever extension is appropriate for the format you choose, such as Hw1.txt or Hw1.html, etc). You must use one of these file formats (that are all readable by OpenOffice, in case you were wondering): plain text (txt), or Word (doc or docx), OpenOffice (odt), or PDF. No other file formats will be accepted.

· Show your work. Correct answers without supporting calculations will not receive full credit.

· How to submit:

o Start at the course web site (http://www.cs.cmu.edu/~110)

o Select the Autolab link

o Select the Hw1 link

o Select the Submit link

o Click on the “Choose File” button

o Find your Hw1 file that you are submitting

o Click on the “Upload” button

o If it worked, you will see this text: Submission Accepted

o Your submission is not completed until you see that text!!!

· Q & A
Q: Can I submit multiple times before the deadline?
A: Yes, but only the last submission is graded.
Q: What if I’m having problems?
A: Email your team’s CA’s. They will help you!
Q: Are submission that are just a few seconds late ok?
A: No. The deadline is exact, and no late submissions are accepted.
Q: How do I get my grade and the graders’ comments?
A: Go back to Hw1 in Autolab and elect “view scores”.

· Once again: Late submissions will be rejected.

· And one last reminder: show your work or you will not receive full credit.

1. Representation [25 pts total; 5 pts each]

A. Convert 1234 from decimal to binary.

B. Convert 01101101 from binary to decimal.

C. Braille is a system of representing symbols that is readable by blind and vision-impaired people. The basic Braille system uses 6 dot positions to describe each symbol, where each dot can be raised or not.

1. How many symbols can be represented in this way?

2. Describe a system for converting any basic Braille symbol into a single integer.

3. Convert the string “yes” into Braille, and then – using your system – convert these Braille symbols into 3 integers.

D. Convert the 5-character string “I do!” into a zero-terminated list of integers (using ASCII values).

E. True or False (1 point each):

1. If a binary number is of the form 1000…000 (any number of 0’s), then it must be a power of 2.

2. The same exact bit sequence can be interpreted as numbers, text, audio, video, or anything else. Bits alone carry no semantic information about how to interpret them.

3. log₂N basically means “the number of times you can divide N by 2 (and still get an integer result)”.

4. As computers move from 32-bit to 64-bit architectures, the largest integer that can be represented is doubled (that is, the largest value that can be represented using 64 bits is twice as large as the largest value that can be represented using 32 bits).

5. We use the Data Abstraction Hierarchy to allow us to reason over data more naturally or intuitively, even though inside a digital computer all data is ultimately represented only as 1’s and 0’s.

2. Algorithm: Binary Search [25 pts total; 12.5 pts each]

A. Say you had to find the square root of 73, only you did not have a calculator handy. Here is one way you could do it using just simple arithmetic (+,-,*,/). In this problem, you will find the approximate square root of 73 using binary search. To do this, first observe that we know the answer lies between 0 and 10 (right?). So our first guess will be the middle of that range, or 5. We square our guess and get 25, which is too low, so now we know the answer lies between 5 and 10. And so we continue with a guess of 7.5. Continuing with this approach, list every guess (starting from the range (0,10)) until you have found a value that, when squared, is within 0.5 of 73 (that is, is in the range [72.5, 73.5]).

B. As you know, binary search is an efficient way to guess a number in a fixed range, say between 1 and 100 (or 1 billion, or whatever). Here, you will modify binary search to work over an unknown range. So you are to guess a number (an integer, to be precise), but you cannot presume anything about that integer’s value (no upper bound and no lower bound).

1. Describe an efficient algorithm that will play the number-guessing game, only for an arbitrary integer N (where N is unbounded, and may be negative). Note: by “efficient”, we mean that the algorithm requires at most O(log|N|) guesses.

2. Show that your algorithm requires at most O(log|N|) guesses.

3. Provide all the guesses, in order, that your algorithm would make to find the number -138.

3. Algorithm: Sorting (25 pts)
The following questions pertain to snapshots of xSortLab.

A. Selectionsort Trace (12.5 pts; 2.5 pts per question)

In this example, selectionsort just compared element 3 with element 5. Now answer the following questions:

1. Which are the next two elements to be compared?

2. Which is the next element that will be marked as “Max”?

3. Which are the next two elements to be swapped?

4. Why is element 16 black rather than gray?

5. Exactly how many more swaps will be made from this point forward until the list is sorted?

B. Mergesort Trace (12.5 pts; 2.5 pts per question)

In this example, mergesort just compared element 2 with element 6, and copied element 2 into element 3 of the temp list.

1. What is the next element to be copied into the temp list?

2. Which are the next two elements to be compared?

3. Element 4 will be copied into the temp list before element 9, even though element 9 is smaller than element 4. Explain.

4. Each time the temp list is copied back to the original list, mergesort has completed one “pass”. How many passes are required to sort the given list of 16 elements? How many would be required for a list with 1 billion elements?

5. Why does mergesort require a temp list? Specifically, why not just swap elements directly in the original list in the same way selectionsort does?

4. Analysis (25 pts)

A. Function Families (15 pts; 3 pts each)

Answer each of the following problems with one of O(logN), O(N), O(NlogN), or O(N²).

1. Say that there are N people in a room and everyone shakes hands with everyone else (but nobody shakes hands with themselves). How many total handshakes were there?

2. A single-elimination tournament with 64 teams requires 6 rounds. More generally, however, how many rounds are required if there are N teams?

3. You have a sorted list with N elements in it. You have a second, unsorted list also with N elements in it, and you want to check whether every element in the second list also occurs in the first list. How many steps (comparisons) are required?

4. How many steps (arithmetic operations) are required to find the average of an unsorted list of N numbers?

5. How many steps (arithmetic operations or comparisons) are required to find whether or not the average of an unsorted list of N numbers actually occurs in that list? For example, for the list [7,2,5,6], the average is (7+2+5+6)/4, or 5, which does occur in the list, so you would say yes. Conversely, for the list [7,3,8], the average is (7+3+8)/3, or 6, which does not occur in the list, so you would say no.

B. Sorting Analysis (10 pts; 5 pts each)

1. Briefly but explicitly explain why selectionsort requires O(N²) steps.

2. Briefly but explicitly explain why mergesort requires O(NlogN) steps.

5. Bonus/Optional (up to 6pts)

These problems are entirely optional. You can score 100% on this assignment without doing (or even reading!) these problems.

A. Base-K [2 pts]

Do some web searching and read about converting between bases. Then…

1. [0.5pt] Convert 1234 from decimal to base 7.

2. [0.5pt] How many digits are required to represent a number N in base 7?

3. [1pt] Just as binary search divides a list into 2 parts and eliminates half the list on each pass, we could instead use ternary search, and divide the list into 3 parts and eliminate 2/3rds of the list on each pass. Show that this would result in no more than a “constant time speedup” – that is, that there is some constant C such that ternary search is no more than C times faster than binary search regardless of the size of the input. Interestingly, due to its increased complexity, in practice C turns out to be about 1 (that is, ternary search is about the same speed as binary search, which is why we don’t bother with it).

B. 10’s complement and 2’s complement [2 pts]

Do some web searching and read about 10’s complement and 2’s complement. Then…

1. [0.5pt] Show how to compute 5873 - 3984 by converting -3984 to 10’s complement and then adding.

2. [0.5pt] Say we are computing X - Y in this same fashion using 10’s complement. Explain how we can detect that the result is negative (that is, Y>X), and then what we should do to obtain the final answer in decimal (and not 10’s complement).

3. [1pt] In C++ and in Java (languages we are not learning this semester), integers are represented using 32-bit 2’s complement. The largest possible value in that representation is about +2.1 billion (well, it is exactly 2³¹-1). When we try to add 2 billion to itself in Java, we do not get 4 billion, but rather a negative number!

· Very briefly, why do we get a negative number?

· Exactly which negative number do we get?

C. Euclid and Binary GCD [2 pts]

Do some web searching and read about the Euclid GCD algorithm and the Binary GCD algorithm. For example, here is a helpful pdf with some worked-out examples. Then…

1. [0.5pt] Use the Euclid GCD algorithm to find the gcd of 410,228 and 123,970. Show each intermediate step.

2. [0.5pt] Use the Binary GCD algorithm to find the gcd of 410,228 and 123,970. Show each intermediate step.

3. [0.5pt] Do some web searching to find a GCD algorithm that is distinct from Euclid’s or the Binary algorithm (so do not , for example, find the “extended” versions of these algorithms). Include a citation to a web site describing the algorithm you selected, and then to find the gcd of 410,228 and 123,970 using that algorithm.

4. [0.5pt] Briefly compare the previous 3 algorithms – which is most efficient? Clearest? “Best”? Why?