Course schedule
Syllabus
References
Tutorial exercises
Tests
|
Course schedule
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
Syllabus
| Propositional logic |
Syntax, semantics, valid, satisfiable and unsatisfiable
formulas, encoding and examining the validity of some logical arguments.
| | Proof techniques |
Forward proof, proof by contradiction, contrapositive proofs,
proof of necessity and sufficiency.
| Sets, relations
and functions |
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.
| | Combinatorics |
Basic counting techniques: inclusion and exclusion,
pigeon-hole principle, permutation, combination, summations. Introduction to recurrence
relations and generating functions.
| Algebraic structures
and morphisms |
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,
trees.
|
References
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,
Discrete
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,
Tata McGraw-Hill.
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.
Tutorial exercises
Tests
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
|