SPPU · Second Year Computer Engineering · 2024 Pattern (Revised)
Discrete Mathematics
PCC-252-COM · Semester IV · 3 credits · CCE 40 + end-semester 60
Unit 1: Set and Propositions
9 hoursPropositional logic and equivalences, translating English sentences, mathematical and strong induction; naïve and axiomatic set theory, set operations, cardinality, inclusion–exclusion, countable and uncountable sets, power sets.
Marks: 12 in the end-semester exam · CCE: Unit test (15 marks, Units 1 & 2)
Unit 2: Relations and Functions
9 hoursProperties and representations of relations, equivalence relations, partial orders, partitions, Hasse diagrams, lattices, transitive closure and Warshall's algorithm; injective, surjective and bijective functions, composition, inverse and recursive functions.
Marks: 12 in the end-semester exam · CCE: Unit test (15 marks, Units 1 & 2)
Unit 3: Introduction to Trees
9 hoursProperties of trees, decision trees, prefix codes and Huffman coding, cut sets, the max-flow min-cut theorem, Prim's and Kruskal's algorithms.
Marks: 12 in the end-semester exam · CCE: Assignments or case study (15 marks, Units 3 & 4)
- Trees and their properties
- Prefix codes and Huffman coding
- Cut sets and the max-flow min-cut theorem
- Minimum spanning trees
Unit 4: Introduction to Graph Theory
9 hoursGraph terminology and special graphs, representation and isomorphism, connectivity, Euler and Hamilton paths, the handshaking lemma, Dijkstra's algorithm, planar graphs and colouring.
Marks: 12 in the end-semester exam · CCE: Assignments or case study (15 marks, Units 3 & 4)
- Graph terminology and special graphs
- Graph representation and isomorphism
- Euler and Hamilton paths
- Dijkstra's shortest-path algorithm
- Planar graphs and graph colouring
Unit 5: Counting Principles and Algebraic Structures
9 hoursAddition and multiplication principles, permutations and combinations, binomial coefficients, pigeonhole and inclusion–exclusion principles, generating functions; semigroups, monoids, groups, homomorphisms, rings, integral domains and fields.
Marks: 12 in the end-semester exam · CCE: Seminar, open-book test or quiz (10 marks, Unit 5)
Unit contents are summarised from the official SPPU syllabus . AiCanCode.org is not affiliated with Savitribai Phule Pune University.