Assignment 1

Part I: Short Answer Questions

This part of the assignment is a crude and blatant attempt to check that you have read over the course information materials, but I hope that writing the answers down will help you to remember some key points from the material in this module. I am not looking for creativity in the answers: feel free to cut and paste from the course notes. In fact, you could think of it as a scavenger hunt for answers in the notes.

How much are the assignments in the course worth?
You have to have finished the course by what date?
You have just over 12 weeks to finish the course so about how many hours a week should you set aside for working on it?
How many modules are there in the course?
According to Brian Kernighan (and your trusty instructor) how is good programming learned? (Be complete.)
Why was Python chosen for this course?
Which of the examinable topics means the least to you right now?
What should computer science really be called?
What are our two key computational resources?
What does the "envelope of algorithm performance" refer to?
What is a computer program?
What is an algorithm?
List the key operations imperative programming relies on.
What are the four functional components of a computer?
How many keywords are there in Python?
Why is the Structured Program Theorem important?

Part II: Using the Python Shell

Use the Python shell to:

Display the value of 2¹⁰⁰.
Calculate the volume of a sphere of radius 2.0 metres. (The formula for the volume of a sphere is 4πr³/3.)
Display the square root of 2.

Run the following code:

>>> if 10**20 > 20**10:
        print '10**20 wins!'
else:
        print '20**10 wins!'

Run the following code:

>>> n = 1000000
>>> size = 0
>>> while n > 1:
        n = n / 2
        size = size + 1
>>> print '1000000 is approximately 2**', size

Run the following code:

>>> for c in 'Tim':
        print c

Part III: Writing Algorithms

To get some practice specifying algorithms write instructions to enable someone to recreate each of the sugar cube structures pictured below. (N.B. To mark this question I will try and follow your instructions precisely and see how closely the result matches the goal. You might want to give the instructions to a friend and see what they construct before submitting them to me.)

(i) (ii)
(iii) (iv)
(v)

Logistics for Parts I to III

Prepare a text file containing,

your answers to the questions form Part I,
the transcript of your Python shell session (including the output!) from Part II, and
your five sets of instructions from Part III.

Send the file to me either,

by attaching it to an email message to me,

or,

by using MyYC's assignment submission feature: Under Student Tools click My Assignments then select Assignment 1 from the list and then look for this button:

Part IV: Trading off Processors and Memory

In Big Picture 1: Computer Science you read that algorithms are ranked according to how much space and time (or memory and processing) they use with the goal being to use as little of each as possible. The flipside is that most problems can be solved more quickly the more of each of those resources you have available. We'll demonstrate this in the following exercise (and we'll share our data to confirm it across trials, and perhaps get our competitive juices going). We're going to compare the time it takes to complete some processing depending on how many processors and how much memory we have.

Get a deck of cards and a stopwatch (if not an actual stopwatch, any watch where you can measure time in seconds).
Shuffle the deck of cards.
Time how long it takes you to sort the cards into order* using your hands and a table top (i.e. you can spread the cards out or stack them anyway you want on the table top).
Get three friends and shuffle the deck and time how long it takes the four of you to sort the cards using the tabletop. Give some thought to how you should organize your efforts. (How you do this represents your algorithm.) You might want to do multiple timings here because you will probably be faster the second and third times than the first. After a couple of attempts the rate of your improvement will probably decrease (and you'll be getting bored).
Before your friends flee, shuffle the deck and then time yourselves sorting the cards again but without using the table top, i.e. all the cards have to be held in your eight hands at all times (no placing cards on your kness, head or anywhere else, or holding any in your mouth etc. Although the desire to do these things shows you just how valuable a little more memory can be.).
Now that your friends have left, shuffle the deck and time yourself sorting the deck one last time but this time using only your two hands, i.e. no table top! (Or knees etc.)

Logistics

Post your timing results in the MyYC discussion forum in the following format:

Time:Processors:Memory

where the time should be measured in seconds, the number of processors is the number of hands (either 2 or 8) and the memory is either large (the tabletop) or small (just the built-in memory of the processors) e.g. If it takes you 2 minutes and ten seconds to sort the deck working alone but using the tabletop you would record

130:2:large

One record per line please.

I'll compile all the results once they're available and prepare a graphical summary.

* We'll use Bridge order where the order of the suits will be Clubs-Diamonds-Hearts-Spades and the cards within each suit will be ordered from Ace to King.