Assigned on Friday, 11/14/03.
Due on Wednesday, 11/19/03.
This is an exam, and should be viewed as such. Specifically:
What you are allowed to do: You may refer to your own class notes, the textbook, the lab book, the HTML tutorial, your homework assignments, and the lab applets. You may ask me in person or via email for clarification questions.
What you are not allowed to do: You may not discuss this exam or any material on it with anybody, except for me. You may not use the WWW, the Internet at large, or any other external sources apart from those listed above in order to answer the questions on this exam.
To further clarify web usage: You may only use the class web page, the HTML tutorial linked from the class web page, and the lab applets. You may not surf, search, or visit any other websites in working on this exam.
If you have any questions about what is legitimate use: ask me!
Turn in your answers to the following questions on paper.
Suppose that I wish to keep a collection of integers in sorted order. I can choose to do so with an array, or with a linked list. Whenever I insert or delete an integer, I want my data to remain in sorted order.
(a) Is inserting a new item quicker with a linked list or array? Why?
(b) Is looking up the 106th number in the list quicker with a linked list or array? Why?
(c) Does storing the data in an array take more, less, or the same amount of memory than storing the data in a linked list? Why?
(d) Does storing the data in an array make writing software to use it easier, harder, or about the same than storing the data in a linked list? Why?
Suppose the following list of numbers is stored in an array:
18, 19, 6, 2, 27, 30, 25
For each parts (a) and (b) below, show your work and explain your steps. You need to convince me that you know what you're doing, and have not merely transcribed steps from the sorting applet. You are welcome to use the sorting applet if you wish, though I suspect that it will not be all that useful in being able to document each step.
(a) Show each step when sorting the list with selection sort.
(b) Show each step when sorting the cost with quicksort.
(c) When analyzing the effectiveness of sorting techniques, why don't we compare running times? What do we measure instead, and why?
Pretend that nobody at Carleton has ever tried to view the web site http://www.badgerbadgerbader.com, but that you have now launched your web browser in anticipation of viewing this site for the first time. Tell the story of what happens between the time you type "http://www.badgerbadgerbadger.com" and hit the Enter key and the time the Badger Badger Badger (BBB) home page appears on your screen. Your story should include something about the process your browser goes through to obtain the IP address of www.badgerbadgerbadger.com, which computer your browser contacts once the IP address is in hand, how the browser goes about requesting the BBB home page, what gets handed back to the browser, and how that information gets translated into the page your browser displays for you. I'd like a couple paragraphs, or perhaps a step-by-step list of events. You may find it helpful to draw a diagram, though that's up to you.
(a) Why does TCP use packets for transmitting information?
(b) TCP packets are often of a moderately small size, such as 1500 bytes. Why shouldn't TCP packets be as small as possible? Explain the good and the bad ramifications of having extremely small TCP packets.
(c) Why shouldn't TCP packets be as large as possible? Explain the good and bad ramifications of having extremely large TCP packets.
(d) Suppose that an ACK packet is lost during a TCP session. What happens? Does this prevent information from making it intact to the destination?
(e) Suppose that a NAK packet is lost during a TCP session. What happens? Does this prevent information from making it intact to the destination?
(f) Suppose that a NAK packet were corrupted so that it became an ACK (this is not likely to really happen). What happens? Does this prevent information from making it intact to the destination?
(g) Suppose that an ACK packet were corrupted so that it became a NAK (this is not likely to really happen). What happens? Does this prevent information from making it intact to the destination?
(h) What is the difference between TCP and IP? What aspects of Internet communication does each handle?
(a) Describe the "halting problem."
(b) What role does the halting problem play in Alan Turing's considerations on whether or not machines can think?
(c) Does the halting problem strengthen, weaken, or not affect John Searle's argument? Searle does not address this directly, so this is something of an "opinion" question. I do, however, expect that you back up your thoughts with specific evidence from Searle's paper. You must indicate in your answer that you understand Searle's perspective. Your answer does not need to be long to satisfy the above requirements.
Create a web page that displays your course schedule for this term in a table. One of the columns of your table should contain links to the course home page, if such a page exists (it does for CS 107, at http://www.mathcs.carleton.edu/faculty/dmusican/cs107f03). Print out and turn in your HTML on paper.