CSCI 110
Home | |
Course Schedule | |
Assignments | |
Lecture Notes
Review sheet solutions for Final Exam
Solutions to Practice Problems
The following problems are intended to help you study for the exam. In addition, you should
review the problems from the first two review sheets, along with your homework and labs.
1. Use the web page screen shot given in Figure 1 to answer the following questions. This
shot was taken when the mouse was over the link.
Figure 1. Screen shot of web page for problem 1
a. What is the filename of the web page?
b. What is the title of the web page?
c. Where does the link go?
Answer: http://www.google.com
d. What is the name of the web server that this page is served from?
Answer: mathcs.holycross.edu
e. Write the HTML file that would generate this page. Hint: Headlines of size 1 and 3 are
in this page.
Answer:
<HTML>
<HEAD>
<TITLE>Mystery Page</TITLE>
</HEAD>
<BODY BGCOLOR = "white">
<CENTER><H1>Hello World!</H1></CENTER>
<P>
<H3>Check out this magic
<A HREF = "http://www.google.com">link</A></H3>
</BODY>
</HTML>
2. The following equations give the running times (t) of different algorithms with respect to the size
of the input (n). For each, state whether the problem is tractable or intractable:
Answer:
3. The following table gives the running time of an algorithm for different input sizes:
Size time(secs)
1 0.5
2 2.0
3 4.5
4 8
5 12.5
... ...
10 50
100 5000
a) Draw a graph of the running time vs. the input size for sizes of 1 to 5.
b) Based on the values given, do you think this algorithm is tractable or intractable? Why?
Answer: This algorithm appears tractable, because it can process an input the size
of 100 in a relatively small amount of time (less than 1.5 hours). The actual running
time here is about 1/2 (n*n) which is a polynomial so it is tractable.
4. Protocols.
a) What is the purpose of a protocol?
Answer: A protocol is a set of rules that allow computers with different
operating systems to communicate or exchange information.
b) List three protocols that we covered in class, and briefly state their functions.
Answer: 1) TCP: Transmission control protocol--breaks email into packets at source
computer and puts message back together at destination.
2) IP: Internet protocol--routes email across internet.
3) HTTP: Hypertext Transfer Protocol--transfer web pages and associated files.
4) FTP: File Transfer protocol--transfer files from one computer to another.
5. What color does #FF00FF represent in the RGB color representation?
Answer: Purple
6. Suppose an image file has a bit depth of 8, a width of 100 pixels and a height of 200 pixels.
a) How many colors are can be represented in the image?
Answer: 256 (that is, 2 to the 8th power).
b) What is the size of the image if displayed on a monitor with a resolution of 50 ppi (pixels per
inch)?
Answer: 2 inches in width by 4 inches in height.
7. Briefly describe what "packet switching" means and how it is used on the internet.
Answer: Packet switching is the process in which email messages are broken
up into small "packets". Each packet is sent separately across the internet (and they
may take separate routes to their destination).
8. What is a non-computable function? Describe 2 problems that are
non-computable.
Answer: A non-computable function is one for which no computer program can be
written that will solve the function.
Two problems that are non-computable are:
- The Halting Problem: Determining whether a program will halt in a finite amount of time.
- Determining whether two programs are equivalent (for each input they both give the same output.)
9. Suppose you want to prove that a given problem was non-computable with a proof by
contradiction. What are the 2 steps you must accomplish for such a proof?
Answer: 1)Assume the program to solve the problem exists.
2) Show that this assumption leads to impossible consequences.
10. Write an assembly language (P88 instructions) to read in two numbers. If the first is bigger, it
should print out the first number. Otherwise the program should print nothing and end.
Answer:
IN AX
COPY X, AX
IN AX
CMP AX, X
JNB LAST
COPY AX, X
OUT AX
LAST END
11. Write a Python program to read words into a list until the word "stop" is entered. Count the number
of words entered that start with the letter 'a' and print out that number and the contents of the list.
Answer:
#Program aCounter.py
myWords = []
print "Enter words. Type stop to end."
aCount = 0
word = raw_input("Enter a word: ")
while word != "stop":
myWords.append(word)
if word[0] == 'a':
aCount = aCount + 1
word = raw_input("Enter a word: ")
print "The number of words starting with a is ", aCount
print "The list of words is ", myWords