CSCI 150, Spring 2003
Home | | Course Schedule | | Assignments | | Lecture Notes
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
b. What is the title of the web page?
c. Where does the link go?
d. What is the name of the web server that this page is served from?
e. Write the HTML file that would generate this page. Hint: Headlines of size 1 and 3 are in this page.
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:
Size time(secs) 1 0.5 2 2.0 3 4.5 4 8 5 12.5 ... ... 10 50 100 5000
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.
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.
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. Describe how we know that some functions are non-computable. Describe 2 problems that are non-computable.
Answer: Functions are not a countable set, but programs are a countable set. So if we pair up each program with a function, there will always be functions left over. These are the non-computable functions.
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 pascal program to read in integers into an array until a -1 is entered. Count the number of 2's entered and print out the result.
Answer:
program twoCounter;
type
intArray : array[1 . . 100] of integer;
var
myNumbers: intArray;
count: integer
twoCount: integer;
begin
writeln('Enter integers. End with a -1');
twoCount := 0;
count:= 1;
read (myNumbers[count]);
while myNumbers[count] <> -1 do
begin
if myNumbers[count] = 2 then
begin
twoCount := twoCount + 1;
end;
count := count + 1;
read(myNumbers[count]);
end;
writeln('The number of 2s is ', twoCount);
end.