    Hi Guest, 18 October 2019 Friday IST             Home > Academic/Programmes > Programme Structure > CIS (2012)       CSC3101: MATHEMATICAL CONCEPTS FOR COMPUTER SCIENCE 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 REFERNCES 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                     