CSE 383M (63970) Statistical and Discrete Methods for Scientific Computing
CS395T (52155) Computational Statistics with Application to Bioinformatics
The University of Texas at Austin Department of Computer Science
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.
- 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
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.
- [CB1] Mathematical Primer for Structural Bioinformatics by Chandrajit Bajaj (mirror link)
- [JK] Foundations of Data Science by John Hopcroft and Ravindran Kannan (mirror link)
- Additional Lecture notes for selected materials (Extra reference materials)
TENTATIVE COURSE OUTLINE.
|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||
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|
Distribution Sampling, Unbiased Estimators, Universal Hashing
due on 02-23-2015, 11:59pm
Discrepancy and Dispersion, Sampling Polyhedra, Quasi Monte Carlo Samplings, Motion Groups, Molecular Docking
|02-12-2015||High Dimension Integration, Error Bounds (Reproducing Kernel Hilbert Spaces)|| QMC1, QMC2,MQC
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|
Fast Normal Mode Analysis, Approximating Harmonic Motion of Molecule
Graph Laplacian, Graph Spectrum, Eigenvalues, Connection to Differential Geometry
|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
Random Matrices, Fast Approximate Matrix Multiplication
|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,||
|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||
|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|
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
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/
The syllabus page shows a table-oriented view of the course schedule, and the basics of course grading. You can add any other comments, notes, or thoughts you have about the course structure, course policies or anything else.
To add some comments, click the "Edit" link at the top.