=========================preview======================
(COMP2711)[2012](s)final~=baru6^_24968.pdf
Back to COMP2711 Login to download
======================================================
HKUST C Department of Computer Science and Engineering
COMP 2711: Discrete Math Tools for CS C Spring 2012
Final Examination

Date: 25 May 2012 Time: 16:30C19:30 Venue: HALL
#

Name: Student ID:
Email: Lecture and Tutorial:

Instructions
.
This is a closed book exam. It consists of 9 questions and 19 pages.

.
Please write your name, student ID, email, lecture section and tutorial on this page.

.
For each subsequent page, please write your student ID at the top of the page in the space provided.

.
Please sign the honor code statement on page 2.

.
Answer all the questions within the space provided on the examination paper. You may use the back of the pages for your rough work. The last three pages are scrap paper and may also be used for rough work. Each question is on a separate page. This is for clarity and is not meant to imply that each question requires a full page answer. Many can be answered using only a few lines.

.
Unless otherwise speci.ed you must always explain how you de-rived your answer. A number without an explanation will be considered an incorrect answer.


Questions 1 2 3 4 5 6 7 8 9 Total
Points 10 11 10 10 12 10 15 10 12 100
Score

As part of HKUSTs introduction of an honor code, the HKUST Senate has recommended that all students be asked to sign a brief declaration printed on examination answer books that their answers are their own work, and that they are aware of the regulations relating to academic integrity. Following this, please read and sign the declaration below.
I declare that the answers submitted for this examination are my own work.
I understand that sanctions will be imposed, if I am found to have violated the University regulations governing academic integrity.
Students Name:

Students Signature:
Problem 1: [10 points]
1. Consider the recurrence below de.ned for n 0.
1 if n =0
T (n)= 4T (n . 1)+6 if n> 0
Give a closed-form, exact solution to the recurrence. You only have to give the solution. You do not need to show how you derived it.
2. Prove the correctness of your solution by induction.
Solution:
1. By iterating the recurrence, we get:
4n . 1
T (n)=4n +6 =3 4n . 2.
4 . 1
2. We need to prove:
T (n)=3 4n . 2. (1)
Base case: When n = 1, T (0) = 1 = 3 40 . 2. Equation (1) is true.
Inductive step: Now consider n> 1. Assume Equation (1) is true for the case of n . 1, i.e., T (n . 1) = 3 4n.1 . 2.
For the case of n, we have
T (n)=4T (n . 1) + 6 = 4(3 4n.1 . 2) + 6 (induction hypothesis) =3 4n . 2.
By the weak principle of mathematical induction, we conclude that Equa-tion (1) is true for all n 0.
Grading: 5, 5 .

Problem 2: [11 points] Let a be a non-negative real number and n be a non-negative integer that is a power of 3. Consider a function T (n) given by
1 if n =1
T (n)= 2
aT (n 3 )+ nif n> 1
1.
Find a closed-form expression for T (n)