Assignment 01

Due: Thursday, August 29, 2019 at noon 50 pts.

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 an editor (I like jpico) that your lab instructor has shown you in your CS 1580 lab #1( or #0 depending on who your lab instructor is). First though, make a new directory inside your SDRIVE directory and call it cs1570 (from home, change directory to SDRIVE. Then type mkdir cs1570 and enter). Change into that directory (cd cs1570). Now, make a new directory under this cs1570 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 63 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. Note: You are to assume that you are living in 1999 when there was NO text messaging and NO conference calling, i.e. you can only make one call to one recipient at a time and each call takes exactly 2 minutes.

    2. You have a bag of coins: 500 quarters, 3 dimes, and 3 pennies. Given a monetary value, you want to provide the least number of coins that make that value. Write an algorithm that outputs whether it is possible and what the coin combination is.

    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.

To submit this homework, you are going to use the cssubmit program for your section of cs1570. This assignment will be used for all sections. Your answers should be written up using your favorite editor in a subdirectory called hw1 hanging off your cs1570 subdirectory. Remember: make a different directory under cs1570 for every one of your assignments. From that directory, at the UNIX command, type "cssubmit 1570 a 1" if you are in section a. If you are in section b, type "cssubmit 1570 b 1". If you are in section c, type "cssubmit 1570 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 1570 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. You can look here for guidance on submitting using the cssubmit command.

NOTE: For 400 yrs, the sections of classes at this university were lettered. Thus, there was cs1570 section A or section B or ... Because of new software used by the regestrar's office, the sections are now numbered. Price's section is 101, Brown's sections are 102 and 103, Cole's sections are 105 and 106. Because I don't want to change the directory names for cssubmit from letters to numbers, let's use this plan. Those of you in section 101, pretend that your section is A (or a...either upper or lower case works), 102 will map to B, 103 will map to C, 105 and 106 map to D and E, respectively.

SECOND 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.