National University of Computer and Emerging Sciences, Karachi
FAST School of Computing
Final Examination, Fall-2022
December 30, 2022, 08:30 AM – 11:30AM
Course Code: CS1005 Course Name: Discrete Structures
Instructor Names: Mr. Shoaib Raza, Ms. Bakhtawer, Ms. Safia, Ms. Fizza Aqeel, Mr. Fahad Hussain and Mr. Sudais
Student Roll No: Section No:
Instructions:
Return the question paper together with the answer script. Read each question completely before answering
it. There are 5 questions written on 4 pages.
In case of any ambiguity, you may make assumptions. However, your assumptions should not contradict any
statement in the question paper.
Attempt all the questions in the given sequence of the question paper. Show all steps properly in order
to get full points.
____________________________________________________________________________________________________
Total Time: 03 Hours Maximum Points: 80
Question # 1: [CLO -3, C4] [8 x 2 = 16 points]
(a) Let a, b, c and d be the propositions
a: The election is decided. b: The votes have been counted. c: Democrats candidate have lost.
Write these propositions using a, b, and c and logical connectives (including negations):
(i) Democratic candidate have not lost if the votes have not been counted.
(ii) The election is not decided only if the votes are not counted.
(iii) The votes have been counted but the Democratic candidate has lost.
(b) Using the premises (statements) from part (a), apply rules of inference to obtain conclusion(s) from these
premises. Also, name the rules of inference used to obtain each conclusion from the premises.
(c) Using a truth table, prove or disprove that the premises statements from part (a) and conclusion(s) from Part (b)
form a tautology.
(d) Prove or disprove the following the logical equivalence using the laws of logic:
¬ [c v (b ∧ (¬c → ¬a))] and ¬c ∧ (a v ¬b)
(e) Write the negation of the statement (ii) and (iii) from part (a) in English.
(f) Let Q (x, y) be the statement "x + y = x − y". If the domain for both variables consists of all integers. Determine
the truth value of the following statements.
(i) ∃y ∀x Q (x, y)
(ii) ∀y ∀x Q (x; y)
(g) Let C(x) be the statement "x is in the correct place" and E(x) be the statement "x is in excellent condition," and
let T(x) be the statement “x is a tool”, where the domain for the x consists of all tools. Use quantifiers to express
each of these statements.
(i) All tools are in the correct place and are in excellent condition.
(ii) One of your tools is not in the correct place, but it is in excellent condition.
1
(h) Write the English statement using the predicates from part (g) and any needed quantifiers:
(i) ∀x (C(x) ∧ E(x))
(ii) ¬∃x (C(x) ∧ E(x))
Question # 2: [CLO -2, C3] [8 x 2 = 16 points]
(a) Suppose in sets A, B, & C, the set B ∩ C consists of 8 elements, set A ∩ B consists of 7 elements and set C ∩ A
consists of 7 elements then how many minimum elements will be there in set A U B U C?
(b) Prove or disprove using Set Builder form: A ∩ (B − A) = ∅.
(c) Let f be the function from {1, 2, 3, 4} to {a, b, c, d} and g be the function from {a, b, c, d} to {1, 2, 3, 4}, with
f (1) = d, f (2) = c, f (3) = a, and f (4) = b, and g (a) = 2, g (b) = 1, g (c) = 3, and g (d) = 2.
Find f ° g, if does not exist, give reason.
(d) Find g ° f for function f and g given in part (c), if does not exist, give reason.
(e) Prove or disprove that the relation (f ° g) obtained in Part (c) is an equivalence relation.
(f) Does the relation (g ° f) obtained in part (d) holds Asymmetric Property, show proper steps.
(g) On April 27, 2000, more than 300 Kilogram of junk crashed to the ground of South Africa. The material was
eventually identified as a part of a Delta 2 rocket used to launch a global positioning satellite in 1996. The objects
fall toward the Earth in the absence of friction. Suppose in 1st second, it falls 16 feet, in the 2nd second ,48 feet, in
the next second, 80 feet, and so on. Find the distance the object travels in ten seconds.
(h) If there are 450 Discrete Math students giving exam in 11 rooms, what is the minimum possible number of students
in any of the rooms?
Question # 3: [CLO -2, C3] [8 x 2 = 16 points]
(a) Express in sigma notation the sum of the squares of first n natural numbers.
(b) Find the sum of the squares of first n natural numbers.
(c) Proof the sum expression obtained in part (b) with the help of mathematical induction.
(d) Prove or disprove using direct proof that if p is a positive even and q is an odd positive integers, then p*q is
an even integer.
(e) Prove or disprove by contradiction that √2 is irrational.
(f) Prove or disprove by contraposition that if x is an integer and 7x + 9 is even, then x is odd.
(g)Prove or disprove if an integer is a perfect square, then its cube root is irrational.
(h) Draw a graph from the set X = {1, 3, 7, 15, 31} to the set Y = {1, 3, 6, 10, 15} with edges defined by the
relatively prime relation, that is, the greatest common denominator of x and y, gcd (x, y), is equal to 1.
2
Question # 4: [CLO -3, C4] [8 x 2 = 16 points]
(a) The floor plan of a five-room house is shown in figure 01. The rooms are labeled A, B, C, D and E. The outside
of the house is labeled F. The openings represent doors. Draw a graph that models the connecting relationships on
the floor plan, where vertices represent rooms and the outside and edges represent connecting door.
Figure 01
(b) Is it possible to find a trail in figure 01 that starts and ends in room A, and passes through every interior doorway
of the house exactly once? If so, find such a trail.
(c) For a given pair of graphs G and G1 in figure 02. Determine whether G and H are isomorphic. If they are, give
function F: V(G) →V(H) that define the isomorphism. If they are not, give an invariant for graph isomorphism that
they do not share.
Figure 02
(d) Consider the graph shown in Figure 03. With the indicated link costs, use Dijkstra shortest-path algorithm to
compute the shortest path from A to all other nodes. Use the table given below for computations.
N D(B) D(C) D(D) D(E) D(F) D(G) D(H) D(I)
A - - - - -
Figure 03
(e) Set up a binary tree for the following list, in the given order, using reverse alphabetical ordering.
STOP, LET, THERE, TAPE, NONE, YOU, ANT, NINE, OAT, NUT.
(f) We have 6 blocks of memory to store data. Data items 24, 4, 2, 33, 7, 35 are needed to store on those blocks.
How will the items be stored to make future retrieval of the items faster?
(g) A data entry operator is entering books in a library system with their ISBNs, while entering the data he saw a
previously added ISBN ‘0800101130’ which he feels is erroneous. How can he verify if the previously entered
ISBN is correct or not.
(h) Find the third element in the fourth row of Pascal’s triangle.
3
Question # 5: [CLO -2, C3] [8 x 2 = 16 points]
A box contains gold coins:
If the coins are equally divided among 13 friends, seven coins are left over.
If the coins are equally divided among 19 friends, sixteen coins are left over.
If the coins are equally divided among 21 friends, nineteen coins are left over.
If the coins are equally divided among 25 friends, thirteen coins are left over.
If the box holds the smallest number of coins that meets these four conditions, how many coins are left?
In this problem, you are supposed to state and use of the following theorems:
(a) Apply:
(i) Linear congruences
(ii) The Euclidean Algorithm Lemma
(b) Apply:
(i) Bézout’s Theorem
(ii) Chinese Remainder Theorem
(c) A message has been encrypted using the function f (P) = (P + 5) mod 26. If the message in encrypted form is
VZJXYNTS UFUJW, decrypt the message.
(d) Use Fermat’s little theorem to calculate the remainder of 8751 when divided by 47.
(e) How many permutations of the letters ABCDEFG contain:
(i) the string BCD?
(ii) the strings BA and GF?
(f) A box contains 8 blue socks and 6 red socks. Find the number of ways two socks of same color can must be
drawn from the box.
(g) Find the last term of (a - 2b)4 using the binomial theorem.
(h) How many ways are there of choosing k things from {1 . . . n}, if 1 and 2 can’t both be chosen? (Suppose n, k≥2.)
BEST OF LUCK