Hi Guest, 30 September 2020 Wednesday IST

About CUSAT | About Department | Alumni | Sitemap | Disclaimer  

     
 
  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