Assignment 01

Due: Thursday, Jan. 25, 2018 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. You want to buy a Snickers candy bar from the vending machine outside room 216 in the Computer Science Building using money (not any other form of payment). Give a detailed algorithm for how you would accomplish this task. Be sure to take into account the (reasonable) possibilities, such as an empty wallet or having only hundred dollar bills on you or having exact change or ... You can skip the less likely situations such as there being an alligator in your purse or an angry resident gorilla in the vending machine or the vending machine turns into a black hole making you its first victim.

  2. Assume that a maze is represented by an 8x8 grid where each cell is black or white. You can move to a white cell, but you cannot move to a black cell (e.g., a black cell is a wall and you cannot walk through walls!). Assume that you start off positioned in the

  1. upper leftmost available white cell. Your goal is to reach the lower rightmost white cell. An example is shown below where the starting position is designated with S and the goal position is designated with a G. Give a detailed algorithm for how you would accomplish this task. Your algorithm should work for an arbitrary 8x8 grid, not just the grid shown below.As in the popular "word search" puzzles, suppose that you’re given a 19x18 grid of characters similar to the one shown below and a list of words. Give a detailed algorithm for how you would find all of those words in such grid. A word can appear (backwards or forwards) horizontally, vertically, or diagonally in the grid. As an example, we’ve circled the word “AIREDALE” in the grid below.

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