=========================preview======================
(COMP271)292f12 - final.pdf
Back to COMP271 Login to download
======================================================
COMP 271: Final Exam
2002 Fall Semester
17 December 2002
8:30 am C 11:30 am

You have 3 hours to solve 5 problems for a total of 100 marks. Answer all problems in the space provided. You may also use the back of the test papers. Good luck!
Student name: Student ID:
Problem
1
2
3
4
5
Your mark

Maximum
20
20
20
20
20
Your total marks:
Problem 1. (20 points) Answer the following in 2C4 sentences. In each case provide a clear
and precise explanation of your answer.
(a)
(3 points) Does the problem of deciding whether there exists a cycle in an undirected graph belong to the class NP?

(b)
(3 points) Does the problem of deciding whether there exists a cycle in an undirected graph belong to the class P?

(c)
(3 points) Consider the following problem: Given a set of n integers, sort them in non-decreasing order. Does this problem belong to the class P?

(d)
(3 points) Consider the following problem: Given an undirected graph G, decide whether or not it contain a clique of size 10. Does this problem belong to the class P?

(e)
(4 points) Assume that the 3-SAT decision problem does not belong to the class P. Does it then follow that the CLIQUE decision problem does not belong to the class P?

(f)
(4 points) Assume that the 3-SAT decision problem does not belong to the class P. Does it then follow that no problem in the class NP can be solved in polynomial time?


Problem 2. (20 points)
Let ai, i =1,2,...,8 be eight symbols. You are given a .le in which symbol ai occurs fi times (i.e. fi is the frequency of symbol ai)for i =1,2,...,8. If i is the number of bits in the codeword for symbol ai, then the total number of bits used to encode the .le is
8
fii. i=1
(a) (4 points) Explain why the total number of bits used to encode the .le is at most 3 .8
i=1 fi.
(b)
(8 points) Let fi = i for i =1,2,...,8, that is a1 has frequency f1 =1, a2 has frequency f2 = 2, etc. Construct an optimal binary pre.x code tree for this set of frequencies, using Hu.mans algorithm.

(c)
(4 points) From your answer in part (b), determine the corresponding variable length encoding of each of the symbols, a1,a2,a3,a4,a5,a6,a7,a8.

(d)
(4 points) Determine the total number of bits used to encode the .le, for the code of part (c).


Problem 3. (20 points)
Suppose you are given three strings of characters: X = x1x2 xn, Y = y1y2 ym, Z = z1z2 zp,where p = n + m. Z is said to be a shu.e of X and Y i. Z can be formed by interleaving the characters from X and Y in a way that maintains the left-to-right ordering of the characters from each string. The goal of this problem is to design an e.cient dynamic-programming algorithm that determines whether Z is a shu.e of X and Y .
(a)
(5 points) Show that cchocohilaptes is a shu.e of chocolate and chips, but that chocochilatspe is not.

(b)
(10 points) For any string A = a1a2 ar,let Ai = a1a2 ai be the s