CSCI 112 Fall 2016
Exploring Computer Science
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Homework
Project

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

All Homework

Homework 1

  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)
    1. How many assignments can you turn in late? What is the penalty?
    2. What percentage of your grade are exams? What percent is each exam?
    3. When are my office hours?
    4. If you can't come to my office hours, what is the best way to find a time to meet with me?
    5. Is one of the topics of coverage for the course Networks?
    6. Can you tell exactly what grade you got on any assignment in the course at any time?
    7. What grade will you get if your final percentage in the course is 86?
    8. What is due on Wednesday, September 7, and at exactly what time(s)?
    9. Will I give extra credit assignments to students who are not performing well in the course?
    10. How many of the Questions & Answers do you need to complete for each section? Do you turn them in?
    11. Can you listen to your iPod or send a text message when you are in the classroom?
    12. What percentage of your final grade is the third paper worth?
    13. How many papers will you submit to me this semester?
    14. How many problems are on Homework 9?
    15. If you need help during the evening hours, are there any options?
    16. How many points is Homework 12 worth? What about Homework 14? Which one of these counts more toward your final grade?
    17. When is the Midterm exam?
    18. Can you take the Midterm on a day other than what is specified?
    19. Is reading the textbook optional? Explain.
    20. Can homework be hand written?

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

Do the following exercises from pages 67-68 of your textbook.
ProblemPoints
24
64
75
93

Homework 3

Do the following exercises from pages 68-69 of your textbook.
ProblemPointsNotes
104
134Show an appropriate calculation for each case and then interpret the result of your calculation.
154
173
183

Homework 4

Do the following exercises from page 69 of your textbook and the ones listed below.
ProblemPointsNotes
204To 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.
234
244
#1 below6

  1. Consider the bitstring 01101101.
    1. Give as many interpretations of this bit string as you can think of. (Give at least 4 specific interpretations for full credit.)
    2. What does the bitstring mean?

Homework 5

Do the following exercises from pages 69-70 of your textbook and the other ones listed below.
ProblemPoints
32abcd8
#1 below8
#2 below8

  1. 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.
    1. Convert the binary number 100110 to decimal.
    2. Convert the six-bit two's complement number 100110 to decimal.
    3. Convert the binary number 010111 to decimal.
    4. Convert the six-bit two's complement number 010111 to decimal.
  2. 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.
    1. Convert the decimal number 13 to binary.
    2. Convert the decimal number 13 to six-bit two's complement.
    3. Convert the decimal number -23 to six-bit two's complement.
    4. Can you convert the decimal number -23 to binary? Why or why not?

Homework 6

Do the following exercises from pages 70-71 of your textbook. As always, clearly show your work for each problem.
ProblemPoints
37 cde6
394
446
#1 below4

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

Do the following exercises from page 108 of your textbook (102 in full book).
ProblemPoints
43
710
84
910

Homework 8

Do the following exercises from pages 109-113 of your textbook (103-107 in full book).
ProblemPointsComments
146
184Make sure you explain your answer.
194Give a clear justification based on your solution to 18.
214
23b4
282First write out what each instruction does. Then read your "pseudo-code" 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, ...")
34aei6
39bc4
252See note below
Problem 1 below4See note below

  1. 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. E-mail me your textfile.

Homework 9

Do the following exercises from pages 112-113 of your textbook (106-107 in full book) and the ones listed below.
ProblemPointsComments
434
483
503In other words, give an algorithm/procedure that accomplishes what is asked.
#1 below6
#2 below6
#3 below4
#4 below2
#5 below4
Note: For problems 1-4, do not worry about potential problems that jump instructions might cause.

  1. If a program written in our machine language consists of 15 instructions,
    1. How many steps are required to execute the program if it is executed normally?
    2. How many steps are required if pipelining is used?
    3. 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.)
  2. If a program written in our machine language consists of 100 instructions,
    1. How many steps are required to execute the program if it is executed normally?
    2. How many steps are required if pipelining is used?
    3. How much faster is pipelining than normal execution for this program?
  3. Generalize the previous results: If a program written in our machine language consists of n instructions,
    1. Give a formula for the number of steps required to execute the program normally.
    2. Give a formula for the number of steps required if pipelining is used.
    3. Give a formula for how much faster pipelining is than normal execution.
    4. 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?)
  4. 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.
  5. 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 10

Do the following exercises from pages 143-144 of your textbook (133-134 in full book) and the one listed below.
ProblemsPoints
144
234"how much" means a percentage.
254Think about what happens in both possibilities. Clearly explain your answer.
274
Problem 1 below4

  1. What is the difference between multitasking and multiprocessing? Be specific, but brief.

Homework 11

Do the following exercises from pages 144-145 of your textbook (134-135 in the full book) and the ones listed below.
ProblemPointsComments
334Answer both parts.
414Answer both parts.
424Make sure you understand the exact definitions of the two terms. Also, try to exhaust all possible causes of each.
434
474Give your answer using reasonable units (e.g. days or years if it is really large).
Problem 1 below4
Problem 2 below4

  1. 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?
  2. 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 12

Do the following exercises from pages 194-195 of your textbook (182-183 in full book) and the ones listed below.
PROBLEMPointsComments
134Give specific numerical evidence for your answer.
146
164This problem involves two conversions. Show both.
1 below6
2 below4
3 below2

    1. What is the difference between a bridge and a repeater?
    2. What is the difference between a bridge and a switch?
    3. What is the difference between a switch and a router?
  1. 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.
    1. Why is this a good thing?
    2. Give one problem that arises because of this.
  2. 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 13

Do the following exercises from pages 194-195 of your textbook (182-183 in full book) and the ones listed below.
ProblemPointsComments
275
344The problem gives a single URL. It is too long so it is displayed on two lines.
1 below4Show all of the relevant calculations.
2 below4This is not asking about network layers.
3 below3Show your calculations for all three IP addresses, and explain your reasoning for each being on or not on the network.

  1. 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 32-bit string representation of the subnet mask, and what does that have to do with anything?)
  2. 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.
  3. 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.
    1. 198.110.98.147
    2. 198.110.112.45
    3. 198.121.98.6

Homework 14

Do the following exercises from pages 195-196 of your textbook (183-184 in full book) and the ones below.
ProblemPointsComments
1 below6This question is about network layers, so do not give an answer like 'DNS'.
2 below4
3 below12Re-read the handout and make sure you decode the packet correctly. Especially pay attention to the order of data within the packet.
434Answer both parts of the question. Be specific and clear in your answer.
456Clearly justify your choice in each case. Read the roles of each layer and think carefully about each one.

  1. Hope does not allow access to KnowHope from machines that are off campus without first entering a username and password.
    1. 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.)
    2. 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.
  2. TCP, an implementation of the transport layer, breaks up messages into packets for transmission.
    1. Give one reason why breaking up a message into packets is a good idea.
    2. Give one complication that arises from breaking up a message into packets.
  3. 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:40|aa:02:ef:23:00:12|198.110.97.7|34.45.125.17|1175|25|2 of 4|nt 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.
    1. What is the IP address of S?
    2. What is the IP address of D?
    3. What is the IP address of M1?
    4. What is the IP address of M2?
    5. What is the Ethernet address of S?
    6. What is the Ethernet address of D?
    7. What is the Ethernet address of M1?
    8. What is the Ethernet address of M2?
    9. What is the port number of the application on S that sent the message?
    10. What is the port number of the application on D that the message is being sent to?
    11. What kind of application sent the message?
    12. 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 15

Do the following exercises.
ProblemPoints
#1 below6
#2 below18
#3 below6
#4 below6

  1. You must show all of your work for this problem to receive credit!
    1. 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 7-bit segment.
      Message: 1111100 1111010 1001111 1100001 0100010 0000011 1010001
      1. 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.
      2. 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.

    2. 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 7-bit segment.
      Message: 1011010 1001001 1010110 1111100 0111110
      1. 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.
      2. 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.

  2. Consider the string zip. This problem will explore the overhead associated with error-correcting codes.
    1. Encode the string using ASCII represented in binary.
    2. Encode the string using ASCII represented in hexadecimal.
    3. Encode the string from (a) with the Hamming Code discussed in class.
    4. Encode the string from (a) with the repetition code with k=3 discussed in class.
    5. How much larger is the binary string in (c) than the original in (a)? (Give your answer in the form of "x times larger".)
    6. How much larger is the binary string in (d) than the original in (a)? (Give your answer in the form of "x times larger".)
    7. Which code is more efficient in this case: The hamming code or the repetition code with k=3?
    8. Which code is able to correct more errors? Provide details.
    9. Which code is better? Why?
  3. For this problem, assume that messages are written using the 26 characters from the English alphabet.
    1. 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.
    2. The string YBPROBQLAOFKHVLROLSXIQFKB was encrypted with a shift cipher with an unknown value of k.
      1. What was the original message?
      2. 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.
  4. 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 error-correcting code, and compress it. Do you suppose it matters which order these operations are performed? In other words, should they apply an error-correcting 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 error-correct and then encrypt or compress, do you suppose you can still correct errors that occur?