Course Syllabus

CSE 383M (63970) Statistical and Discrete Methods for Scientific Computing

CS395T (52155) Computational Statistics with Application to Bioinformatics

Spring 2015

The University of Texas at Austin 
Department of Computer Science 

 

Instructor:

Professor Chandrajit Bajaj

  • Office hours – Wednesday 1:15 p.m. - 3:15 p.m., POB 2.324A
  • Contact: bajaj at cs.utexas.edu

NOTE: Most questions should be submitted to Canvas rather than by sending emails to the instructor. Please make reservation a day before for the office hour in advance to avoid conflict. 

 

Teaching Assistant

Xiaorong Zhu

  • Office hours – Tuesday 1:30p.m. - 2:30 p.m, Thursday 11:00 a.m. - 12:00 p.m., GDC 6.408C 
  • Contact: xiaorong at utexas.edu

Note: Please make reservation a day before for the office hour in advance to avoid conflict. 

 

Lecture Time and Location: T Th 9:30 – 11:00 a.m. in GDC 4.304 

 

Prerequisites

This Course dwells on fundamentals and algorithms for data in high dimensions with provably probabilistic bounds on the accuracy. The emphasis shall be on high dimensional linear and non-linear geometric data with applications in Bioinformatics and Scientific Computing. The course is aimed at first or second year graduate students, especially in the CSEM, CS, and ECE programs, but others are welcome. You’ll need math at the level of at least 2nd year calculus, plus linear algebra, plus either more continuous math (e.g., CS and ECE students) or more discrete math (e.g., CSEM students). 

 

Textbook and Course Material.

 

TENTATIVE COURSE OUTLINE. 

Date Topic Reading Assignments
01-20-2015 High Dimensional Spaces, Law of Large Numbers  [JK] Chap2, Appendix
 
01-22-2015 Cube, Spheres, Gaussians in High Dimensions, Central Limit Theorem  [JK] Chap2, Appendix

 A1

due on 02-04-2015, 11:59pm

01-27-2015 Bernoulli Trials, Probability Distributions, Binomial, Poisson, Normal  [JK] Appendix  
01-29-2015 Markov, Chebyshev Tail Bounds, Chernoff Bounds   [JK] Appendix  
02-03-2015  Uniform Sampling of Spheres, Gaussians in High Dimension, Separating Mixtures of Gaussians  ss[JK] Chap2, Chap3 A1 Solution 
02-05-2015

Distribution Sampling, Unbiased Estimators, Universal  Hashing

 [JK] Appendix    A2

due on 02-23-2015, 11:59pm

02-10-2015

Discrepancy and Dispersion, Sampling Polyhedra, Quasi Monte Carlo Samplings, Motion Groups, Molecular Docking

sa, LD1
 
02-12-2015  High Dimension Integration, Error Bounds (Reproducing Kernel Hilbert Spaces)  QMC1, QMC2,MQC
 
02-17-2015

Eigenvalues, Eigenvectors, Singular Vectors, Real Spectral Theorem

 [JK] Appendix, Chap3  
02-19-2015 SVD, Low Rank Matrix Approximation; Best Fit Spaces [JK] Chap2  A2 Solution
02-24-2015 Fast SVD, Principal Components  [JK] Chap3  A3 out, 

due on 03-15-2015, 11:59pm

02-26-2015 Best Fit Subspaces, Random Projections, Dimension Reduction,   [JK] Chap2  
03-03-2015 Johnson-Lindenstrauss Lemma, Approximate Nearest Neighbours   [JK] Chap2  
03-05-2015 Fast Johnson-Lindenstrauss Lemma   [JK] Chap2  
03-10-2015

 Fast Normal Mode Analysis, Approximating Harmonic Motion of Molecule 

 NMA  
03-12-2015

Graph Laplacian, Graph Spectrum, Eigenvalues, Connection to Differential Geometry

 [JK] Appendix  
03-17-2015  Spring break    
03-19-2015  Spring break   A3 Solution 
03-24-2015  Midterm Exam  [midterm solution]   A4 out on April 1st, 

due on 04-15-2015, 11:59pm

03-26-2015

Random Matrices, Fast Approximate Matrix Multiplication

 [JK] Chap4  
03-31-2015 Matrix Sketching, Non-uniform Sampling   [JK] Chap7  
04-02-2015  Probability Approximation Analysis of Sketching Matrices Multiplication, Martingale theory  [JK] Chap10  
04-07-2015 Compressive Sensing, Sparse Vectors  [JK] Chap10  
04-09-2015 Perceptron, Learning, Threshold Function, SVM  [JK] Chap6  
04-14-2015 Non-linear SVM Kernel Methods  [JK] Chap6 A4 Solutioin 
04-16-2015  Shatter Functions, VC-Dimension, PPAC: Provably Probablistic Approximate Correct Learning Theory  [JK] Chap6  A5 out, 

due on 05-07-2015, 11:59pm

04-21-2015  VC-Dimension Theorem, Supervised Learning Sample Sizes   [JK] Chap6  
04-23-2015  Multivariate Geometric Optimization, Convex Programming,

[CB1]  paper

 [JK] Chap6

 
04-28-2015  Global Polynomial Optimization over Semi-algebraic sets CB1 paper  [JK] Chap6  
04-30-2015 Polynomial Equation System Solving and Generalized eigenvalue problems, Resultants, Bezoutians

[CB1]

 [paper]

 
05-05-2015 Random Walks and Markov Chain, Metropolis Hastings, Gibbs Sampling   [JK] Chap5   
05-07-2015 Review of Lessons Learned and the Way Forward, Take-home Final Exam  [CB1] slides  Exam Due on 05-14-2015, 11:59pm

 

Tests

There will be one in-class midterm exam and one in-class final exam. The proposed dates for the two tests are:

  • Midterm: Tuesday, March 24
  • Final: Thursday, May 7

 

Assignments

There will be five written HW assignments. Please refer to the above schedule for assignments due time. You are allowed to discuss with each other, but all solutions must be written individually.

 

Course Requirements and Grading

Grades will be based on these factors

  • In-class attendance and participation (extra 10%)
  • HW assignments (60% and a little more extra credit) 

5 assignments, each will take 12% for the final grade. Some assignments may have extra questions for extra points you can earn. (They will be specified in the assignment sheet each time.)

  • In-class midterm exam (20%) 
  • Take home final exam (20%) 

 

Students with Disabilities. Students with disabilities may request appropriate academic accommodations from the Division of Diversity and Community Engagement, Services for Students with Disabilities, 471-6259, http://www.utexas.edu/diversity/ddce/ssd 

 

Accommodations for Religious Holidays. By UT Austin policy, you must notify the instructor of your pending absence at least fourteen days prior to the date of observance of a religious holiday. If you must miss a class or an examination in order to observe a religious holiday, you will be given an opportunity to complete the missed work within a reasonable time before or after the absence, provided proper notification is given.

 

Statement on Scholastic Dishonesty. Anyone who violates the rules for the HW assignments or who cheats in in-class tests or the final exam is in danger of receiving an F for the course. Additional penalties may be levied by the Computer Science department,  CSEM  and the University. See http://www.cs.utexas.edu/academics/conduct/

 

 

 

Course Summary:

Date Details