=========================preview======================
(COMP170)Midterm1_2007_sol.pdf
Back to COMP170 Login to download
======================================================
HKUST C Department of Computer Science and Engineering
COMP170: Discrete Math Tools for CS C FALL 2007 Midterm Examination 1 C Solution Key
Date: Tue, October 09, 2007 Time: 19:00C20:30 Venues: LTA, LTB


Instructions
.
This is a closed book exam. It consists of 18 pages and 8 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.

.
Unless otherwise speci.edyou must always explain how you derived your answer. A number without an explanation will be considered an incorrect answer.

.
Solutions canbe written in terms of binomial coe.cients and falling facto-

rials. For example, 35 + 24 may be written instead of 16, and 53 instead of 60. Calculators may be used for the exam (but are not necessary).

.
Please do not use the nPk and nCk notation. Use nk and nk instead.


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

As part of HKUSTs introduction of an honor code, the HKUST Senatehas 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:
There will be n guests of honor at an award ceremony tomorrow. The guests will be seated on a platform in a row of n seats facing the audience.
(a)
How manydi.erent ways are there to seat the n guests in the n seats?

(b)
Let n> 2. Suppose now that two of the guests had a .ght and will not agree to sit next to each other. How many ways are there to seat the n guests so that the two who fought do not sit next to each other? Explain how you derived your answer.

(c)
Let n> 10. Now suppose that the guests include .ve married couples, and for each married couple, we want the husband and wife to sit next to each other. How many ways are there to seat the guests so that this happens? Explain how you derived your answer.


[Note: this question is independent of (b); that is, we no longer assume that there are two guests who fought each other.]
Ans: