Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CISC181(S21) Lab 2

Submission guidelines

The problems on this lab require a mix of solution types. Part 1 Problem 1 requires you to type a solution into a text box on this document. Problem 3d has a table for you to fill in and another text box. Problems 2 and 3 require you to create and submit program files called lab03_2.toy and lab03_3.toy, respectively. These are to be plain text files, as explained below. Place the following into a zip file called Lab02_solutions.zip:

· Your completed Lab02.docx file

· Your Lab02_2.toy program file

· Your Lab02_3.toy program file

· Your Lab04_4.toy program file

Upload the .zip file to onQ by the lab's due date and time.

Part 1

Instructions

In this part of the lab, you will try out a few programs written in the assembly language for the Toy computer described in the module 3 (the CPU) slides.

1. Download the file Lab02File.zip from onQ to your computer and extract the file toy.html from it.

2. Open the Toy simulator by dragging toy.html from a file listing that shows it onto an open web browser. It should open immediately.

3. Note that in a Toy program all mnemonic opcodes (get, print, load, store, add, sub, goto, ifpos, ifzero, stop) MUST be indented by at least one space from the left edge, and all memory location labels (e.g., top and bottom in the first exercise) and comments (lines starting with #) MUST NOT BE indented. You can use spaces or tabs for your indenting.

4. Use a text editor to build and edit your programs, then copy and paste them into the Toy simulator to run them. A text editor is a program that works something like a word processor such as Microsoft Word, but without the ability to do special formatting, bolding, underlining, etc. It just stores plain, ordinary text. The free program Visual Studio Code is an excellent choice for this.  Saving your programs to disk regularly is likely to save you time and frustration.

5. Windows users may have trouble if their systems hide the ".txt" extension (last few characters) of text file names. Unfortunately, this is the default behaviour of Windows' File Explorer app, and it may lead to situations in which, for example, a file that looks like it is called "Lab02-2.toy" is actually called "Lab02-2.toy.txt". To make sure this is not a problem for you, do a web search for "windows show file extensions" and follow the directions you find.

6. You CAN edit programs in the Toy simulator to fix minor errors. Unfortunately, the programming language that the simulator was written in (JavaScript) specifically forbids file output for security reasons, so there is no automatic way to save your lovely programs if you have edited them in the Toy. However, you can select a program's text as you usually do (with a mouse, for example), copy it into your clipboard, paste it into an empty file in your text editor, and then save it.

7. NOTE: You will only receive marks in Part 1 if your submitted programs run correctly.

1. (1 mark) Just to make sure you have a handle on how to make the simulator work, type or copy and paste this program into the program code window on the left.

top     get

        ifzero bottom

        print

        goto top

bottom  stop

Try to predict the behaviour of this program. Will it print out a 0 or some other number as its last operation? Execute the program (by clicking on the RUN button). Here is a sequence of input values to try:

6

-2

5

1

0

Of these, which was the last value printed in the output window (to the immediate right of the input window), above "stopped")? 

2. (6 marks) Let's try working with a memory location for storing data. Replace the program code window's content with this:

top     get

        ifzero show

        print

        add sum

        store sum

        goto top

show    load sum

        print

        stop

sum     0

By the name I have given the memory location sum, you might suspect that this program adds up a list of number values, and you would be right. To see that this is the case, run the program and enter the same sequence of input values that you used for part 1, above. When the value of sum is loaded into the accumulator, and then printed, its value should be 10. Let's modify the program so that it not only prints out the sum, but the number (count) of non-zero values that were entered, too. Here is how (and this is where you may want to copy and paste the code into your editor and work on it there!):

a. Start by adding a memory address label called count to the bottom of the program code (i.e., under "sum 0") and give it an initial value of 0.

b. Insert a new instruction (on a new line) after the ‘store sum' instruction to load the value of count into the accumulator. (Hint: the instruction is ‘load count'. Remember that instructions must be indented!)

c. Insert an instruction after that to add 1 to the value in the accumulator. (As I work through this, the instruction I just created is on line 7.)

d. Insert an instruction after that to store the value in the accumulator at the memory location you have labelled count. (This will automatically overwrite whatever happens to be stored there.)

e. Insert an instruction after the final ‘print' that loads the value stored at memory location count into the accumulator.

f. Insert a print instruction after that. (It should be immediately above the ‘stop' instruction.)

If you have done your work properly, you should end up with a program that is 16 lines long (more if you have added any comments – that is entirely optional), and that, when run with the same input data as that used the program in part 1, gives the following output:

6

-2

5

1

10

4

stopped

(where the 10 represents the sum, and the 4 represents the value of count, that is, the number of input values preceding the loop ending 0.)

Test your program on some other input, until you are satisfied that it is working correctly. Save your code into a text file called Lab02-1-2.toy for inclusion in your solution .zip file. Windows users (and maybe others?), if you are using Visual Studio Code, it may try to add a ".txt" extension to what it (correctly) perceives is a text file. You can avoid this by saving the file with quotation marks around its name, like this:

 

Once Visual Studio Code "knows" there is such a thing as a ".TOY" file, it will happily let you save others without trying to add ".txt" to the filename. At least, that's how my VS Code behaves.

3. (6 marks) There is no division instruction in the Toy language, but maybe we can crudely approximate one by doing repeated subtractions to let the Toy calculate an integer average of a list of numbers. To keep things as simple as possible, we will arbitrarily specify that this program need only work for a list of non-zero positive integers, and that (as with the previous two programs) input will stop when a 0 is entered. NOTE: Sometimes this program will work with negative integers in the input, but if the overall sum of the numbers is negative, it will give incorrect results. I'm sure there's a way to program around this problem, but I don't want to make our code overlong, so let's just stick with non-negative input. Start with your Lab02-1-2.toy code and save it as a new file called Lab02-1-3.toy. (Be careful not to overwrite Lab02-1-2.toy.) Make the following additions to the code:

a. Add two new memory address labels at the bottom of the code, avg and rem. Give both initial values of 0.

b. Insert the following code between the final print instruction and the stop instruction. Note that I said ‘between the final print and the stop instructon;' stop should still be the last instruction executed. If you are typing the code in, type carefully to catch any errors.

calcavg load sum

        ifpos cont

        goto showavg

cont    store rem

        sub count

        store sum

        ifpos incavg

        goto calcavg

incavg  load avg

        add 1

        store avg

        goto calcavg

showavg load avg

        print

        load rem

        print

c. Save your work in the text editor frequently, so that if something needs fixing you will not lose what you've done. Include your completed Lab02-1-2.toy program in your .zip file submission.

d. Run the program (at least) three times, using the following input data, noting what values print out for avg and rem in each case. Note that the 0 value at the end of each of these lists signals an end to input and is NOT used in the average calculations.

	Input sequence	Value printed for avg	Value printed for rem
i.	1, 2, 3, 4, 5, 0
ii.	6, 8, 4, 2, 1, 7, 0
iii.	12, 13, 14, 3, 0

Hint: The last two numbers printed out are the values of avg and rem. avg is, of course, my abbreviation for average and rem is short for remainder. It will, of course, always be 0 if the sum divided by the count is an integer. Check using a calculator app or by doing the arithmetic in your head that you are getting the correct results.

4. (3 marks) You are on your own for this problem. Save a copy of Lab02-1-3.toy as Lab02-1-4.toy (again taking care not to overwrite Lab02-1-3.toy). Alter the program so that it can include 0 values in the sum and ends input, instead, after the user enters a negative number. For example, if the user enters 1, 2, 4, 0, 3, 8, -1, the output should be:

 

Note that if your revised program is much longer than the original, you are probably trying too hard. To make sure your finished program is working correctly for more than just the input suggested above, test it using other lists of numbers to make sure it gives consistent results.

Save your Lab02-1-4.toy program and include it in your .zip file submission.

Part 2

1. (8 marks) In the module 4 (Algorithms) slides, you saw the exchange sort algorithm and how it was used to sort a collection of books by the surnames of their authors. The time complexity of that algorithm, as measured by the number of comparisons it makes in its inner loop, is given as

 

where n is the number of books (i.e., the number of items to sort). Thus, to sort 10 books, exchange sort makes

  

comparisons.

A naïve person, such as one who had not looked at the slides for this module, might suspect that the job of sorting 20 books would require twice as many comparisons as are needed for 10 books, and would therefore take about twice as much time, but this is not the case.

Assume you can compare the authors of two books and swap (exchange) their positions if needed at an average rate of one operation per second. Calculate the number of comparisons that would be required and the time, in minutes and seconds, that it would take to sort book collections of the sizes given in the table below.

If you've done your work correctly, the time entered for 20 books should be significantly more than double the time shown for 10 books.

Now, let's say a computer that can make 1000000 (one million) comparison-and-swap operations per second, on average, is using exchange sort to sort 1000000 (one million) items of data. How many days, hours, minutes, and seconds will the computer require to do that? Express your answer in "d hh:mm:ss" form, as in "2 13:04:18" for 2 days, 13 hours, 4 minutes, and 18 seconds.

2. (8 marks) Quicksort can, in the worst circumstances (owing to unwise choices of pivot values), perform as poorly for large collections of data as exchange sort. It usually doesn't however, and is frequently described as having an average complexity that is proportional to

n log₂(n)

(That's n times the log₂ of n.) log₂ is described in this week's notes on binary search, as binary search has a time complexity proportional to log₂(n). Scientific calculators frequently have a way of calculating log₂ of a number, and so does Microsoft Excel. I encourage you to use Excel or some compatible spreadsheet program (Google Sheets, perhaps) to help you with calculating these logarithms for this problem. For practice, open a new workbook in Excel, put the number 128 into cell A1 and this formula, exactly as shown, into cell B1:

=log(a1,2)

then press Enter. You should have caused a 7 to appear in place of the formula in cell B1. 7 is the log₂ of 128, which is usually written log₂(128), and 7 is also (not coincidentally) the number of zeroes in the binary for 128:

10000000

Let's repeat the exercise from the previous page, but this time using quicksort instead of exchange sort. For this first part, it will still be you sorting books, and you are still capable of one compare-and-swap operation per second on average, but now you'll be using n log₂(n), and rounding up to the nearest integer, instead of (n² – n)/2 for your middle column calculations. Again, I've done the first one for you.

Returning to our computer that can make 1000000 (one million) comparison-and-swap operations per second, on average. It is now using quicksort to sort 1000000 (one million) items of data. How many days, hours, minutes, and seconds (d hh:mm:ss) will the computer require to do that?