Assignment 01

Due: Wednesday, Sept 2, 2015 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 under your home directory and call it cs1570 (from home, 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 are given a sequence of characters and must check that it conforms to the rules for a valid password: contains at least one non-alphabetic character, contains at least one digit, contains at least one uppercase alphabetic character, and is at least 8 characters long. How do you determine if the password is valid? Write an algorithm.

  2. You have to go to your neighbor's house to let their 180 lb. Great Dane out to go to the bathroom, give him fresh water, and give him a doggy treat. (Seeing as the dog loses 5 lbs during the process, you'd better do it right.) Constraints to consider for this issue/problem:

    • the mailman is present between 2:00 and 2:10.

    • the lawn keeper hired will be around between 10:00 and noon.

    • the dog becomes "socially unstable" (biting, gnawing, clawing, etc) while strangers are around.

    • a doggy treat will instantly curb non-social behavior for about 10 seconds.

    • It takes 10 seconds to chain the dog to a tree, if that happens to be a necessary exercise.

    • the owner left you 4 doggy treats.

    • you own a working wrist watch.

    • the dog will go anywhere you toss a treat.

Write an algorithm for taking care of the dog.

3. Do one of the following:

    • You and I need to communicate via the US Postal Service. What you want to communicate is secret, so you don't want someone who finds a package on your doorstep or in your mailbox to be able to open it and read what's inside.

      • We each have access to an arbitrary number of indestructible boxes, and an arbitrary number of indestructible key locks. Each box can have as many locks put on it as you want. Unfortunately, each lock has only one key, each key only one lock, and only the person who possesses the lock has the key. We can send things to each other in locked boxes, but, of course, the recipient doesn't have the key to the lock because the sender still has it. Sending the key unsecured will get it stolen or, worse, copied. We also have no way to meet each other in person to exchange keys securely.

      • Write an algorithm that specifies how we can arrange, with these resources, to exchange messages securely with each other.

  • Assume the following: all the lowercase letters have numeric values 97 through 122, i.e. a=97, b=98, ... , z=122; all the uppercase letters have numeric values 65 through 90, i.e. A=65, ... , Z=90; a special character called the "null character", Ø, has value 0. A word is a contiguous string of non-null letters followed by the null character,Ø. Words are read left to right. Define the lexicographic difference of two words, W1 and W2, to be zero if W1 is identical to W2, otherwise it is the absolute value of the numeric difference of the two letters of W1 and W2 where they first disagree. Examples: W1 is aligator and W2 is alignment so Lex-dif is 13 since n(110) - a(97) = 13. W1 = Align and W2 = align so Lex-dif is 32 since a(97) - A(65) = 32. W1 is bob and W2 is bob so Lex-Dif = 0 since they are identical. W1 is Frank and W2 is Frankenstein so Lex-dif is 101 since e(101) - Ø(0) = 101.

    • Write an algorithm to compute the lexicographic difference of two words.

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