Hi Guest, 18 July 2019 Thursday IST

About CUSAT | About Department | Alumni | Sitemap | Disclaimer  

  Home > Academic/Programmes > Programme Structure > CIS (2012)
Core/Elective: Core Semester: 1 Credits: 4
Course Description

This course introduces the study of mathematical structures that are fundamentally discrete in nature. It introduces linear algebra, logic, computability, graph theory and probability. 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 understand vectors and matrices
To study mathematical logic
To study detailed models of computability
To study graph theory and its applications
To understand application of probability

Course Content

1. Linear Algebra: Vector spaces, Orthogonality, Eigen-value analysis, Vector and matrix norms, Multivariable analysis, Vector and matrix calculus, Unconstrained and constrained optimization problem solving methods.

2. Logic: Propositional logic, Truth tables, Tautologies, Resolution proof system, Predicate logic, Temporal logic

3. Computability: Turing Machines, Recursive and Recursively Enumerable languages, Decidability, Resource bounded computation, Complexity classes, Complexity measures, Relationships among complexity measures, Polynomial time and space, Theory of NP-completeness

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, Bipartite graphs, Tree, different characterization of trees - Algorithms on graphs – BFS, DFS 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. 5. Random Variables and Stochastic Processes: Random variables, Functions of random variables, Sequences of random variables, Stochastic processes, Markov chains, Markov processes and queuing theory


1. Discrete Mathematical Structures for Computer Science (1st Ed): Bernard Kolman, Robert Busby, PHI (1984)
2. Linear Algebra and Probability for Computer Science Applications (1st Ed): Ernest Davis, CRC Press (2012)
3. Graph Theory and Its Applications (2nd Ed): Jonathan L. Gross and Jay Yellen, CRC (2005)
4. Schaum's Outline of Probability, Random Variables, and Random Processes (2nd Ed) : Hwei Hsu, McGraw-Hill (2010)

Copyright © 2009-19 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