Laboratory work for Tuesday 11/4 and Thursday 11/6:
Start the multimedia with Start>Run uc, and select Networks. As you go through the multimedia, answer the following questions. Discuss your answers with your TA before you leave (it's OK to ask about anything you don't quite understand from the multimedia), and include them as part of your homework assignment:

1. What are some resources (name at least three) that servers provide clients via a network?
2. Given what you learned about Ethernet bus networks, why is Lehigh replacing the current 100-megabit Ethernet with a 1-gigabit Ethernet network in Packard Lab?
3. What does a Domain Name Service (DNS) do?
4. What are packets on the Internet? Describe the kind of information that at least one or two different layers of the OSI network model add to each packet.
5. What is encryption? Why is the Data Encryption Standard more secure than the Caesar cipher algorithm?
6. What's the difference between a virus and a worm?
7. What is a router? Why might one might to have a router in one's home?

Laboratory work for Tuesday 11/11 and Thursday 11/13:
Start the multimedia with Start>Run umcpp, and select Arrays. As you go through the multimedia, answer the following questions. Discuss your answers with your TA before you leave (it's OK to ask about anything you don't quite understand from the multimedia), and include them as part of your homework assignment:

1. What are the two data members of an Lstring and what is the purpose of each?
2. On the screen with the drag anddrop exercise for Lstrings, what are the values of vixen[4] and vixen[6]?
3. Given int v=4, what is the value of vixen[sqrt(4)]?
4. After vixen[v*3] = vixen[0], how has the Lstring vixen changed?
5. For the two multiple-choice exercises about the message, ERROR: "String access out of bounds in myfiles.cc, line 3", what are the correct answers, and why?
6. When prompted, write the function upto(). (LOOKOUT will load function a program with reverse(), which you may or may not want to use as a starting point.) Note: this is the same as exercise 15.11 given below (just submit it once of course).
7. Near the end of the section on Sorting there are two multiple choice questions. What is the right answer for the first one, and why?
8 . At the end of the BinarySearch section, Knobby asks, "How many interations does it take for BinarySearch() to find the value 20?" What did you enter? What is the right answer? How does its performance compare with LinearSearch() for the same value?

Homework exercises:
In addition to the above questions from your lab work you will continue working (in pairs) on the Game of Life:
1) Review and revise your Requirements specification, Use cases and UML class diagram, per comments from the TA (If you and the TA think any of these documents need no revision, write a note to the TA to this effect.)
2) Write pseudocode for the complete Game of Life program (following your use cases and UML class diagram).
3) Implement a function that initializes a Game of Life configuration randomly. Hint: you can use the LOOKOUT library's StringArray class to represent the game configuration.

Also do the following exercises in The Universal Computer:

Exercise 6.28: What is a protocol? Name three or four protocols and explain what they contribute to computer networking.

Exercise 6.34: Why would it be a bad idea to give Internet browsers write access to files?

Exercise 6.37: A Caesar cipher produces a cipher text "DKTVJFCA". What is the plain text? How does this exercise affect your confidence in this encryption scheme?

Exercise 15.5: What loop pattern does the above while loop have? Why would such a loop pattern occur commonly in connection with indexable objects such as Lstrings?

Exercise 15.6: What happens when a program attempts to execute the following code fragment?

int i=0;
while (i <= myName.length())
//boundary loop invariant: 0 <= n <= myName.length()
{ if (myName[i] == ' ') myName[i] = '*';
i=i+1; //variant: incrementing i by 1
}
(Hint: this is an example of an “off by one” error.) Correct the code (and the invariant comment).

Exercise 15.9: Function reverse() creates a local variable by invoking a constructor with a parameter in.length(). Why? What would happen if this were simply Lstring out? (If you’re not sure, try it, and then explain what happens.)

Exercise 15.11: Write a function, called upto(), that returns an Lstring containing all the characters up to a specified delimiter character (e.g., ' ') in another Lstring. For example, if myName contains "Glenn Blank" then upto(myName,' ') returns "Glenn".
(This is an exercise you can do while going through the multimedia, as noted above.)

Exercise 15.16: Write two functions that implement the Caesar cipher algorithm, described in the section on computer security in chapter 6 (pp. 163-4). Given a clear text Lstring and a replacement letter displacement number j, the cipher function produces a cipher text Lstring. Given a cipher text Lstring and j, a decipher function produces the original clear text. Extra credit: Write a generalized decipher function where given just a cipher text Lstring, all possible clear text Lstrings (for all possible values of j) are displayed—leaving it up to the user to decide which one is most likely.

Exercise 15.43: Modify the above code fragment to find all instances of lower case vowels.

Exercise 7.3: Suppose the size of A is 100 and we initialize the first five elements as we did above. (A[0]=9, A[1]=4, A[2]=5, A[3]=6, A[4]=8.) Under what circumstance would the revised algorithm be more efficient? Under what circumstance would its performance be the same?

Exercise 7.16: If there are 10 elements in sortArray, how many times will line 6 be executed? How many times will line 8 be executed? How many times will line 11 be executed? How many times will line 14 be executed? If there are 100 elements, how many times will line 11 be executed?

Exercise 7.20: What does the computation of line 5 accomplish? How does it rely on the behavior of integer division? Give an example.

Exercise 7.23: Modify the pseudocode for BinarySearch so that instead of NOTFOUND it returns a value indicating where one might want to insert the key value that was not found in the array. Then modify and test program BiSearch.cc (in Y:\lib\gcc\lookout\ch12Outside) to make sure your algorithm works.

Exercise 7.43: Why does repeatedly dividing the array in half require roughly log2(N) comparisons to ensure that a key is not in the array? Hint: Any N which is a power of 2 is equal to the product 2*2*..*2 (where there are log2(N) factors).

Exercise 7.44: Under what conditions should we sort an array before searching it?

Exercise 7.58: For example, suppose one algorithm’s measure is 6N and a second algorithm’s measure is 2N2. Compute the two values for powers of 10 up to 1,000,000. Compare the size of the two numbers with the size of their difference. What happens, and what is its significance?

Exercise 7.62: If chess-playing is an exponential problem, and people are relatively slow to consider the consequences of possible moves, why are some people good chess players? Why only recently did a special-purpose supercomputer defeat the world champion?

Extra credit:

Exercise 6.40 (explore): What is the Secure Sockets Layer (SSL) and what does it do? Does it increase your confidence that web-based transactions can protect your private information?

Exercise 15.55: Using C strings and arrays instead of Lookout classes, create the table WordList shown in figure 15.13, then display it.

Exercise 15.63: Using templates, design and implement a generic version of the BinarySearch algorithm, shown in figure 15.12. Show that it works with at least two different element types.

Exercise 7.56 (explore): On the web, find yet another sort algorithm and describe how it works.

Due: Monday, 11/17, anytime before midnight.

Hand in: When you're ready to submit your assignment, combine the answers to all the exercises into one text file. Then, attach your file to assignment #6 (where you got this assignment) in Blackboard.

Prof. Blank