Hi Guest, 30 September 2020 Wednesday IST

Home > Academic/Programmes > Programme Structure > SE (2015)

 CSS3101: MATHEMATICAL CONCEPTS FOR COMPUTER SCIENCE Core/Elective: Core Semester: 1 Credits: 4 Course Description To understand any Computer Science topic deeply enough, it is essential to have a firm foundation of the underlying mathematics. This course introduces the mathematical concepts which form the prerequisite for a study of advanced Computer Science. A major emphasis of the course would be to develop the students problem solving skills Course Objectives To get a firm foundation of the mathematical foundations of computer science. To hone problem solving skills in computer science. Course Content 1. Introduction  proofs  propositions  predicates and quantifiers  truth tables  first order logic  satis fiability  pattern of proof  proofs by cases  proof of an implication  proof by contradiction  proving iff  sets  proving set equations  russells paradox  well-ordering principle  induction  invariants  strong induction  structural induction  pigion hole principle  parity  number theory  divisibility  gcd  euclids algorithm  primes 2. Graph theory  simple graphs  isomorphism  subgraphs  weighted graphs  matching problems  stable marriage problem  graph coloring  paths and walks  shortest paths  connectivity  Eulerian and Hamiltonian tours  travelling salesman problem  trees  spanning trees  planar graphs  Eulers formula  directed graphs  strong connectivity  relations  binary relations  surjective and injective relations symmetry, transitivity, reflexivity, equivalence of relations  posets and dags  topological sort 3. Sums and asymptotics  arithmetic, geometric and power sums  approximating sums  harmonic sums  products  stirlings approximation for finding factorial  asymptotic notations  recurrences  towers of Hanoi  solving recurrences  master theorem  linear recurrences  infinite sets  countable and uncountable sets  cantors continuum hypothesis 4. Finite automata  regular expressions  pushdown automata  context free grammar  pumping lemmas  Turing machines  Church-Turing thesis  decidability  halting problem  reducibility  recursion theorem  time and space measures  complexity classes  NP  reductions 5. Probability  events and probability spaces  conditional probability  tree diagrams for computing probability  sum and product rules of probability  A posteriori probabilities  identities of conditional probability  independence  mutual independence  birthday paradox  random variables  indicator random variables  probability distribution functions  Bernoulli, Uniform, Binomial distributions  Expectation  linearity of expectations  sums of indicator random variables  expectation of products  variance and standard deviation of random variables  Markovs and Chebyshevs theorems  Bounds for the sums of random variables  random walks REFERNCES [1] Eric Lehman, F Thomson Leighton, Albert R Meyer, Mathematics for Computer Science, MIT, 2010 [2] Susanna S. Epp, Discrete Mathematics with Applications, 4th Edition, Brooks Cole, 2010 [3] Gary Chartrand, Ping Zhang, A First Course in Graph Theory, Dover Publications, 2012 [4] Michael Sipser, Introduction to Theory of Computation, 2nd Edition, Cengage, 2012

 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