Hi Guest, 30 September 2020 Wednesday IST

About CUSAT | About Department | Alumni | Sitemap | Disclaimer  

     
 
  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