MCA-101
Discrete Structures
The mathematics the rest of the degree is built on — sets and relations, logic and proof, number theory, groups and graphs.
- Semester
- Semester 1
- Credits
- 4
- Scheme
- 3 lectures + 1 tutorial a week
- Contact hours
- 44 across four units
- Category
- Core
What the paper is
Discrete Structures is the paper that makes the others possible. Almost nothing here is studied for its own sake: relations and functions are what a database schema is, Boolean algebra is what a circuit and an SQL WHERE clause both reduce to, recurrence relations are how you get a running time out of a recursive algorithm, and graphs are the shape of every network, dependency and route problem you will meet later.
It is also the paper most likely to be a shock if your degree so far was practical. There is no code in it. The unit of work is a proof, and the skill being examined is whether you can state a claim precisely and argue it without hand-waving — which is why the syllabus spends a whole unit on methods of proof before it uses them.
It carries four credits and a tutorial hour, one of only two first-semester papers to do so. That tutorial is not padding; it is where the problem sets get worked, and it is the difference between recognising a technique and being able to apply it under exam conditions.
What to concentrate on
- Unit II is the one that pays off everywhere else. Get comfortable with normal forms, induction and the K-map before the exam is close, because Unit III's number theory and Unit IV's graph proofs both assume you can write an argument cleanly.
- Graph theory is the largest single block of marks in most papers and the most self-contained — Euler and Hamiltonian conditions, planarity with Euler's formula, and colouring with Welch-Powell are reliably examinable and can be revised late if they have to be.
- Number theory reappears in semester 3 under Applied Cryptography: congruences, Euler's phi function and Fermat's little theorem are the whole basis of RSA. Learning them properly once saves learning them twice.
Syllabus, unit by unit
Summarised from the approved scheme. Hours are the contact hours the scheme allots, which is a fair guide to where the marks sit.
Unit I · Set theory, combinatorics and recurrences
11 hours- Sets, subsets, power set, multi-sets, operations and algebra of sets, inclusion–exclusion
- Cartesian product, relations and their types, equivalence and partial order relations, closure
- Functions: one-one, many-one, onto, composition, invertible functions
- Combinatorics: permutations, combinations, combinations with unlimited repetition, pigeonhole principle
- Recurrence relations: linear first-order with constant coefficients, homogeneous and non-homogeneous
Unit II · Logic, proof, lattices and Boolean algebra
12 hours- Formal logic: statements, tautologies, fallacies, logical equivalence, algebra of propositions, rules of inference, normal forms
- Methods of proof: direct, indirect, contradiction, exhaustive cases, mathematical and complete induction
- Lattices: posets, sublattices, bounded, distributive and complemented lattices, isomorphic lattices
- Boolean algebra: subalgebra, Boolean functions and expressions, minimisation, K-maps
Unit III · Number theory and group theory
11 hours- Primes, division algorithm, GCD and LCM, Euclidean algorithm, fundamental theorem of arithmetic
- Congruences, linear congruence equations, Chinese remainder theorem, Euler phi function, Fermat's little theorem
- Applications of congruences — ISBN, UPC — and an introduction to cryptography
- Group theory: subgroups, cosets, cyclic and normal subgroups, quotient groups, Lagrange's theorem, homomorphism, permutation groups
Unit IV · Graph theory
10 hours- Graphs and their types, degree of a vertex, subgraphs, isomorphism, representation and operations
- Walks and paths, connectivity, weighted graphs, Euler graphs and Fleury's algorithm, Hamiltonian graphs
- Cut-vertices and cut-edges, planar graphs and Euler's formula
- Graph colouring: vertex and edge colouring, chromatic number and polynomial, Welch-Powell algorithm, four colour conjecture, five colour theorem with proof
How it is examined
- Question 1 is compulsory, covers the whole syllabus, and is made of objective or short-answer questions. It carries 12 marks.
- The rest of the paper is four units matching the four above. Each unit sets two questions and you attempt one, so there are four more answers at 12 marks each.
- Examiners are asked to map every question to a course outcome using Bloom's taxonomy, which is why questions are phrased as “apply”, “analyse” or “evaluate” rather than only “explain”.
The pass mark is 40 out of 100 in every paper.
Learning objectives
- Familiarisation with basic mathematical structures and combinatorics
- Understanding and applying mathematical logic and Boolean algebra
- Understanding and applying number theory and elementary group theory
- Constructing and applying graphs to computer science problems
Assumed beforehand
- Basic knowledge of mathematics
Books it is taught from
- TB1Kenneth H. Rosen, “Discrete Mathematics & its Applications: With Combinatorics and Graph Theory”, McGraw Hill, 7th edition, 2017
- TB2J. P. Tremblay and R. Manohar, “Discrete Mathematical Structures with Applications to Computer Science”, McGraw Hill, 1st edition, 2001
- TB3Swapan Kumar Sarkar, “A Textbook of Discrete Mathematics”, S. Chand, 9th edition, 2019
Notes for MCA-101
Lecture notes, question papers and assignments filed against MCA-101 are in the library. Everything there has been checked by a moderator before it appears, and an account is free — new ones are approved by hand, which is what keeps the shelf clean.