    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  Eric Lehman, F Thomson Leighton, Albert R Meyer, Mathematics for Computer Science, MIT, 2010  Susanna S. Epp, Discrete Mathematics with Applications, 4th Edition, Brooks Cole, 2010  Gary Chartrand, Ping Zhang, A First Course in Graph Theory, Dover Publications, 2012  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                     