27 January 2012

DISCRETE STRUCTURES FOR COMPUTER SCIENCE - Topics


Course Description :

Introduction to discrete mathematical structures; Formal logic and predicate calculus; Sets, relations and functions; Proof techniques; Graphs and trees; Primes, factorization, greatest common divisor, residues and application to cryptology; Boolean algebra; Permutations, combinations and partitions; Recurrence relations and generating functions; Introduction to error-correcting codes; Formal languages and grammars, finite state machines.

Textbook :

T1.      Kolman, Busby, Ross and Rehman, Discrete Mathematical Structures for Computer Science, Pearson Education, 5th Edition, 2003.

Topics :


Week No.
Topics
Reference to
Text Book
1
Sets, Operations on sets, Sequences, Matrices
T1-Ch.1
2
Propositions, Conditional statements, Induction
T1-Ch.2
3
Pigeonhole Principle, Recurrence Relations
T1-Ch. 3.3, 3.5
4
Relations and Digraphs, Paths in Relations, Equivalence Relations
T1-Ch. 4.2 - 4.5
5
Operations on Relations, Transitive closure
T1-Ch. 4.7 – 4.8
6
Functions, Function for Computer Science Permutation functions
T1-Ch. 5.1,5.2,5.4
7
Partially ordered sets, Lattices, Boolean Algebras
T1-Ch.6.1, 6.3, 6.4
8
Review and Problem Solving

Syllabus for Mid-Semester Test: Topics covered in the first eight weeks
9
Graphs, Euler Paths, Hamilton Paths
T1-Ch 8.1 – 8.3
10
Trees, Labeled Trees
T1-Ch.7.1, 7.2
11
Tree Searching, Undirected Trees
T1-Ch. 7.3, 7.4
12 – 13
Minimal Spanning Trees
T1-Ch. 7.5
14
Semi groups, Products and Quotients of Semi groups
T1-Ch.9.1, 9.2
15
Groups, Products and Quotients of Groups
T1-Ch.9.3, 9.4
16
Review and Problem Solving

Syllabus for Comprehensive Exam (Open Book) All topics given in Plan 


 
Reference Books :

R1.     D.S. Malik and M.K. Sen, Discrete Mathematical Structures: Theory and Applications, Thomson, 2004.
R2.     Goodaire & Parmenter : Discrete Mathematics & Graph Theory, Pearson Education, 2000.
R3.     Kenneth H. Rosen, Discrete Mathematics and its Applications, Tata McGraw Hill, 5th Ed., 2004.
R4.     C.L. Liu, Elements of Discrete Mathematics, 2nd Edition, McGraw Hill, 1986.

0 comments:

Post a Comment