=========================preview======================
(COMP170)Midterm_2_2005_sol.pdf
Back to COMP170 Login to download
======================================================
HKUST C Department of Computer Science
COMP170: Discrete Math Tools for CS C FALL 2005 Midterm Examination 2
Solution Key Date: Tue, Nov 8, 2005 Time: 19:00C20:30 Venues: LTD, LTC, LTB


Instructions
.
This is a closed book exam. It consists of 20 pages and 10 questions.

.
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 clarityand is not meant to imply that each question requiresa full page answer. Many canbe answered using only a few lines.

.
Only use notation given in class. Do not use notation thatyou have learnt outside of this class that is nonstandard.

.
Calculators may be used for the exam.

.
In questions 8, 9 and 10 you are asked for a solution to a recurrence. A solution means a formula given in closed form. Formulas using the summa-


tion symbol( )or ellipses(...)will not be accepted as answers.
Questions 1 2 3 4 5 6 7 8 9 10 Total
Points 10 10 10 6 11 8 12 9 12 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:
De.nitions and Formulas: This page contains some de.nitions used in this exam and a list of formulas (theorems) thatyou may use in the exam (without having to provide a proof). Note that you might not need all of these formulas on this exam.
De.nitions
1.
N = {0, 1, 2, 3,...}, the set of non-negative integers.

2.
Z+ = {1, 2, 3,...}, the set of positive integers.

3.
R is the set of real numbers.

4.
R+ is the set ofpositive real numbers.


Formulas:
nn!
1. =
ii!(n.i)!
nn.1 n.1
2. If0 <i<n then =+ .
ii.1 i
3.
.(p q)is equivalent to .p .q.

4.
.(p q)is equivalent to .p .q.

5.
..x U (p(x)) is equivalent to .x U (.p(x))


n.1
6. i=1 i = n(n .1)/2.
.3
n.1 i22n.3n2+n
7. = .
i=1 6
.n
n.1 i 1.r
8. If r .1 then r==
i=0 1.r
.n+2 n+1
n nr.(n+1)r+r
9. If r .1 then iri =
=
i=0 (1.r)2
.2 n+2 2n+3
n ir+r.(n+1)2 rn+1+(2n2+2n.1)r.nr
10. If r .=1 then r=
i=0 i2(