Mathematical Techniques for Computer Science Applications

G22.1180
Monday, 7:00-9:00.
Warren Weaver Hall room 312.
Professor Ernest Davis

Reaching Me

Office hours: Tue 10:00-12:00, Wed 3:00-4:00

Textbooks:

Required:
Amos Gilat, MATLAB: An Introduction with Applications, Wiley, 2008. Note that amazon.com is selling a new copy cheaper ($61.04) than the used copies at the NYU bookstore ($66), and you can get much cheaper used at bookfinder.com. For the purposes of this class, it does not matter which edition you buy. I didn't comparison shop the other books.
Steven Leon, Linear Algebra: With Applications, 7th edition, Pearson, 2005.

Recommended:
Morris DeGroot and Mark Schervish, Probability and Statistics, Addison Wesley, 2001.

Online documentation for MATLAB: Getting Started with MATLAB

Class email list

Be sure to subscribe to the class email list

Grader

Xin Li. email: lixin @ same host as above. Office: 1009 715 Bway. Office hours Thu, 2-4.

Prerequisites:

None.

Description

This course gives an introduction to theory, computational techniques, and applications of linear algebra, probability and statistics. These three areas of continuous mathematics are critical in many parts of computer science, including machine learning, scientific computing, computer vision, computational biology, computational finance, natural language processing, and computer graphics. The course will teach a specialized language for mathematical computation, such as MATLAB, and will discuss how the language can be used for computation and for graphical output. No prior knowledge of linear algebra, probability, or statistics is assumed.

Sample Code

Assignments

Assignment 1 due Sep. 28.
Exercises 1 NOT TO HAND IN.
Assignment 2 due Oct. 12. Postponed to Oct. 19.
Exercises 2 NOT TO HAND IN.
Assignment 3 due Nov. 2.
Sample Output for Assignment 3
Exercises 3 NOT TO HAND IN.
Assignment 4 due Nov. 16. Postponed to Nov. 23
Sample solutions to Assignment 4
Assignment 5 due Nov. 30.
Sample outputs for Assignment 5
Assignment 6 due Dec. 14
Sample outputs for Assignment 6

Final exam

Monday, December 21, 7:00 PM. 312 WWH.
Study sheet

Provisional syllabus, subject to change

Requirements

Biweekly assignments (60% of the grade).
Final exam (40% of the grade).

Part I. Introduction:

Week 1.A Introduction to MATLAB. Basic programming language features.
Class Notes Chapter 1: MATLAB. Gilat.

Part II. Linear Algebra:

Week 1.B. Vectors. Basic operations. Dot product. Vectors in MATLAB. Plotting in MATLAB.
Class Notes Chapter 2: Vectors.

Week 2. Matrices. Definition, fundamental properties, basic operations. Linear transformations.
Class Notes Chapter 3: Matrices.

Week 3. Abstract linear algebra: Linear independence, basis, rank, orthogonality, subspaces, null space.
Class Notes Chapter 4: Vector Spaces.

Week 4. Solving linear equations using Gaussian elimination.
Class Notes Chapter 5: Algorithms

Weeks 5+6. Geometric applications.
Class Notes Chapter 6: Geometry.

Week 7: Basis change and singular value decomposition.
Class Notes Chapter 7: Basis change.

Part III. Probability

Week 8: Introduction. Independence. Bayes's Law.

Week 9: Random variables. Expected value and variance. Discrete and continuous distributions.
Application: Machine learning.

Week 10: Information theory and entropy. Maximum entropy technique.

Week 11: Markov chains.
Application: Natural language processing.

Part IV. Statistics.

Week 12: Non-parametric statistics. Computer-based resampling techniques. Confidence intervals and statistical significance.
Application: Software testing.

Week 13: Distributions. Binomial and normal distributions.

Week 14: Monte Carlo methods.

Illness

Taking care of your health is always a priority, but particularly this year, as there is a widespread and dangerous flu epidemic. Therefore:
If you have any symptoms of the flu, and especially if you are sneezing or coughing, PLEASE TAKE CARE OF YOURSELF AT HOME AND DO NOT COME TO CLASS. Going out in public when you have a communicable illness is not only unwise in terms of your own health, but it is extremely irresponsible and unfair to fellow students to put them at risk.

Please note also:

I am not taking attendance, and there is no penalty for missing class. If you are too ill to come to class, but well enough to work at home, then submit your assignments by email. If you are too ill to work, I will accept assignments a week late. If you miss both the regular due date and the late deadline due to illness, please consult with me promptly about making up the assignment. If you are too ill to come to the final exam, if at all possible, let me know in advance by email; if not, then please contact me as soon as possible.

Cheating

You may discuss any of the assignments with your classmates (or anyone else) but all work for all assignments must be entirely your own. Any sharing or copying of assignments will be considered cheating. By the rules of the Graduate School of Arts and Science, I am required to report any incidents of cheating to the department. Department policy is that the first incident of cheating will result in the student getting a grade of F for the course. The second incident, by GSAS rules, will result in expulsion from the University.