CS 3333. Mathematical Foundations of CS

This course introduces and reviews several mathematical and statistical tools that are useful in the design and analysis of computer algorithms and in the development of system performance models. Topics to be studied include

Prerequisites: CS 1713/1 Introduction to CS and MAT 1223 Calculus II.
Corequisite: Must enroll in CS 3331.

Instructor    Rajendra V. Boppana
    Office: Science Building 4.01.52    Phone: 210 458-5692   Email: boppana[at]cs.utsa.edu
    Office Hours: MW 2 - 3 pm or by appointment

TAs Pengjun Pan ppan[at]cs.utsa.edu Office hour: Tuesday 10-11 am in the CS Lab or by appointment
Jie Xiao jxiao[at]cs.utsa.edu Office hour: Monday 10-11 am in the CS Lab or by appointment

Required Textbooks
[KR] K. Rosen, Discrete Mathematics and Its Applications, 7th edition, McGraw-Hill, 2011.
[S3] Spiegel, Schiller and Srinivasan, Schaum's Outline of Probability and Statistics (Schaum's Outline Series), McGraw-Hill, 2008, 432 pages. ISBN-10: 0071544259.

Grading    15% Homeworks (about 9)
                    5     Quizzes (about 15; at the beginning of lectures) + Participation
                    40     Tests (2)
                    40     Final. May 11th, 1:30 pm

Student conduct and absence. No makeup exams or assignments are given. If you must miss an announced exam or an assignment deadline, you should inform the instructor in advance. No computers or cell phones may be used during the lectures and recitations. Students who do not want to participate in the recitations should submit a written note to the instructor so that their quiz credits will be used to substitute for participation credits. Any student who attends the recitations and engages in talking with other students, browsing the Web, using cell phones, or any other disruptive behavior will be disciplined.

You should do all assignments and homeworks on your own, without collaborations. Submission of homeworks with solutions copied from the assignments in prior semesters or other sources is academic dishonesty and will result in a failing grade for the course.

Week.Class#	Topic	Reference
1.2 -- 3.1 (1.1 is MLK holiday)	Introduction to the course. Integers: division, modular arithmetic, congruences; primes, greatest common divisors, number systems	Chapter 4 (except § 4.4) from [KR]
3.2 -- 5.1	Matrices and vectors: multiplication, transposes, determinants, inverse matrices Matrix analysis: linear equations, eigenvalues and eigenvectors	§ 2.6 from [KR], Notes
5.2	Review 1
6.1	Test 1
6.2 -- 8.2	Combinatorics: counting, pigeonhole principle, permutations, combinations.	§ 6.1-6.3 from [KR], Notes
Mar 12-16	Spring Break
9.1 -- 10.1	Combinatorics: binomial coefficients, binomial theorem, generalized permutations and combinations, principle of inclusion-exclusion.	§ 6.4-6.5 and § 8.5-8.6 from [KR], Notes
10.2	Review 2
11.1	Test 2
11.2 -- 14.1	Probability theory, Bayes' theorem, expectation and variance, random variables, distribution functions Probability: law of large numbers, central limit theorem, tail probability estimations	Chapters 1-3 from [S3] Chapter 6 from [KR] Notes
14.2 -- 15.1	Statistics: summarizing measured data, parameter estimation, confidence intervals, linear regression models	Chapters 5-6 from [S3], Notes
15.2	Review

Notation: x.y in the left column means the week number is x (varies 1 through 15) and the class number is y (1 for Monday and 2 for Wednesday). § denotes a section within a chapter. [KR] and [S3] refer to the textbooks indicated above.

UT San Antonio, Computer Science Department

CS 3333 Mathematical Foundations Spring '12