Get premium membership and access revision papers, questions with answers as well as video lessons.

Got a question or eager to learn? Discover limitless learning on WhatsApp now - Start Now!

Comp 102:Discrete Mathematics Question Paper

Comp 102:Discrete Mathematics

Course:

Institution: Chuka University question papers

Exam Year:2013

CHUKA

UNIVERSITY

UNIVERSITY EXAMINATIONS

FIRST YEAR EXAMINATIONS FOR THE AWARD OF DEGREE
OF BACHELOR OF SCIENCE, COMPUTER SCIENCE

COMP 102: DISCRETE MATHEMATICS

STREAM: COMP Y1S2 TIME: 2 HOURS

DAY/DATE: MONDAY 6/8/2013 11.30 A.M – 1.30 P.M.

INSTRUCTIONS
• Answer QUESTION 1 and any other TWO QUESTIONS from section B.
• This is a CLOSED BOOK EXAM, No reference materials allowed in examination room. Make sure such materials are not found anywhere near your sitting.
• Do not write on this question paper
• No use of mobile phones, no memory watches.
• Write your answers legibly and use your time wisely.
• Scientific, non-programable Calculators may be used.

SECTION A: COMPULSORY

QUESTION 1[30MKS]

a) What is a theorem? [2 marks]

b) Discuss the various proof techniques [8 marks]

c) Give two areas in computer science where proof is useful [2 marks]

d) Suppose there are 50 people in a room, how many of them must have their birthday in the same month? [2marks

e) Each User on a computer system has a password which must be six to eight characters long.
Each character is an uppercase letter or digit.
Each password must contain at least one digit.
How many passwords are there? [6marks]
f) Suppose variable names in a given programming language can be either a single uppercase letter or an uppercase letter followed by a digit, find the number of possible variable names [2marks]

g) How many bit strings of length 8 either start with a 1 or end with two bits 00? [4marks]

h) Suppose a list A contains the 30 students in a mathematics class, and a list B contains the 35 students in an English class, and suppose there are 20 names on both lists. Find the number of students:

(i). Only on list A, (ii) only on list B, (iii) on list A or B (or both), (iv) on exactly one list.
[4marks]

SECTION B: ANSWER ONLY TWO QUESTIONS FROM THIS SECTION

QUESTION 2 [20MKS]

For each of the following functions, decide if it is one-to-one, onto, or neither.

Let D = {0,1,2,3,4,5,6,7,8,9}

(a) f : N × N ? N with the rule f(a, b) = a + b.
(b) f : D × D ? N with the rule f(a, b) = 10 • a + b.
(c) f : N × N ? N with the rule f(a, b) = a2 + b2.
(d) f : D × D ? D × D with the rule f(a, b) = (9 - b,9 - a)

QUESTION 3 [20MKS]

The symmetric di?erence of sets A and B, written A ? B, is de?ned as follows:
A ? B = {x ? U : (x ? A ? x ? B) ? ¬(x ? A ? x ? B)}

(U is the universal set.) Prove that A ? B ? (A - B) ? (B - A).

QUESTION 4 [20MKS]
For each of the following proofs, point out the ?aw in the proof or state that the proof is ?awless.

1. Claim If n is even, then n3 + 2n is divisible by 4.
Proof Suppose n is even. So n = 2k for some k. Then n3 + 2n = (2k)
3 + 2(2k) =8k
3 + 4k = 4(2k3 + k).

Therefore, n3 + 2n is divisible by 4.

2. Claim If a•b =n0, then a =n0 or b =n0.
Proof Suppose a • b =n 0. Either a =n 0 or not.
Case 1 If a =n 0, then trivially a =n 0 or b =n 0.
Case 2: If a 6=n0, then we multiple both side of a•b =n 0 by the reciprocal of a mod n (written a-1). So a-1• a • b =n a-1•0 and thus b =n0.
Therefore we can conclude that a =n0 or b =n0.

3. Claim If two numbers m and n are divisible by 3, then mn is divisible by 9.
Proof Let m=3k and n=3k. Then mn = 9k 2 and therefore, mn is divisible by 9.
4. Claim If n is even, then n2 is divisible by 4.
Proof Suppose n is even. Thus, there exists k such that n = 2k. Then n
2 = 4k2, which is divisible by 4.

Question 5 [20mks]

Think of the following situation: An evil professor has locked you in his house but gives you the following Opportunity to escape. There are two doors, one marked A and the other marked B. Each door could either be an exit or it could lead to a hungry tiger. On both doors there is a sign. If door A is an exit, then its sign is true and otherwise its sign is false.
In contrast, if door B leads to a tiger, then its sign is true and otherwise its sign is false.
Which door should you pick?

Door A Door B

The other door leads to a tiger. Not every door is an exit.

______________________________________________________________________________

Comp 102:Discrete Mathematics Question Paper

More Question Papers

Popular Exams