    Hi Guest, 30 September 2020 Wednesday IST             Home > Academic/Programmes > Programme Structure > CIS (2009)       CSC3101: DISCRETE STRUCTURES & GRAPH THEORY Core/Elective: Core Semester: 1 Credits: 4 Course Description Discrete mathematics is the study of mathematical structures that are fundamentally discrete in nature. It is concerned with techniques to solve certain types of problems such as how to count or to enumerate quantities .The course is intended to cover the main aspects which are useful in studying, describing and modelling of objects and problems in the context of computer algorithms and programming languages Course Objectives To study the basic set theory To familiarise different mathematical structures To study the different properties of graphs To study the basic search algorithms to find the shortest path To familiarise the mathematical modelling of networks. Profile 1. Sets, sub-sets & operations on sets – Finite and infinite sets – Relations & Properties of relations – equivalence relation - Groups- Rings and Fields. 2. Partial order relation, Poset, hub, glb, maximal and minimal elements of a poset – Definition & example of Boolean algebra – Lattices, Distributive laws in lattices – Complemented lattices – Propositional Calculus – Boolean functions, minimum & maximum terms, simplification of Boolean function with Karnaugh map & Quiane Mc Clusky method 3. Basic theorems on permutations & combinations – Pigeon hole principle, principle of inclusion and exclusion – Ordinary and exponential generating functions – Recurrence equations 4. Basic definitions of Graphs, connectivity of a graph, cut points, cycles – Hamiltonian graphs – sub graphs - spanning sub graphs - isomorphic graphs - matrix representation of graphs, Fusion - fusion algorithm, Bipartite graphs, Tree, different characterization of trees Algorithms on graphs – Breadth First Search and Depth First Search, Dijkstra’s algorithm for shortest path, Floyd’s algorithm for all pairs of shortest paths, Kruskal’s and Prim’s algorithm for minimum spanning tree 5. Graph coloring and chromatic polynomials-network flows-maxflow-min cut theorem, Ford and Fulkerson algorithm, separating sets, Basic concepts of Median graphs REFERNCES 1. Discrete Computational Structures (2nd Ed): Robert R. Korfhage , Academic Press (1984) 2. Rings, Fields and Groups: An Introduction to Abstract Algebra (2nd Ed): Reg Allenby (1999) 3. Elements of Discrete Mathematics (1st Ed): L CL Liu, McGraw-Hill (1985) 4. Discrete Mathematical Structures for Computer Science (1st Ed): Bernard Kolman, Robert Busby, PHI (1987) 5. First look at graph theory (1st Ed): John Clark & Derek Allan Holton, Allied Publishers (1995) 6. Graph Theory with Applications to Engineering & Computer Science: Narsingh Deo, PHI (2004)     Copyright © 2009-20 Department of Computer Science,CUSAT Design,Hosted and Maintained by Department of Computer Science Cochin University of Science & Technology Cochin-682022, Kerala, India E-mail: csdir@cusat.ac.in Phone: +91-484-2577126 Fax: +91-484-2576368                     