Assignment 01

Due: Thursday, Sept. 1, 2011 at 8:00 a.m. 50 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. Write an algorithm to implement modulo division. You may assume only positive values. So, you say "what the heck is modulo division?" Here are some examples:

   1. 5 mod 2 is 1 7 mod 6 is 1 7 mod 5 is 2 3 mod 3 is 0

   2. See the pattern? I didn't think so. Here's a definition: For integers (positive) a and b, a mod b is the remainder after integer division of a by b. So, in the above examples, 2 goes into 5 twice with a remainder of 1, 6 goes into 7 with a remainder of 1, 5 goes into 7 with a remainder of 2, etc.

2. Life has been good to you so far. Now you have a job, and, you're thinking, life is even better now that you have a paycheck! However, your job has been trying, and a little bit boring. So, you'd like to take up some time developing an algorithm to make the job even easier than it already is. Here's you job: You are the Measure Minister. People in your town, being too stupid to use a yardstick , bring to you all their stuff to measure. Everything is measured in exact inches. (The foregoing fact makes this problem simple, albeit not realistic. Thus, for this problem, you can assume no one will ever bring you anything measuring 3.5 inches, or 78.23 inches, or 9.01 inches, or ...) Your only tool-o-measurement is a piece of string exactly 8 inches long. Write an algorithm that you (or your replacement) may use to measure in the most efficient way all the stuff that the townspeople might bring to you to measure. Remember, they can bring you little things or big things.....or even really big things!

3. Do one of the following:

• • Roger is a one-tentacled octopus (he had an unfortunate accident with a motorboat). He usually spends his days making his way through the maze of coral on the ocean floor looking for food. But today he is particularly interested in finding his way to the other side of the maze because there is a very good octopus doctor specializing in prostheses ( artificial limbs) there. He knows that the doc can fix him up with pieces of garden hose so he won't have to spend the rest of his life as a unipus in a sea of octipi. So, to help out Roger, write an algorithm that will get him through the maze and to the doctor's office. You can assume that the coral maze is two dimensional in nature; that Roger can't float up over the coral, thus skipping over the maze; that Roger can sense, with his one tentacle, any blockage in his path or not; Roger can also sense when he has reached Dr. Frank's Prostheses and Garden Shop (the doctor's office); Roger, being a damaged octopus, leaves a drop of ink at every "step" on his way; Roger can count drops of ink.

    • I think it might be helpful here to assume that the path of the maze is comprised of unit squares corresponding to each "step" that Roger takes. Also, the drops of ink he leaves will not overlap; thus he can count the number of times he has passed that particular square.

  • Roger Bob is a one-tentacled octopus peg-legged pirate (he had an unfortunate accident with a motorboat another pirate). He usually spends his days making his way through the maze of coral on the ocean floor looking for food rich people's houses stealing stuff. But today he is particularly interested in finding his way to the other side of the a maze because there is a very good octopus doctor specializing in prostheses (artificial limbs) there, just because. He knows that the doc can fix him up with pieces of garden hose so he won't have to spend the rest of his life as a unipus in a sea of octipi there's a chest of treasures at the end. So, to help out RogerBob, write an algorithm that will get him through the maze and to the doctor's office treasure chest. You can assume that the coral maze is two dimensional in nature; that Roger Bob can't float jump up over the coral maze, thus skipping over the maze; that Roger Bob can sense see, with his one tentacle eyes, any blockage in his path or not; Roger Bob can also sense when he has reached Dr. Frank's Prostheses and Garden Shop (the doctor's office) the treasure;Roger Bob, being having a damaged octopus peg leg, leaves a drop of ink hole in the sand at every "step" on his way; Roger Bob can count drops of ink holes in the sand.

    • I think it might be helpful here to assume that the path of the maze is comprised of unit squares corresponding to each "step" that Roger Bob takes. Also, the drops of ink holes he leaves will not overlap; thus he can count the number of times he has passed that particular square.

  • Write an algorithm that will successfully get some one through a 2-D maze.

    • Algorithmize demazification.

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.