COS 109: Problem Set 3

Due 5:00 PM, Tuesday, Oct 10, in the box outside Room 419, CS building, or in class. Answers need not be long, merely clear so we can understand what you have done. Please submit typed material, not hand-written, if at all possible, and keep a copy for yourself just in case something goes astray. Thanks.

Collaboration policy for COS 109: Working together to really understand the material in problem sets and labs is encouraged, but once you have things figured out, you must part company and compose your written answers independently. That helps you to be sure that you understand the material, and it obviates questions of whether the collaboration was too close.

You must list any other class members with whom you collaborated.

To hand in the assignment use the drop box at https://dropbox.cs.princeton.edu/COS109_F2017/Problem_Set_3

 

1. The ASCII system for encoding characters

As we mentioned in class, text is stored in the ASCII format whereby a byte is used to represent text in order to be able to exchange text in digital form. This table shows the actual code where the labels on the rows (0--7) come before the labels on the rows (0--F). For example, the number 9 is in row 3 and column 9, so the ASCII representation for 9 is 39 in hexadecimal. Similarly, the representation for M is 4D. You will notice that the first hexadecimal number is never more than 7. This is because ASCII characters that have higher first numbers are unprintable representing various control characters.

(a) Write your name as you would (e.g. David Paul Dobkin in my case)

(b) Write the ASCII representation of your name as a sequence of bytes. This representation should consist of a series of hexadecimal numbers. Note that the space character is represented by ASCII 20.

(c) Transform the representation from part (b) into a sequence of bits that provide the bit seuence by which your name would be transmitted.

(d) The sequence of hexadecimal digits 434F53203130392069732066756E2121 contains a message. What is the message?

 

2. Bits and bytes

This problem concerns conversions among decimal, binary and hexadecimal repreesentations.

(a) For each of the numbers 31, 119, 256, 11234 in decimal, give the binary and hexadecimal representations

(b) For each of the numbers 1A, 2CB, ABCD in hexadecimal, give the binary and decimal representations

(c) For each of the numbers 1010110010001, 11110000111, 111111000111 in binary, give the decimal and hexadecimal representation

(d) If every gas station in America were to be given a unique number, how many bits would be necessary in this representation?

3. Programming exercise

In this problem, you will write a short program using the instruction set we created in class. You will begin by creating a flow chart showing how your algorithm will operate. You will then convert your chart to assembler code (i.e. code for our Toy language). Since it is difficult to be sure that a program operates correctly without running it, you will want to use the simulator I showed in class to test your code.

The simulator is located here . A few quirks of the simulator are

      (i) If a statement does not have a label, it cannot have text in the first column. So, you will want your statements to begin with a space.

      (ii) Any memory locations that you want to name should be declared within your program (typically at the bottom). This can be done by a statement (that begins in the first column) naming the variable or a statement that names the variable and then "init Val" which initializes the variable to the value Val.

      (iii) If when running your program in the simulator, you hit an infinite loop continually asking for input, the simulator will allow you to exit the running program by clicking on the button to stop asking for input. When you do this, you need to close that tab and reopen the simulator in another tab.

You will find it easier to start with something small and simple, like some of the programs in the notes, to be sure you understand how the simulator works and how to get numbers in and print them out again, before you try to solve the assigned problem.

(a) Create a flowchart and then write a program that gets one number from the keyboard, prints that number and successive lower numbers down to 0 inclusive, then stops. For instance, if the initial number is 4, the program prints 4, 3, 2, 1, 0 on successive lines. This can be done in 6 instructions, so if you find yourself writing a lot more, you're on the wrong track. Think about the class example that adds up numbers. You might it helpful to figure out the operations that have to be performed each time through the loop, then worry about how to stop the loop.

Hints:

      (i) This program requires a loop; if your program doesn't have some kind of loop, it's wrong.

      (ii) The loop has to end somehow; if your program doesn't make some test that can terminate the loop, it's wrong.

      (iii) Thus your program is likely to contain code analogous to this, though not necessarily the same:

	Top	GET
		IFZERO Done
		...
		GOTO Top
	Done	...

(b) Modify your program from part (a) to compute the sum of the numbers rather than counting down the numbers. This should result in a program that is only slightly longer.

4. Estimation problems

(a) According to this article , transactions at a supermarket checkout require 2 types of time. The transaction itself (i.e. saying hello, paying, saying good-bye, ... ) requires 41 seconds. The scanning of each item requires 3 seconds. They argue that it is better to get in line behind one person with many many items instead of getting in line behind several people with few items. Quantify their result by giving examples of tradeoffs giving situations where you would choose the longer line and others where you would choose the shorter line behind someone with many items.

(b) The article also says that Americans spend 37 billion hours a year waiting in lines. Does this number feel too high, too low or just right?

4.