Assignment 01

Due: Thursday, Jan. 20, 2011 at noon 500 points.

For this assignment, you will type and submit three (3) algorithms. Make your algorithms clear and concise step-by-step procedures that solve the problems given. I think that each of these should require at least three steps and probably (though, possibly) no more than twenty steps. Think about your answers.

You are to edit a single file in your DFS account using one of the editors that your lab instructor has shown you in your CS 54 lab #1. First though, make a new directory under your home directory and call it cs53 (from home, typemkdir cs53 and enter). Change into that directory (cd cs53). Now, make a new directory under this cs53 directory and name it hw1. Change into that directory and then create the file with your answers in it, naming it something clever like "hw1.txt". The .txt extension is used for files that are nothing but text (not to be compiled). What ever you name that file, make sure it has a .txt extension. This assignment is NOT C++ programming. You are not to compile this. In this (one and only) file (for this assignment), you are to number your answers for the following 3 problems. Also, be sure to put your name and section letter at the top!!

  1. There is a class of 50 students. The teacher and each student owns and keeps in his/her pocket a working cell phone. Each of these cell phones has a log of the phone number of everyother student. Email is down. The teacher will cancel class and needs to let the class know as fast as possible since the class starts in 15 minutes. Clearly, the teacher can't call all the students himself; there isn't enough time. Write an algorithm for the teacher to follow to expedite informing all students in the class that it is cancelled.

  2. Blahville has a maddening downtown area: all of the (many) streets oriented north-south are alternating one-way streets, and all of the (many) streets oriented east-west are also alternating one-way and intersecting the north-south streets. You find yourself as a passenger in a car with a nervous driver who is unfamiliar with that area. You have to guide them by telling them what to do at every intersection they come to. You are in the middle of a block, but your goal is to reach the apothecary which is exactly one block behind you.

    1. Write an algorithm that you can use to tell the driver what turns to make at each intersection and how far to go to reach your goal.

    2. Do the same with the restriction that at least one right turn and at least one left turn has to be made before reaching the goal (because... um ... it's a Swiss Cheese Mobile you're driving).

  3. So you bought a time machine and fell through time several hundred years. Now you're making your way through life as the "Weights and Measures Minister". You carry in your pockets a set of weights and on your head abalance (since there's no room in your pockets). You live in a community of potto ranchers, and they quite often need to weigh their pottos. When someone needs your services, it is that they want you to verify the weight of the potto they have. You have in your pockets:

    • 5 1-pound wts.

    • 1 1-clove wt.

    • 2 1-stone wts.

    1. So, you put the potto on one side of the scale and an appropriate subset of your weights on the other side of the scale. Write an algorithm to determine whether or not you can verify the weight, in pounds,that a person claims their potto weighs, and which of your weights are required to do the job. Thus, if Bob says "my Potto weighs X lbs", your algorithm should be able to tell you if you can weigh something weighing X lbs. Suggestion: start by finding out what a clove and stone are.(try Google.)

    2. Note: Don't be concerned about the effect those weights have on your trousers. Sagging pants will soon be in style.

To submit this homework, you are going to use the cssubmit program for your section of cs 53. This assignment will be used for all sections. Your answers should be written up using your favorite editer in a subdirectory called hw1 hanging off your cs53 subdirectory. Remember: make a different directory under cs53 for every one of your assignments. From that directory, at the UNIX command, type "cssubmit 53 a 1" if you are in section a. If you are in section b, type "cssubmit 53 b 1". If you are in section c, type "cssubmit 53 c 1", etc. (Can you see the pattern?) Hit enter. Of course, when submitting homework #2, your last entry in that command should be a 2. Don't type cssubmit 53 a h2 or some other variant like that; just the digit 2. Use this scheme for subsequent submissions. If you have any questions about using the editor or submitting, just ask.

NOTE: You can submit the same assignments multiple times. If you submit and then remember something you forgot, you can edit your file, save it, then submit again. The new submission will overwrite the old; we won't see the old one. Time stamps on submissions apply to the latest submission. Always run the submit script from the directory in which the file(s) to be submitted reside(s). Any questions, just ask. Remember, there is a due date/time. Try not to exceed that. If you do, it'll cost you.