JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY: KAKINADA KAKINADA - 533 003, Andhra Pradesh, India L T [Pp Ic 3 0 0 13 Mathematical Foundations of Computer Science (MTCSEI101) 1 Year - I Semester Course Objectives: This course is aimed at enabling the students to + To understand the mathematical fundamentals that is prerequisites for variety of courses like Data mining, Network protocols, analysis of Web traffic, Computer security, Software engineering, Computer architecture, operating systems, distributed systems bioinformatics, Machine learning. * To develop the understanding of the mathematical and logical basis to many modern techniques in computer science technology like machine learning, programming language design, and concurrency. + To study various sampling and classification problems. Course Outcomes: After the completion of the course, student will be able to ‘© To apply the basic rules and theorems of probability theory such as Baye’s Theorem, to determine probabilities that help to solve engineering problems and to determine the expectation and variance of arandom variable from its distribution. ‘Able to perform and analyze of sampling, means, proportions, variances and estimates the maximum likelihood based on population parameters. * To learn how to formulate and test hypotheses about sample means, variances and proportions and to draw conclusions based on the results of statistical tests. ‘+ Design various ciphers using number theory. + Apply graph theory for real time problems like network routing problem, UNIT I: Basic Probability and Random Variables: Random Experiments, Sample Spaces Events, the Concept of Probability the Axioms of Probability, Some Important Theorems on Probability Assignment of Probabilities, Conditional Probability Theorems on Conditional Probability, Independent Events, Bayes Theorem or Rule, Random Variables, Discrete Probability Distributions, Distribution Functions for Random Variables, Distribution Functions for Discrete Random Variables, Continuous Random Variables UNIT I: Sampling and Estimation Theory: Population and Sample, Statistical Inference Sampling With and Without Replacement Random Samples, Random Numbers Population Parameters Sample Statistics Sampling Distributions, Frequency Distributions, Relative Frequency Distributions, Computation of Mean, Variance, and Moments for Grouped Data. Unbiased Estimates and Efficient Estimates Point Estimates and Interval Estimates. Reliability Confidence Interval Estimates of Population Parameters, Maximum Likelihood Estimates UNIT IM: Tests of Hypothesis and Significance: Statistical Decisions Statistical Hypotheses. Null Hypotheses Tests of Hypotheses and Significance Type I and Type II Errors Level of Significance Tests Involving the Normal Distribution One-Tailed and Two-Tailed Tests P Value Special Tests of Significance for Large Samples Special Tests of Significance for Small Samples Relationship between Estimation Theory and Hypothesis Testing Operating Characteristic Curves. Power of a Test Quality Control Charts Fitting Theoretical Distributions to Sample Frequency Distributions, The Chi-Square Test for Goodness of Fit Contingency Tables Yates’ Correction for Continuity Coefficient of Contingency. UNIT IV: Algebraic Structures and Number Theory: Algebraic Systems, Examples, General Properties, Semi Groups and Monoids, Homomorphism of Semi Groups and Monoids, Group, Subgroup,JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY: KAKINADA KAKINADA - 533 003, Andhra Pradesh, India Abelian Group, Homomorphism, Isomorphism. Properties of Integers, Division Theorem, The Greatest Common Divisor, Euclidean Algorithm, Least Common Multiple, Testing for Prime Numbers, The Fundamental Theorem of Arithmetic, Modular Arithmetic (Fermat's Theorem and Euler's Theorem) UNIT V: Graph Theory: Basic Concepts of Graphs, Sub graphs, Matrix Representation of Graphs: Adjaceney Matrices, Incidence Matrices, Isomorphie Graphs, Paths and Circuits, Eulerian and Hamiltonian Graphs, Multigraphs, Planar Graphs, Euler’s Formula, Graph Colouring and Covering, Chromatic Number, Spanning Trees, Algorithms for Spanning Trees (Problems Only and Theorems withouf Proof). Text Books: 1, Foundation Mathematics for Computer Science, John Vince, Springer. 2. Probability & Statistics, 3rd Edition, Murray R. Spiegel, John J. Schiller and R. Alu Srinivasan, Schaum's Outline Series, Tata McGraw-Hill Publishers 3. Probability and Statistics with Reliability, K. Trivedi, Wiley. 4, Discrete Mathematics and its Applications with Combinatorics and Graph Theory, 7" Edition, H. Rosen, Tata McGraw Hill. Reference Books: 1. Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher and E. Upfal. 2. Applied Combinatorics, Alan Tucker, Wiley.