Back to COMP2711 Login to download
HKUST C Department of Computer Science and Engineering
COMP170: Discrete Math Tools for CS C Spring 2011 Final Examination
Date: Thursday May 26, 2010 Time: 12:30-15:00 Venue: Sports Hall

Name: Student ID:
Email: Lecture and Tutorial:

This is a closed book examination. It consists of 16 pages and 9 questions.

Please write your name, student ID, email, lecture and tutorial sections 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 (and sometimes has an extra page for you to do work on). 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.

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

Calculators may be used for the examination.

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

Student ID:

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:
Student ID:

Problem 1: (10 Points) In this question, n and j are two non-negative integers such that n =3j.
A bag of n candies are distributed among a group of n children as follows:
At the beginning, the whole bag is given to one child.

After a child receives a bag of candies,

He keeps the whole bag to himself if the bag contains fewer than 3 candies;

Otherwise, he divides it into three smaller bags, each with 1/3 of the candies. He keeps one of the smaller bags to himself (even though it might contain 3 or more candies), and passes the other two bags to two other children who have not received any candies.

There is only one table where a bag of candies can be divided into smaller bags, and only one child can use it at one time. That means that no two children can use the table simultaneously. Suppose it takes log3 m seconds to divide a bag of m candies into three equal size smaller bags. Furthermore, there is no idle time once the distribution process is s