Discrete Mathematics Lectures: Rajendra Akerkar

Course Title: Discrete Mathematics

Number of Unites: 4

Schedule: Three hours of lecture and one hour of discussion per week.

Prerequisites: Programming in C

Catalog Description :
In this paper the concepts of prepositional and predicate logic, concise overview of set theory are introduced. This paper also includes functions, relations and classical concept of graph theory.

Expanded Description:
This course coveres the mathematical techniques related to computer science. Topics included: logic, relations, functions, basic set theory, countability and counting arguments, proof techniques, mathematical induction, graph theory, combinatorics, discrete probability, recursion, recurrence relations, and number theory. Emphasis will be placed on providing a context for the application of the mathematics within computer science. The analysis of algorithms requires the ability to count the number of operations in an algorithm. Recursive algorithms in particular depend on the solution to a recurrence equation, and a proof of correctness by mathematical induction. The design of a digital circuit requires the knowledge of Boolean algebra. Software engineering uses sets, graphs, trees and other data structures. Number theory is at the heart of secure messaging systems and cryptography. Logic is used in AI research in theorem proving and in database query systems. Proofs by induction and the more general notions of mathematical proof are ubiquitous in theory of computation, compiler design and formal grammars. Python programming will be used in the lab sessions.

The lectures will cover the following topics:

Unit-1: Mathematical Logic - statements and notation, connectives, Normal forms and Inference theory for the statement calculus. (07)
Unit-2: The predicate calculus, inference theory of predicate calculus, Automatic theorem proving. (06)
Unit-3: Set theory, Computer representation of sets. (06)
Unit-4: Induction and Recursion - Definitions and examples, applications too algorithm verification and Languages in the form of regular expressions and regular set. (06)
Unit-5: Graph terminology and representation. Elementary graph algorithms - DFS, BFS. Spanning tree - Kruskal & Prim's Algorithms. (07)
Unit-6: Shortest Path algorithms, Topological Sorting, Bipartite Graphs, Eularian and Hamiltonian Graphs. (06)
Unit-7: Relations and Ordering - Product sets and relations, representation of relations, equivalence relations, closure properties, Warshell’s algorithm, Computer representation of relations. (06)
Unit-8: Functions - Types of functions, function as relations, inverse of a function, pigeonhole principle and applications, permutations and their properties. (05)

Course Objectives & Role in the Program:

This is a special topics graduate course with a strong emphasis on applications. It will consist of lectures given by the instructor as well as presentations by students about their project and assignments.

Learning Outcomes:
Upon successful completion of this course student will:
- be able to do apply mathematical concepts,
- be familiar with terminology used in this topical area,
- have read and analyzed important historical and current trends addressing discrete mathematical structures.

Method of Evaluation

Final Exam

35%

Midterm

30%

Lab work

25%

Homework

10%

Homework will consist of written assignments (problem solving) and lab assignment consists of python programming problems. Each student has to submit a written assigments and also participate in the lab sessions. The midterm exam will be held in class at some point near the middle of the semester and final exam (written) will be conducted in the last week of the course. Class participation includes class attendance and active participation in the discussion of readings.

Required Books:

Discrete Mathematics, R. A. Akerkar and R. R. Akerkar (Pearson Education India)

Additionally, you may wish to refer to the following books:

Discrete Mathematics, Norman L. Biggs; (2nd edition, Oxford University Press, 2002); ISBN: 0198507178;

General Online Resources: