 All HomeworkHomework 1

Answer the following questions based on the course website.
For each one, specify which link on the left you clicked to get
the information.
For instance, your answer for one might be:
e. Certainly (Gradebook)
Each question is worth 1/2 point. (10 points)
 How many assignments can you turn in late? What is the penalty?
 What percentage of your grade are exams? What percent is each exam?
 When are my office hours?
 If you can't come to my office hours, what is the best way to find a time to meet with me?
 Is one of the topics of coverage for the course Networks?
 Can you tell exactly what grade you got on any assignment in the
course at any time?
 What grade will you get if your final percentage in the course is 86?
 What is due on Wednesday, September 7, and at exactly what time(s)?
 Will I give extra credit assignments to students who are not performing
well in the course?
 How many of the Questions & Answers do you need to complete for each section? Do you turn them in?
 Can you listen to your iPod or send a text message when you are in the classroom?
 What percentage of your final grade is the third paper worth?
 How many papers will you submit to me this semester?
 How many problems are on Homework 9?
 If you need help during the evening hours, are there any options?
 How many points is Homework 12 worth? What about Homework 14?
Which one of these counts more toward your final grade?
 When is the Midterm exam?
 Can you take the Midterm on a day other than what is specified?
 Is reading the textbook optional? Explain.
 Can homework be hand written?

What is computer science? (20 points)
The purpose of this assignment is to try to give you a good start to
understanding what computer science is by asking you to give a clear
definition of what it is based on what those in the field think it is.
The audience you are writing for is the general public—that is,
assume the reader has no knowledge of computer science or any of the
terminology.
Give a clear and complete definition of computer science,
making sure to define any terms you use (information, computation,
computing system, etc.). You should find, modify, or create a definition
that makes perfect sense to you. In other words, do not just use the
"dictionary" definition if it does not make sense to you. Either modify
it so it makes more sense, further clarify it so it makes sense, or
look for other definitions.
A good format for your answer would be a one sentence definition
followed by one or more paragraphs further clarifying your definition.
If you use this format, you may quote your one sentence definition from
one of your sources if you find a definition you think is clear and
complete.
Make sure you include your definition as a quote so it is
clear that it is not your definition, and cite the source.
Then provide
a clarification of the definition by defining any vague terms and
giving further explanation as needed.
Use your textbook, Wikipedia (If it's on Wikipedia, it has to be true!),
Google, a dictionary, the library, and any other source of information
you can think of to find the best definition you can.
In fact, it might be helpful to get
definitions from multiple sources and merge them into one definition.
Your answer should be no longer than one page (and no shorter than half a
page), and must be typeset. (That is, it may not be hand written.)
You should have at least three different sources (the textbook counts),
and make sure to cite all of your sources!
Follow the guidelines given on the Project page for citing and listing references.
Grades will be based on the
Paper Grading
Criteria 2.0.
Homework 2Do the following exercises from pages 6768 of your textbook.
Problem  Points


2  4
 6  4
 7  5
 9  3 
Homework 3Do the following exercises from pages 6869 of your textbook.
Problem  Points  Notes


10  4
 13  4  Show an appropriate calculation for each case and then interpret the result of your calculation.
 15  4
 17  3
 18  3 
Homework 4Do the following exercises from page 69 of your textbook and the ones listed below.
Problem  Points  Notes


20  4  To clarify, the problem gives hexadecimal numbers that encode an ASCII message. So you need to convert from hexadecimal to ASCII. The answer to this is an English word so if you get nonsense you did not do it correctly.
 23  4 
 24  4 
 #1 below  6 

 Consider the bitstring 01101101.
 Give as many interpretations of this bit string as you can think of. (Give at least 4 specific interpretations for full credit.)
 What does the bitstring mean?
Homework 5Do the following exercises from pages 6970 of your textbook and
the other ones listed below.
Problem  Points


32abcd  8
 #1 below  8
 #2 below  8

 Show all of your calculations for the following, even if you can do them in your head.
For each, give a brief description of your calculations so that someone reading your solution
understands what you are doing.
 Convert the binary number 100110 to decimal.
 Convert the sixbit two's complement number 100110 to decimal.
 Convert the binary number 010111 to decimal.
 Convert the sixbit two's complement number 010111 to decimal.
 Show all of your calculations for the following, even if you can do them in your head.
For each, give a brief description of your calculations so that someone reading your solution
understands what you are doing.
 Convert the decimal number 13 to binary.
 Convert the decimal number 13 to sixbit two's complement.
 Convert the decimal number 23 to sixbit two's complement.
 Can you convert the decimal number 23 to binary? Why or why not?
Homework 6Do the following exercises from pages 7071 of your textbook. As always, clearly show your work for each problem.
Problem  Points


37 cde  6
 39  4
 44  6
 #1 below  4

 What is the importance of the other three problems on this assignment? In other words, what concept(s) are they trying to teach you about?
Homework 7Do the following exercises from page 108 of your textbook (102 in full book).
Problem  Points


4  3
 7  10
 8  4
 9  10 
Homework 8Do the following exercises from pages 109113 of your textbook (103107 in full book).
Problem  Points  Comments


14  6
 18  4  Make sure you explain your answer.
 19  4  Give a clear justification based on your solution to 18.
 21  4
 23b  4
 28  2  First write out what each instruction does. Then read your "pseudocode" version to figure it out. Your solution will describe what the program does overall, not just what each instruction does. (e.g. "Bake a cake" versus "put eggs and flour in a bowl, ...")
 34aei  6
 39bc  4
 25  2  See note below
 Problem 1 below  4  See note below


Write a program in the machine language described in the Appendix of our textbook that places FF in all memory cells from address A0 through C0.
Your program should be in memory cells 00 through 13 (and no more).
Note: All numbers in this problem given in Hexadecimal.
Note:
You can choose to do either 25 or problem 1, but not both. Notice that 25 is only worth 2 points, so if you attempt that one your maximum homework score will be 36/38. If you do #25, you can include it with your written assignment.
If you do Problem 1, write and test your program in BMach. Use version 1.4 (the older versions have a bug).
Put enough comments in your code to indicate that you understand what your code is doing. Save your program in BMach and call it Problem1.txt. Email me your textfile.Homework 9Do the following exercises from pages 112113 of your textbook (106107 in full book) and the ones listed below.
Problem  Points  Comments


43  4
 48  3
 50  3  In other words, give an algorithm/procedure that accomplishes what is asked.
 #1 below  6
 #2 below  6
 #3 below  4
 #4 below  2
 #5 below  4
 Note: For problems 14, do not worry about potential problems that jump instructions might cause.
 If a program written in our machine language
consists of 15 instructions,
 How many steps are required to execute the program if it is
executed normally?
 How many steps are required if pipelining is used?
 How much faster is pipelining than normal execution for this program? (Give your answer in the form "x times faster", where x is a number. Hint: You need to divide one number by another number to get the answer.)
 If a program written in our machine language
consists of 100 instructions,
 How many steps are required to execute the program if it is
executed normally?
 How many steps are required if pipelining is used?
 How much faster is pipelining than normal execution for this program?
 Generalize the previous results: If a program written in our machine language consists of n instructions,
 Give a formula for the number of steps required to execute the program normally.
 Give a formula for the number of steps required if pipelining is used.
 Give a formula for how much faster pipelining is than normal execution.
 We define speedup to be the theoretical upper limit on how much faster pipelining is than normal execution. What is the speedup in this case? (Hint: What happens when n is really large?)
 Let's generalize one more time: Assume a machine has a machine cycle with 7 steps instead of 3 and that the steps can be overlapped in much the same way as we discussed with our machine (that is, we can start a new instruction at each step of the machine cycle). What would the speedup be? Make sure to justify your answer.
 It turns out that for various reasons, including the presence of jump instructions, one rarely attains the theoretical speedups you calculated in the previous questions. Why do jump instructions slow things down? It might help to run through one of the examples in the book that has jumps using pipelining to see what the problem is.
Homework 10Do the following exercises from pages 143144 of your textbook (133134 in full book) and the one listed below.
Problems  Points


14  4
 23  4  "how much" means a percentage.
 25  4  Think about what happens in both possibilities. Clearly explain your answer.
 27  4
 Problem 1 below  4

 What is the difference between multitasking and
multiprocessing? Be specific, but brief.
Homework 11Do the following exercises from pages 144145 of your textbook (134135 in the full book) and the ones listed below.
Problem  Points  Comments


33  4  Answer both parts.
 41  4  Answer both parts.
 42  4  Make sure you understand the exact definitions of the two terms. Also, try to exhaust all possible causes of each.
 43  4
 47  4  Give your answer using reasonable units (e.g. days or years if it is really large).
 Problem 1 below  4
 Problem 2 below  4


A computer system has a cache with access rate of 1 ns (1 x 10^{9} seconds),
and RAM with access rate of 50 ns (50 x 10^{9} seconds).
Assume that a requested item is in the cache 95% of the time.
What is the average access time for an item on this system?

A computer system has a cache with access rate of 1 ns (1 x 10^{9} seconds),
RAM with access rate of 50 ns (50 x 10^{9} seconds), and virtual memory on the
hard drive with access rate of 9 ms (9 x 10^{3} seconds).
Assume that a requested item is in the cache 95% of the time, and is in the
RAM 99% of the time. What is the average access time for an item on this system?
Homework 12Do the following exercises from pages 194195 of your textbook (182183 in full book) and the ones listed below.
PROBLEM  Points  Comments


13  4  Give specific numerical evidence for your answer.
 14  6 
 16  4  This problem involves two conversions. Show both.
 1 below  6 
 2 below  4 
 3 below  2 


 What is the difference between a bridge and a repeater?
 What is the difference between a bridge and a switch?
 What is the difference between a switch and a router?
 The backbone of the Internet has a lot of built in redundancy.
That is, there are generally many ways to route information from one
machine to another.
 Why is this a good thing?
 Give one problem that arises because of this.

In the CSMA/CD protocol, if a machine detects a collision, it waits
a random amount of time before trying to transmit again.
Explain why it does this rather than immediately trying again or using a fixed wait time.
Homework 13Do the following exercises from pages 194195 of your textbook (182183 in full book) and the ones listed below.
Problem  Points  Comments


27  5 
 34  4  The problem gives a single URL. It is too long so it is displayed on two lines.
 1 below  4  Show all of the relevant calculations.
 2 below  4  This is not asking about network layers.
 3 below  3  Show your calculations for all three IP addresses, and explain your reasoning for each being on or not on the network.

 The subnet mask on FerzleCorp's network is 255.255.224.0.
Given this, how many IP addresses are available on the their domain?
Explain how you arrived at your answer.
(Hint: What is the 32bit string representation
of the subnet mask, and what does that have to do with anything?)
 Suppose you try to access the KnowHope home page using the URL
http://www.hope.edu/knowhope, and get a message from your web browser
that the server cannot be contacted. You happen to know that the IP
address for www.hope.edu is 208.67.222.222, so you try
http://208.67.222.222/knowhope, and to your surprise, it works.
Clearly there is a problem somewhere on the network.
Where is the problem? Explain your answer.

The base network address for computers at Despair University is 198.110.96.0,
and the subnet mask is 255.255.240.0.
Given this, which of the following IPs addresses are on Despair University's network?
Justify your answers.
 198.110.98.147
 198.110.112.45
 198.121.98.6
Homework 14Do the following exercises from pages 195196 of your textbook (183184 in full book) and the ones below.
Problem  Points  Comments


1 below  6  This question is about network layers, so do not give an answer like 'DNS'.
 2 below  4 
 3 below  12  Reread the handout and make sure you decode the packet correctly. Especially pay attention to the order of data within the packet.
 43  4  Answer both parts of the question. Be specific and clear in your answer.
 45  6  Clearly justify your choice in each case. Read the roles of each layer and think carefully about each one.

 Hope does not allow access to KnowHope from machines that are off
campus without first entering a username and password.
 Which protocol layer determines whether or not a username and
password will need to be entered?
Explain. (Think carefully. What information is used and what
layer deals with that information? This is not asking about
the layer that asks for a username and password.)
 How can Hope's web server determine whether or not
a machine requesting access to KnowHope is on campus.
Give your answer in terms of
IP address, subnet mask, network base address,
and an appropriate computation.
 TCP, an implementation of the transport layer, breaks up messages
into packets for transmission.
 Give one reason why breaking up a message into packets is a good idea.
 Give one complication that arises from breaking up a message into packets.
 Being the unsavory sort of person you are, you decide to snoop on
the network. You see the following packet:
12:ab:22:83:f8:40aa:02:ef:23:00:12198.110.97.734.45.125.171175252 of 4nt to do somet
Label machines related to this packet as follows:

S is the original source of the packet
 D is the final destination
 M1 is the intermediate node that this message just came from
 M2 is the intermediate node that this message is just being sent to.
Keep in mind that it is possible that these are not 4 different machines.
You need to answer several questions based on the information in the packet.

If the information to answer a question is absolutely not contained in
the packet, write impossible to determine.

If the information to answer a question might be contained in
the packet but you cannot be certain,
write uncertain, but it might be X, where X
is the the possible answer(s).
Here are the questions.
 What is the IP address of S?
 What is the IP address of D?
 What is the IP address of M1?
 What is the IP address of M2?
 What is the Ethernet address of S?
 What is the Ethernet address of D?
 What is the Ethernet address of M1?
 What is the Ethernet address of M2?
 What is the port number of the application on S that sent the message?
 What is the port number of the application on D that the message is being sent to?
 What kind of application sent the message?
 What kind of application is the message destined for?
Note: An actual packet will not look like the one above.
It will just be raw data that needs to be interpreted to look like the packet above. An actual packet represented in hexadecimal might look like:
12ab2283f840aa02ef230012e678fc9a128832e6ca89e38eecfdac23549acd0f0ae345ccff52e
To simplify things for you (so you don't have to do a whole lot of converting), I have simply interpreted
the packet for you already. This comment has no bearing on this problem, but I thought it was important enough
to point out.
Homework 15Do the following exercises.
Problem  Points


#1 below  6
 #2 below  18
 #3 below  6
 #4 below  6

 You must show all of your work for this problem to receive credit!
 Assume the following string was encoded with the Hamming Code
discussed in class, and was transmitted over a noisy channel. Also
assume that at most 1 error occurred in each 7bit segment.
Message: 1111100 1111010 1001111 1100001 0100010 0000011 1010001
 Try to decode the message
(That is, give the hexadecimal characters that were encoded).
If you are unable to decode one or more letters, explain why.
 Assuming you were able to decode some or all of the characters in the
message, can you be certain that those were the characters that were sent?
Explain.
 Assume the following string was encoded with the Hamming Code
discussed in class, and was transmitted over a noisy channel, and
that it is possible that at most 2 errors occurred in each 7bit segment.
Message: 1011010 1001001 1010110 1111100 0111110
 Try to decode the message
(That is, give the hexadecimal characters that were encoded).
If you are unable to decode one or more characters, explain why.
 Assuming you were able to decode some or all of the letters in the
message, can you be certain that those were the characters that were sent?
Explain.
 Consider the string zip. This problem will explore the overhead associated with errorcorrecting codes.
 Encode the string using ASCII represented in binary.
 Encode the string using ASCII represented in hexadecimal.
 Encode the string from (a) with the Hamming Code discussed in class.
 Encode the string from (a) with the repetition code with k=3 discussed in class.
 How much larger is the binary string in (c) than the original in (a)?
(Give your answer in the form of "x times larger".)
 How much larger is the binary string in (d) than the original in (a)?
(Give your answer in the form of "x times larger".)
 Which code is more efficient in this case: The hamming code or the repetition code with k=3?
 Which code is able to correct more errors? Provide details.
 Which code is better? Why?

For this problem, assume that messages are written using the 26 characters
from the English alphabet.
 Draw a chart that can be used to decrypt a string that was
encrypted with the shift cipher with k=7.
Use it to decode the string FVBNVAPAOHSMYPNOA.
 The string YBPROBQLAOFKHVLROLSXIQFKB was encrypted with a
shift cipher with an unknown value of k.
 What was the original message?
 What value of k was used to encrypt the message?
Hint: You need to try several values of k
until you obtain a message that is readable.
You may use an online tool to do this,
but you should give the URL and provide all output in your homework.
 There are times when people need to transmit data in such a way
that it is secure, reliable, and efficient. Thus they may need to
encrypt it, apply an errorcorrecting code, and compress it.
Do you suppose it matters which order these operations are performed?
In other words, should they apply an errorcorrecting code then compress it and then encrypt it, or do these
three operations in some other order.
Let's assume the data to be sent is a memo encoded in ASCII or Unicode.
Suggest an order and clearly justify your ordering.
Note: It is important to realize that these operations are performed in the reverse order at the receiving end. Also, think about the purpose of each of the three operations you are performing on the data. For instance, when you transmit the data, consider what happens if there are errors and/or someone intercepts the packet. Can you correct the errors using your order? Is the original message protected from an observer?
You should also realize that if you encrypt it and then compress it or add error correction, the original data is still encrypted. In other words, encryption does not have to be the last thing you do. On the other hand, if you errorcorrect and then encrypt or compress, do you suppose you can still correct errors that occur?
