Discrete Structure
Semester II · BCA 151 · 3 credits
0 / 6
chapters done
-
The syllabus asks for
- Propositions and connectives
- Tautologies and equivalences
- Predicates and quantifiers
- Rules of inference
- Proof techniques
- Which proof technique should I try?
- Eight uses of logic in computing
Key points
- Propositions combine through connectives; the truth table decides equivalence, tautology or contradiction.
- Quantifiers extend logic to properties of many objects; negation swaps ∀ and ∃.
- Valid arguments chain inference rules; invalid ones commit fallacies.
- Proof techniques are templates; choose by the shape of the statement.
-
The syllabus asks for
- Sets and their operations
- Relations
- Functions
- Cardinality and countability
- Three kinds of function in one picture
- Eight uses of sets, relations and functions
Key points
- Sets and bit strings: union, intersection and complement are the logical operators applied to membership.
- Relations capture structure (equivalence → partitions, order → posets); closures add forced pairs.
- Functions classified as injective, surjective, bijective; counting uses powers, falling factorials and inclusion–exclusion.
- Cardinality separates countable from uncountable infinities, with consequences for computability.
-
The syllabus asks for
- The basic rules
- Permutations
- Combinations
- The binomial theorem
- Inclusion–exclusion and derangements
- The pigeonhole principle
- Counting and probability
- Pascal's triangle: all the binomial coefficients in one picture
- Eight uses of counting
Key points
- Product and sum rules solve most counting problems; subtract overlaps with inclusion–exclusion.
- Order matters → permutations; order does not → combinations; repetition changes the formula.
- The binomial theorem links combinations to powers and subsets.
- The pigeonhole principle proves existence without finding the object.
-
The syllabus asks for
- Mathematical induction
- Recursive definitions
- Linear recurrence relations
- Divide-and-conquer recurrences
- The recursion tree of merge sort
- Eight uses of induction and recursion
Key points
- Induction proves infinitely many statements with two finite checks; strong induction is the right tool when the step needs several earlier cases.
- Recursive definitions give structures and programs; structural induction proves their properties.
- Linear recurrences are solved through the characteristic equation; non-homogeneous ones add a particular solution.
- The master theorem gives the cost of divide-and-conquer algorithms at a glance.
-
The syllabus asks for
- Graph terminology
- Traversal, connectivity and Euler/Hamilton
- Planarity and colouring
- Weighted graphs: shortest paths and spanning trees
- Trees
- One graph, three answers
- Eight uses of graphs and trees
Key points
- Graphs are vertices and edges; degree, paths and connectivity answer structural questions, and the handshake lemma constrains degrees.
- Euler's theorem decides Euler circuits by degrees; Hamilton circuits have no simple test.
- Planarity and colouring have formulas and applications in scheduling.
- Dijkstra gives shortest paths and Kruskal/Prim give minimum spanning trees.
- Trees are acyclic connected graphs; traversals, search trees and Huffman codes are their main uses.
-
The syllabus asks for
- Divisibility, primes and gcd
- Modular arithmetic
- Applications
- Algebraic structures
- Lattices and Boolean algebra
- Clock arithmetic and the RSA message path
- Eight uses of number theory and algebraic structures
Key points
- The Euclidean algorithm computes gcds quickly and the extended version yields inverses.
- Modular arithmetic lets us compute with remainders; Fermat, Euler and the CRT are its workhorses.
- RSA turns the difficulty of factoring into public-key encryption.
- Groups, rings and fields classify structures by their axioms; Boolean algebras unify logic, sets and circuits.
No chapter matches. Try another word.
The paper
TU assessment: 60% final examination set by the university, 40% internal (assignments, lab work, attendance). Confirm the split in your college's notice.