Syllabus Of Discrete Structure

on
Course Title: Discrete Structure
Course no: CSC-152 Full Marks: 90+10
Credit hours: 3 Pass Marks: 36+4

Nature of course: Theory (3 Hrs.)

Course Synopsis: This course contains the fundamental concepts of logic, reasoning  and algorithms.

Goal: After completing this course, the target student will gain knowledge in discrete  mathematics and finite state automata in an algorithmic approach. It helps the  target student in gaining fundamental and conceptual clarity in the area of Logic,  Reasoning, Algorithms, Recurrence Relation, and Graph Theory.

Course Contents:
Unit 1. Logic, Induction and Reasoning 12 Hrs.
Proposition and Truth function, Propositional Logic, Expressing statements in Logic  Propositional Logic, The predicate Logic, Validity, Informal Deduction in Predicate  Logic, Rules of Inference and Proofs, Informal Proofs and Formal Proofs, Elementary  Induction, Complete Induction, Methods of Tableaux, Consistency and Completeness  of the System.

Unit 2. Finite State Automata 10 Hrs.
Sequential Circuits and Finite state Machine, Finite State Automata, Language and  Grammars, Non-deterministic Finite State Automata, Language and Automata,  Regular Expression.

Unit 3. Recurrence Relations 8 Hrs.
Recursive Definition of Sequences, Solution of Linear recurrence relations, Solution  to Nonlinear Recurrence Relations, Application to Algorithm Analysis. Combinatory,  Partial Order relation.

Unit 4. Graph Theory 15 Hrs.
Undirected and Directed Graphs, Walk Paths, Circuits, Components, Connectedness  Algorithm, Shortest Path Algorithm, Bipartite Graphs, Planar Graphs, Regular  Graphs, Planarity Testing Algorithms, Eulerian Graph, Hamiltonian Graph, Tree as a  Directed Graph, Binary Tree, Spanning Tree, Cutsets and Cutvertices, Network Flows, Max-flow and Min-cut Theorem, Data Structures Representing Trees and Graphs in Computer, Network Application of Trees and Graphs, Concept of Graph  Coloring.

Text / Reference books:
  1. Kenth Rosen, Discrete Mathematical Structures with Applications to Compute Science, WCB/ McGraw Hill
  2. G. Birkhoff, T.C. Bartee, Modern Applied Algebra, CBS Publishers.
  3. R. Johnsonbaugh, Discrete Mathematics, Prentice Hall Inc.
  4. G.Chartand, B.R.Oller Mann, Applied and Algorithmic Graph Theory, McGraw Hill
  5. Joe L. Mott, Abrahan Kandel, and Theodore P. Baker, Discrete Mathematics for Computer Scientists and Mathematicians, Prentice-Hall of India

Comments

Post a Comment