mca Syllabus

Fourth Semester
COMPUTER SCIENCE

           
Mathematics
M 401
Contact: 3L + IT
Credit: 4

Sets and functions: Groups, Semigroups and monoids, Cyclic semigroups and submonoids, Subgroups and Cosets, Congruence relations on Semigroups. Morphisms, Normal subgroups. Structure of cyclic groups, permutation groups, dihedral groups. Elementary applications in coding theory.

Rings and Boolean algebra: Rings, Subrings, morphism of rings, ideals and quotient rings. Euclidean domains. Integral domains and fields. Boolean Algebra - direct product, Morphisms. Boolean sub-algebra. Boolean Rings. Applications of Boolean algebra in logic circuits and switching functions.

Recursion and Recurrence Relation: Basic idea, Sequence and discrete function. Generating functions and applications. Graph Thoery: Graphs, Digraphs, Isomorphism, Walks, Paths, Circuits, Shortest Path Problem, Dijkstra's Algorithm, Trees, Properties of Trees, Cotrees and Fundamental Circuits, Shortest Spanning Trees - Kruskal's Algorithm,Prim’s Algorithm,DFS,BFS, Cut Sets, Fundamental Cut Sets and Cut Vertices, Planar and Dual Graphs, Metric Representation of Graphs, Networks, Flow Augmenting Path, Ford-Fulkerson Algorithm for Maximum Flow.

Text:
1. Liu C. L., “Introduction to combinatorial mathematics”, McGraw Hill, 1968.
2 Mott J. L., Kandel A. and Baker T. P., “Discrete mathematics for Computer Scientists and Mathematicians”, PH, 1986.
3 Rosen—Discrete Mathematics, 2/e,TMH
4 S.K. Mapa—Higher Algebra (Abstract & Modern)
5 Robert J. McElice , Robert B. Ash & Carol Ash, “Introduction to discrete
Mathematics”, Tata McGraw Hill
6 Deo N., “Graph Theory with Applications to Engineering and Computer Science”, PHI, 1980
7 Tremblay and Manohar, “Discrete mathematical structures with applications to computer science”, McGraw Hill, 1975
8 Kolamn, Busby and Ross, “Discrete mathematical structures”, 3/ed, PHI, 1996.
9 Fraleigh J. B., “A first course in abstract algebra Narosa”, 1990
10 Smullyan R. M., “First Order Logic Springer Verlag”, 1968

Reference:
1.Lipschutz—2000 Solved Problems in Discrete Mathematics, TMH
2.Balakrishnan—Graph Theory (Schaum),MH
3.Hararay—Graph Theory