UT San Antonio, Computer Science Department

CS 3333 Mathematical Foundations        Fall '08

Survey and development of mathematical and statistical tools suitable for describing algorithmic applications. Vectors, matrices, combinatorics, probability and statistical models. Topics to be studied include

  • Integers (modular arithmetic, GCD, prime numbers, number systems)
  • Matrices (multiplication, transpose, determinants, binary)
  • Matrix Analysis (linear equations, eigenvalues and eigenvectors)
  • Combinatorics (pigeonhole principle, permuations, combinations, binomial theorem)
  • Probability (Bayes' theorem, random variables, expectation and variance)
  • Statistics (summarizing measured data, parameter estimation, confidence intervals)

Prerequisites

CS 1713/1 Introduction to CS and MAT 1223 Calculus II. 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: TR 11 am - 12 noon

TA
Boyu Zhang
Office Hours: 3-4 pm. Location: TBA.     Contact Information: TBA

Lectures

TR 12:30 pm, HSS 3.03.18

Recitation

CS 3331-001 MS 2.01.06 Tue 2 pm
CS 3331-002 HSS 3.03.20 Thu 2 pm

Textbooks

Required
[SB] Stroud and Booth, Engineering Mathematics, 6th edition, Palgrave MacMillan, 2007.
[KR] K. Rosen, Discrete Mathematics and Its Applications, 6th edition, McGraw-Hill, 2007.

Recommended
[VB] V. Balakrishnan, Combinatorics (Schaum's Outline Series), McGraw-Hill, 1995.
[S3]  Spiegel, Schiller and Srinivasan, Probability and Statistics (Schaum's Outline Series), McGraw-Hill, 2008.

Grading

25%  Homeworks and quizzes
35     Tests (2)
40     Final. Dec. 10th 10:30 AM

No makeup exams or assignments are given. If you must miss an announced exam or an assignment deadline, you should let me know in advance. Depending on class participation and progress, pop quizzes may be given. Unless otherwise specified, you should do all assignments and homeworks without collaborations.

Handouts        Available at http://www.cs.utsa.edu/faculty/boppana/3333

Number theory: Lecture 1

Homeworks, Assignments and Important Dates

  Assigned on Due by Comments
Homework 1 9/2 9/9  
 
Final 12/10, 10:30 AM    
 

Syllabus

Week.Class# Topic Reference
1.2 -- 3.2 Introduction to the course. Integers: division, modular arithmetic, congruences;  primes, greatest common divisors, number systems §3.4-3.7 from [KR]
F1 from [SB]
4.1 -- 5.2 Matrices and vectors: multiplication, transposes, determinants, binary matrices §3.8 from [KR]
P5 from [SB]
6.1 Review  
6.2 Test 1  
7.1 -- 7.2 Matrix analysis: linear equations, eigenvalues and eigenvectors P5 from [SB]
8.1 -- 10.2 Combinatorics: counting, pigeonhole principle, permutations, combinations, binomial coefficients, binomial theorem, generalized permutations and combinations, principle of inclusion-exclusion §5.1-5.5, 7.5-7.6 from [KR]
§1.1-1.3, 2.1-2.3 from [VB]
11.1 Review  
11.2 Test 2  
12.1 -- 13.1 Probability theory, Bayes' theorem, expectation and variance, random variables, distribution functions Chapter 6 from [KR]
P28 from [SB]
13.2 -- 14.1 Statistics: summarizing measured data, parameter estimation, confidence intervals, linear regression models P27 from [SB], notes
14.2 Thanksgiving holiday  
15.1 -- 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 Tuesday and 2 for Thursday). § denotes a section within a chapter. [SB], [KR], and [VB] refer to the textbooks indicated above.
 

Rajendra V. Boppana
Mail: CS Department, UT San Antonio, San Antonio TX 78249, USA
Phone: 210-458-5692  Fax: 210-458-4437   Email: boppana[at]cs.utsa.edu