Class timing: Slot D (Mo 11:30-12:25, Tu 09:30-11:25, Th 07:30-08:25)
Class room: CSE 119
Instructor: Abhijit Das
Teaching assistants: Dipankar Das and Soumyajit Dey
Syntax, semantics, valid, satisfiable and unsatisfiable
formulas, encoding and examining the validity of some logical arguments.
Forward proof, proof by contradiction, contrapositive proofs,
proof of necessity and sufficiency.
Operations on sets, relations and functions, binary relations,
partial ordering relations, equivalence relations, principles of mathematical induction.
|Size of a set
Finite and infinite sets, countable and uncountable sets,
Cantor's diagonal argument and the power set theorem, Schröder-Bernstein theorem.
Basic counting techniques: inclusion and exclusion,
pigeon-hole principle, permutation, combination, summations. Introduction to recurrence
relations and generating functions.
Algebraic structures with one binary operation -
semigroups, monoids and groups, congruence relation and quotient structures.
Free and cyclic monoids and groups, permutation groups, substructures, normal
subgroups. Algebraic structures with two binary operations - rings, integral
domains and fields. Boolean algebra and Boolean ring.
|Graphs and trees
Graphs and their basic properties - degree, path, cycle,
subgraphs, isomorphism, Eulerian and Hamiltonian walks, graph coloring, planar graphs,
I plan to follow the following as the main text-book. More precisely, Chapters 1-6,
8 and 9 of this book would be covered. Admittedly, this book does not provide a
satisfactory treatment of every topic in the official syllabus. But its coverage
is quite decent, and the book is low-priced and handy.
Bernard Kolman, Robert C Busby, and Sharon Cutler Ross,
Mathematical Structures, fifth edition, Prentice-Hall of India.
Some other books that can be used as references are:
Ralph P Grimaldi, Discrete and Combinatorial Mathematics,
Pearson Education Asia.
Norman L Biggs, Discrete Mathematics, Oxford University Press.
Kenneth H Rosen, Discrete Mathematics and its Applications,
C L Liu, Elements of Discrete Mathematics, Tata McGraw-Hill.
J P Tremblay and R Manohar, Discrete mathematical structures with
applications to Computer Science, Tata McGraw-Hill.
Also look at the course page for Autumn 2005.
Class Test 1 (Sep 12, 2006): Questions | Solutions
Mid-Semester Test (Sep 15, 2006): Questions | Solutions
Class Test 2 (Nov 15, 2006): Questions | Solutions
End-Semester Test (Nov 20, 2006): Questions | Solutions