Discrete Structure BSCS 2nd TERM Past paper 2015 UOS
University of Sargodha
BS 2nd Term Examination 2015
Subject: Computer Science
Paper: Discrete Structure (CMP-2211)
Time Allowed: 2:30 Hours
Maximum Marks: 80
Objective Part (Compulsory)
Q 1: Write short answers to the following. (2*16)
- Differentiate between bound and free variable with the help of an example?
- Find the negation of this statement:
∀x ∀y (x > 0) ∧ (y < 0) → (xy < 0) - Write the converse of this statement: “If we prepare the exam, then we will get the good grade.”
- Write the addition rule of inference?
- Define Vacuous Proof?
- Differentiate between subset and proper subset?
- Is the function f(x) from the set of integers to the set of integers one-to-one?
- Find a formula for this sequence: 1, 1/2, 1/3, 1/4, 1/5, …
- Define the correctness of an algorithm?
- Differentiate between sum and product rule with the help of an example?
- How many relations are there on set S = {a, b, c}?
- Differentiate between function and relation?
- Draw graph K₄.
- Compute the degree of every vertex in this graph?
- List the members of the following sets:
a. {x | x is a real number such that x² = 4}
b. {x | x is an integer such that x² = 2} - Use truth table to determine whether (¬p ∧ (p → q)) → r is a tautology.
Subjective Part
(Note: Attempt any four out of six questions. All questions carry equal marks.)
Long Questions Maximum Marks 48
Q 2:
I. Translate this statement into quantifiers and predicates logic:
“For all x, for all y
Q3: Rooted Tree Analysis
a) Height of the Given Tree
- The height is defined as the length of the longest path from the root to a leaf.
- Count the number of edges from the root (a) to the furthest leaf.
b) Write $ |A \cup C| $
- If sets and are defined, calculate the union of both and find the size of the resulting set.
c) Write $ (A \cap B) \times (A \cap C) $
- Identify intersections of sets and , and and , then compute the Cartesian product of the resulting sets.
d) Ancestors of Vertex $ q $
- List all vertices leading up to from the root, including itself.
e) Descendants of Vertex $ d $
- List all offspring vertices stemming from downward.
Q4: Quotient and Remainder
I. Quotient and Remainder of -11 Divided by 3
- Use division to find quotient and remainder where .
II. Show $ 2x^3 + 3x + 1 $ is $ O(x^3) $
Q5: Graph Theory
a) Hamilton Circuit/Path
- Check the provided vertices to determine if a Hamilton circuit/path exists.
b) Bipartiteness of Graph
- Verify if you can color the graph’s vertices with two colors without adjacent vertices sharing the same color.
Q6: Password Combinations
I. Count Possible Passwords
- Calculate the number of combinations considering the length and required character types (uppercase letters and digits).
II. Tree Diagram Representation
- Construct a tree diagram to illustrate how many bit strings of length 4 contain no three consecutive zeros.
Q7: Relation on Set $ A = {1, 2, 3, 4} $
I. Represent the Relation
- Draw a directed graph for the relations given in set .
II. Determine Properties of the Relation
- Check if the relation is reflexive, symmetric, antisymmetric, or transitive based on the pairs in .