Module Code and Title:       MAT102          Discrete Mathematics

Programme:                          BCA

Credit Value:                         12

Module Tutor:                       Somnath Chaudhuri

General Objective: This module aims to introduce the basic concepts of mathematical logic and graphs that are necessary for students to engage in more sophisticated levels of software development in future semesters.

Learning Outcomes – On completion of the module, learners will be able to:

1. Solve set theory problems.
2. Solve mathematical induction and deduction problems.
3. Explain the use of various connectives in a statement.
4. State whether a given statement is a tautology or contradiction.
5. Identify different types of normal forms.
6. Find the shortest path between two nodes of a weighted graph.
7. Identify Eulerian and Hamiltonian paths in a given graph.
8. Solve problems related to trees and cut sets.

Learning and Teaching Approach:

Assessment Approach:

A. Individual Assignment: Portion of Final Mark: 10%

Students should submit two assignments related to set theory and graph theory to obtain this 10%. The first one will be before the midterm and constitutes half of the total 10% allocated. Students will be submitting an assignment based on set theory. The second assignment will be done after the midterm, covering topics from graph theory and trees. Three-four numerical problems will be assigned to them to solve. 40% will be awarded for solving the problem, 40% for analysing the problem and 20% for the overall report.

Activity: Problems will be assigned to students related to set theory and graph theory to analyse and solve. Solutions should be submitted in hardcopy format with proper logical expressions.

B. Class Test: Portion of Final Mark: 20%

This is a written test conducted within the class for duration of 30-40 minutes. There will two such tests, one before midterm comprising of topics from the beginning to the quarter point of the subject matter and the other after the midterm comprising of topics from after the midterm to quarter pointer after midterm. Each class test will consist of 3-4 numerical problems. The students have to solve those problems in the class within predefined time.

C. Individual Presentation: Portion of Final Mark: 5%

The presentation will be conducted within the class hours. Students are expected present the topic assigned to them respectively. The duration of each individual presentation will be 10-12 minutes, and include power points slides. 30% will be awarded for content of the presentation, 30% for preparedness, 10% for timing, 15% for handling of Q&A session and 15% for presentation skill.

Activity: A few topics will be taught in the class. Then, when students have adequately grasped the concept of the topic, they have to prepare a presentation on its real-time application. Topics will be on graph theory and trees. The presentation will be evaluated by the contents of the presentation and individual presentation skill.

D. Class Participation: Portion of Final Mark: 5%

This component assesses the student’s overall performance in class throughout the semester. This portion is awarded for the active participation in class activities like discussion and question-answer sessions.

Activity: Questions based on previous class are asked to the whole class at the beginning of every lecture session. Students who give answers are marked (similarly discussion participation is also marked), and these are counted at the end of the semester to assign class participation marks for every student.

E. Midterm Exam: Portion of the Final Mark: 20%

This a college wide examination conducted at the half-way into the semester. This examination is conducted for 1 hour and 30 Minutes and it includes all topics till the half-way point in the subject matter.

Prerequisites: MAT101

Subject Matter:

1. Set theory
   • Introduction to sets
   • Sets and Venn diagrams
   • Intervals
   • Common number sets
   • Closure
   • Real number properties
2. Mathematical Reasoning
   • Introduction
   • Mathematical induction
   • Mathematical deduction
3. Mathematical logic
   • Introduction to mathematical logic
   • Statements and notations
   • Connectives
   • Normal forms
   • Theory of inference for the statement calculus
   • The Predicate calculus
   • Inference theory of the Predicate calculus
4. Graph Theory
   • Basic terminology
   • Multi graphs
   • Weighted graphs
   • Paths and circuits
   • Shortest paths in weighted graphs
   • Eulerian and Hamiltonian paths and circuits
   • The traveling salesman problem
   • Factors of a graph and Planar graphs
5. Trees
   • Introduction to Trees
   • Rooted trees
   • Path lengths in rooted trees
   • Prefix codes
   • Binary search trees
   • Spanning trees and cut trees
   • Minimum spanning trees and transport networks.

Reading List:

1. Essential Reading
   • Trembly, J. P. & Manohar, R. (2005), Discrete Mathematical Structures with Applications to Computer Science, 23^rd reprint, Tata McGraw Hill Edition, New Delhi
   • Liu, C. L. (2005), Elements of Discrete Mathematics, Second Edition, 4^th reprint, Tata McGraw Hill, New Delhi
   • Introduction to Graph Theory (2nd ed.). (2002). PHI.
   • Halmo, P. (2009). Naive Set Theory. Springer.
2. Additional Reading
   • Bonday, J.A., and Morthy, U.S.R., (2003), Graph theory with Applications, Mac Millan Press
   • Cormen, T. H., Leiserson, C. E., Rivest, R. L. (2002), Introduction to Algorithms, (7^th Indian reprint). Prentice Hall of India Private limited, New Delhi
   • Rosen, K. H. (2007), Discrete Mathematics and its Applications, (6^th Edition). Tata Mc Graw Hill Companies
   • Albertson, M. O. & Hutchinson, J. P. (2006), Discrete Mathematics with Algorithms. John Wiley and Sons
   • Kenneth H. Rosen, Discrete Mathematics and Its Application, McGraw-Hill Science/Engineering/Math; 5 edition
   • K. Balakrishnan. (1991), Introductory Discrete Mathematics, Courier Corporation

Date: May 30, 2015