CSE 301: Mathematical Analysis for Computer Science
Semester starting from 28th March 2009
Contact:
Dr. Masud Hasan
Room: CSE 657, Phone: x7738
Email: masudhasan AT cse DOT buet DOT ac DOT bd
Course web: http://teacher.buet.ac.bd/masudhasan/cse301.html
Announcements:
Class Test 1: 12/04/2009, Sunday, in class. Syllabus: Recurrent Problems and Manipulation of Sums; See detail below. Remember to solve the exercises.
Class Test 2 and 3: 10/05/2009, Sunday, in class. Syllabus: CT2: Integer Functions and Number Theory, CT3: Binomial Coefficient and Special Numbers; See detail below.
Class Test 4 and 5: 28/06/2009, Sunday, in class. Syllabus: CT4: Introduction to Probability Theory (Chapter 1), Random Variables (Chapter 2); CT3: Markov Chains (Chapter 4), The Exponential Distribution and the Poisson Process (Chapter 5), and
Continuous-Time Markov Chain (Chapter 6); See detail below.
Class Test marks and answer sheets:
Text:
[Concrete] Concrete Mathematics: A Foundation for Computer Science, 2nd Edition, by Ronald Graham, Donald Knuth, and Oren Patashnik [Collect this book now. It is available at Nilkhet. Indian edition also available, but missing references.]
[Art1] The Art of Computer Programming, Volume 1, Third Edition, by Donald E. Knuth [Chapters will be mentioned]
[Art2] The Art of Computer Programming, Volume 2, Third Edition, by Donald E. Knuth [Chapters will be mentioned]
[Ross] Introduction to Probability Models, by Seldon M. Ross, 9th Edition
[Trivedi] Probability and Statistics with Reliability, Queing, and Computer Science Applications, by Kishor S. Trivedi
Class Note
Syllabus:
Related pre and post ambles of sections/bullets are by default included
Class notes are by default included
All related exercises
are by default included. (Remember that the solution to the exercises in [Concrete] and [Art]
are given at their ends.)
Recurrent Problems
[Concrete]
1.1-1.3 (up to page 11 middle)
Exercise: 1-8, 11(a), 12-14, 17, 21
Manipulation of Sums
[Concrete]
2.1-2.4, 2.5 ("Proof by induction" and "Perturbation method" only)
Exercise: 1, 3-5, 11, 14, 19-23, 25, 26
[Art1]
1.2.3
Exercise: 1-4, 11-17, 19, 25, 26, 28-30, 32
Integer Functions
[Concrete]
3.1, 3.2 (up to Eq. 3.12), 3.4
Exercise: 1-5, 7, 8, 10-12, 14, 15, 19, 21, 23, 31, 33,
[Art1]
1.2.4
Exercise: 1-3, 4-23, 25-28, 33, 35, 41, 48
Number Theory
[Concrete]
4.1 (up to Eq. 4.7 exclusive), 4.2, 4.3 (up to page 110 first para), 4.4, 4.5
(up to Eq. 4.30), 4.6 up to Eq. 4.39 exclusive)
Exercise: 1, 3, 6, 7, 9, 13(a), 14-16, 18, 31
[Art2]
4.5.4 (up to page 381 first para), page 391-392 first para
Binomial Coefficient
[Concrete]
5.1 (up to Eq. 5.8)
[Art1]
1.2.6 (topics/equations related to the corresponding [Concrete] syllabus above)
Special Numbers
[Concrete]
6.1 (up to Eq. 6.8), 6.2 (up to Eq. 6.36), 6.6 (up to Eq. 6.111)
Exercise: 1, 4, 6, 27, 28(b),
[Art1]
1.2.5 (up to Eq. 9 exclusive)
Exercise: 1, 2, 4-6, 11-13
1.2.7 (up to Eq. 3 exclusive)
Exercise: 1, 2, 16, 19
1.2.1 (page 13 only)
1.2.8
Exercise: 1, 2, 4, 5, 7, 8, 9-13, 18, 20, 28, 31, 39
Generating Functions
[Concrete]
7.1
Exercise: 1
Introduction to Probability Theory
[Ross]
1.1-1.6, related exercise
Random Variables
[Ross]
2.1 (uo to Example 2.4), 2.2, 2.3.2, 2.4.1, 2.4.2 (only Example 2.21), 2.5.1 (only Example 2.29-2.32), related exercise
Markov Chains
[Ross]
4.1 (up to Example 4.6), 4.2, 4.3 (up to Example 4.14), 4.4 (up to Example 4.19), 4.5.1 (up to Example 4.24), related exercise
The Exponential Distribution and the Poisson Process
[Ross]
5.2.2 (Examples 5.2, 5.3, 5.5), 5.3.1, 5.3.2 (up to Definiion 5.1), 5.3.3 (Example 5.13), related exercise
Continuous-Time Markov Chain
[Ross]
6.1, 6.2, 6.3 (Examples 6.2, 6.3, 6.5, 6.6), related exercise
Queuing Theory
[Ross]
8.1-8.3, 8.4 (up to page 519)
Photocopy:
[Trivedi] Chapter 7, 8 (only look at how to draw system diagrams and state transition diagrams, and look at related examples. You don't need to learn their methodologies, notations, and techniques)
Class Note of 27/06/2009