Course Objectives:

The main objective of this course is to introduce students to some of the key computational techniques used in modelling and simulation of real-world phenomena. This course is designed to expose students to techniques and methods from a variety of disciplines, not normally encompassed in a single course. Unlike other courses focused more specifically on algorithms, data structures or numerical analysis, this course emphasizes hands-on programming to understand a variety of scientific phenomena and computational methods.

Course Contents

A subset of the following topics will be covered in a typical offering of the course and the lecture/lab hours mentioned for each topic are only indicative of the actual hours.

Introduction to Python, plotting in Python, Monte Carlo simulations, sampling from a discrete distribution, estimating Pi using Monte Carlo simulations, verifying the prime number theorem, random text generation, introduction to Python’s scipy.stats module (2 lectures, 3 lab hours)

Concepts of object-oriented programming, basic algorithms for efficiently traversing and computing path length distributions of arbitrary networks, computing set of connected components using Breadth First Search, introduction to networks, small world networks, percolation, introduction to Pythons’s *NetworkX *package (2 lectures, 3 lab hours)

Introduction to linear system of equations, Jacobi and Gauss-Siedel iterative techniques for solving linear systems, interpolation and Lagrange polynomial, polynomial curve fitting, introduction to Python’s *scipy.interpolate *and *numpy.linalg *(routines to solving equations and inverting matrices) modules (2 lectures, 3 lab hours)

Numerical differentiation using forward-difference formula, elements of numerical integration, the trapezoidal rule, computing the Jacobian matrix, estimating position from accelerometer reading, introduction to Python’s *scipy.integrate *sub-package (2 lectures, 3 lab hours)

Discrete least squares approximations, orthogonal functions, orthogonal least square polynomials and least square approximation, discrete trigonometric approximations, fast Fourier transform (FFT). Introduction to Python’s *numpy.polynomial *and *numpy.fft *packages (2 lectures, 3 lab hours)

Introduction to ordinary differential equations (ODEs), theory of Initial-Value problems, Euler method for solving initial-value problems, simulating a simple pendulum, solving ODEs using Python’s scipy.integrate module (2 lectures, 3 lab hours)

Introduction to partial differential equations (PDEs), finite difference method for solving PDE, finding a root using the bisection method, fixed-point iteration, Newton’s method, finding the fixed point of the dynamics of a single cardiac cell, simulation of the cardiac tissue PDE, using Python’s visualization tools, introduction to Python’s PDE solver (2 lectures, 1 lab)

Introduction to matrix factorization, Cholesky decomposition, sampling from a continuous distribution, ratio-of-uniforms method, generating Gaussian random vectors, introduction to Python’s *numpy.linalg *(routines for matrix decomposition) and *numpy.random *modules (2 lectures, 3 lab hours)

Introduction to Eigen values and Eigen vectors, the power method, deflation methods, applications in page rank and mixing time of Markov chains, introduction to singular value decomposition (SVD), relation to the least square problem, sensitivity of SVD, computing SVD, application in image compression (4 lectures, 6 lab hours)

Monte Carlo integration, importance sampling, introduction to Markov chain, Metropolis-Hastings algorithm, the Ising model, simulated annealing, Gibbs sampler (4 lectures, 6 lab hours)

Introduction to convex optimization, constrained optimization, dual function, dual problem, gradient method with fixed and diminishing step size, rate of convergence and bounds on deviation from optimal value, introduction to Python’s CVXOPT package (2 lectures, 3 lab hours)

Introduction to k-SAT and colorability, the Davis-Putnam algorithm, introduction to Python’s *python-sat *package, NP-completeness, number partitioning problem, recursive and dynamic programming (2 lectures, 3 lab hours)

Learning Outcomes:

Upon successful completion of this course, the student will:

  1. have working knowledge of some popular and well-known computational methods.
  2. be able to Write codes that use computational methods to numerically solve problems in a variety of disciplines.
  3. Know about open source packages that implement popular computational methods.
  4. be able to apply the mathematical concepts discussed over the duration of the course.

Text Books:

None

References:

  1. Richard L. Burden and J. Douglas Faires, “Numerical Analysis,” Cengage Learning; 9th edition, January 1, 2015, ISBN-13: 978-8131516546

  2. William H. Press, Saul A. Teukolsky, William T. Vetterling and Brian P. Flannery, “Numerical Recipes: The Art of Scientific Computing,” Cambridge University Press; 3rd edition, September 6, 2007, ISBN-13: 978-0521880688

  3. Chris Myers, “Computational Methods for Complex Systems: Notes and Exercises” Available online at http://pages.physics.cornell.edu/~myers/teaching/ComputationalMethods*

  4. Official documentation for Python 3 Available online at https://docs.python.org/3

  5. Other reference materials will be prescribed by the instructor on a topic-by-topic basis.

Metadata

Proposing Faculty: Department: Computer Science and Engineering Programme: B.Tech Proposing date: Approved date: Proposal type: Offerings: