CSE2133 — Discrete Mathematics¶
Estimated Exam Suggestion¶
Important: This is an evidence-based suggestion prepared from the supplied question papers for Terms 151, 161, 171, 181, 191, 201, 211. It is not a guaranteed question paper.
How This Suggestion Was Prepared¶
- Every topic was counted by the number of distinct terms in which it appeared.
- A topic was counted only once in one term, even when several sub-questions from that term covered it.
- The core set prioritizes repeated topics while maintaining coverage across the handbook chapters.
- Every selected block is an intact question number from a supplied past paper.
- Original wording, spelling, grammar, numbering, marks, equations, code, tables and supplied figures are retained.
- Original figures are embedded directly in this Markdown file, so no separate image folder is required.
Quick Frequency Graph¶
Priority Summary¶
| Priority | Topics |
|---|---|
| Very high | Predicates, quantifiers and logical translation; Functions, composition and relations |
| High | Propositions, truth tables and logical equivalence; Graph fundamentals, degree and representation; Binary trees, traversals and representations; Sets, set identities and set operations |
| Strong | Counting, combinations and probability; Pigeonhole principle and applications; Expression trees and prefix/postfix evaluation; Graph isomorphism, planarity, coloring and bipartite graphs |
| Medium | Euler, Hamilton and traversable graphs; Number theory, divisibility, GCD and modular arithmetic; Cryptography and pseudorandom-number generation; Proof methods, induction and recursion; Minimum spanning tree and weighted graphs; Tree memory representation |
Core Estimated Question Set¶
Revise these seven original past-paper blocks first.
Core Question 1 — Propositions, Truth Tables and Logical Equivalence¶
Original source: Term 191, Question 1
-
Q1(a) [2+2]: Define Discrete mathematics. List out the problems that can be solved using Discrete Mathematics.
-
Q1(b) [5]: What is proposition? Let p be the statement "Maria learns discrete mathematics." and q the statement "Maria will find a good job." (i) Express \(p\to q\) as a statement in English. (ii) Express \(p\leftrightarrow q\) as a statement in English. (iii) Show the truth table of \(p\to q\) and \(p\leftrightarrow q\).
-
Q1(c) [3+2]: Define tautology, contradiction and contingency. Show that \(\neg p\lor q\) and \(p\to q\) are logically equivalent.
Core Question 2 — Logic, Predicates, Quantifiers and Function Composition¶
Original source: Term 191, Question 2
-
Q2(a) [6]: Let \(A=\{a,b,c\}\), \(B=\{1,2,3\}\), \(C=\{w,x,y,z\}\), \(D=\{4,5,6\}\) and the functions \(f:A\to B\), \(g:B\to C\), and \(h:C\to D\) are determined as \(f=\{(a,2),(b,1),(c,2)\}\), \(g=\{(1,y),(2,x),(3,w)\}\) and \(h=\{(x,4),(y,6),(z,4),(w,5)\}\). Find the composition function \(h\circ g\circ f\).
-
Q2(b) [3]: Define basic logic operations with example.
-
Q2(c) [5]: Translate the following English statements into Logical Expressions using predicates and quantifiers: (i) "Some students in the class has visited Cairo". (ii) "Every student in the class has visited either Aswan or Cairo".
Core Question 3 — Pascal’s Triangle, Combinations and Pigeonhole Principle¶
Original source: Term 171, Question 3
-
Q3(a) [5]: Using Pascal's Triangle find the value of \((a-b)^6\).
-
Q3(b) [5]: A bag contains six white marbles and five red marbles. Find the number of ways four marbles can be drawn from the bag if two must be white and two red.
-
Q3(c) [4]: Using the Pigeon hole principle solve the following problem: Find the minimum number of students needed to guarantee that five of them belong to the same class (Freshman, Sophomore, Junior, Senior).
Core Question 4 — Pseudorandom Numbers and Shift Cipher¶
Original source: Term 191, Question 4
-
Q4(a) [6]: Generate 10 pseudorandom number using the linear congruential method with modulus \(m=9\), multiplier \(a=7\), increment \(c=4\), and seed \(x_0=3\).
-
Q4(b) [4+4]: Decrypt these messages encrypted using the shift cipher \(f(p)=(p+10)\bmod26\): (i)
CEBBOXNOB XYG; (ii)LO WI PBSOXN.
Core Question 5 — Weighted-Graph Representation and Minimum Spanning Tree¶
Original source: Term 171, Question 6
-
Q6(a) [10]: Suppose a weighted graph G in Fig. 2. Represent the graph in memory using sequential and linked list representation.
-
Q6(b) [4]: Find the minimum spanning tree from the graph G in Fig. 2.
Core Question 6 — Planar Graph, Isomorphism and Hamilton Circuits¶
Original source: Term 191, Question 7
-
Q7(a) [3+2]: Define planar graph and chromatic number with example. Explain why \(K_5\) and \(K_{3,3}\) are non-planar?
-
Q7(b) [5]: Check whether the following two graphs are isomorphic or not?
- Q7(c) [4]: Write down the necessary Conditions for Hamilton Circuits.
Core Question 7 — Logical Translation, Recursion and Binary-Tree Representation¶
Original source: Term 191, Question 6
-
Q6(a) [4]: Let x and y be positive integers, and suppose P is defined recursively as follows: \(P(x,y)=0\) if \(x<y\); \(P(x,y)=P(x-y,y)+1\) if \(y\le x\). Find \(P(26,5)\).
-
Q6(b) [4]: Translate these statements into English, where C(x) is "x is a comedian" and F(x) is "x is funny" and the domain consists of all people: (i) \(\forall x(C(x)\land F(x))\); (ii) \(\exists x(C(x)\land F(x))\).
-
Q6(c) [6]: Given a memory representation of binary tree as follows. Root=2; Avail=4. (i) Draw the diagram of the tree. (ii) Find the preorder, in-order and post-order traversals.
High-Value Backup Question Set¶
Revise these after completing the seven core blocks.
Backup Question 1 — Logical Equivalence, Tautology and Quantifiers¶
Original source: Term 171, Question 1
-
Q1(a) [1+3]: Define logical equivalence. Show that the propositions \(p\lor(q\land r)\) and \((p\lor q)\land(p\lor r)\) are logically equivalent.
-
Q1(b) [4]: Show that \((p\land q)\to(p\lor q)\) is a tautology.
-
Q1(c) [4]: Let \(A=\{1,2,3,4,5\}\). Determine the truth value of each of the following statement with explanation: (i) \((\exists x\in A)(x+3=10)\); (ii) \((\forall x\in A)(x+3<10)\); (iii) \((\exists x\in A)(x+3<5)\); (iv) \((\forall x\in A)(x+3<7)\).
-
Q1(d) [2]: Prove that \(\neg(p\land q)\equiv\neg p\lor\neg q\).
Backup Question 2 — Counting and Binary-Tree Representation¶
Original source: Term 201, Question 4
-
Q4(a) [5]: Using Pascal's Triangle find the value of \((a+b)^6\).
-
Q4(a) [4]: Represent the following algebraic representation using binary tree: \(((a+b)(c+d))-(e+f)/h+g\).
-
Q4(b) [5]: A bag contains six white marbles and five red marbles. Find the number of ways four marbles can be drawn from the bag if two must be white and two red.
-
Q4(b) [4+9]: Given a memory representation of binary tree as shown. Root=2; Avail=4. (i) Draw the diagram of the tree. (ii) Find the preorder, in-order and post-order traversals.
Backup Question 3 — Spanning Trees and Binary Numbers¶
Original source: Term 211, Question 5
- Q5(a) [8]: Find all eight spanning trees of the graph in Fig. 5(a).
- Q5(b) [6]: Using tree diagram find the four-bit binary numbers without consecutive 0's.
Backup Question 4 — Graph Representation and Minimum Spanning Tree¶
Original source: Term 201, Question 2
-
Q2(a) [5]: Suppose a weighted graph G in Fig. 2b. Represent the graph in memory using sequential and linked list representation.
-
Q2(b) [4]: Find the minimum spanning tree from the graph G in Fig. 2b.
Backup Question 5 — Binary Search Tree, Traversal and Postfix Evaluation¶
Original source: Term 171, Question 7
-
Q7(a) [5]: Form a binary search tree for the words mathematics, physics, geography, zoology, meteorology, geology, psychology and chemistry (using alphabetic order).
-
Q7(b) [5]: Perform the in-order, pre-order and post-order traversal in the given tree.
- Q7(c) [4]: What is the value of the postfix expression
7 2 3 * - 4 ↑ 9 3 / +?
Final Revision Checklist¶
- Complete all seven core question blocks.
- Complete all five backup blocks if time permits.
- Practise every embedded graph, tree, class diagram, equation, algorithm and code fragment exactly as shown.
- Use the separate topic-frequency file to cover any remaining syllabus area.