

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
covers 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:
 Unit1:
Mathematical Logic 
statements and notation,
connectives, Normal
forms and Inference
theory for the statement
calculus.
(07)
 Unit2:
The predicate calculus,
inference theory of
predicate calculus,
Automatic theorem
proving. (06)
 Unit3:
Set theory, Computer
representation of
sets. (06)
 Unit4:
Induction and Recursion
 Definitions and
examples, applications
too algorithm
verification and
Languages in the
form of regular
expressions and regular
set. (06)
 Unit5:
Graph terminology and
representation.
Elementary graph
algorithms  DFS, BFS.
Spanning tree  Kruskal
&
Prim's Algorithms.
(07)
 Unit6:
Shortest Path
algorithms, Topological
Sorting, Bipartite
Graphs, Eularian and
Hamiltonian
Graphs. (06)
 Unit7:
Relations and Ordering 
Product sets and
relations,
representation of
relations, equivalence
relations, closure
properties, Warshell’s
algorithm, Computer
representation of
relations.
(06)
 Unit8:
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:
 Math Forum@Drexel (http://mathforum.org/discrete/discrete.html)
 Algebraic,
Scientiﬁc, and Statistical
Computing, an Open Source
Approach Using Sage
 A
short course in Discrete
Mathematics by Bender and
Williamson
 Python
Programming
www.python.org
 Python
overview (Professor Deepak
Kumar)
© 2005
14
Technomathematics
Research Foundation


foo
