NCM IST Mathematics for Computer Science

June 18–30, 2018

NCM webpage for IST Mathematics for Computer Science (2018)

Lectures

• Lecture 1, 18 June, 2018 (Lecture material), (Slides)

  Binary search, selection sort, insertion sort, merge sort

• Lecture 2, 18 June, 2018 (Lecture material), (Slides)

  Quicksort, graphs and graph representations

• Lecture 3, 19 June, 2018 (Lecture material), (Slides)

  Breadth first search, depth first search

• Lecture 4, 19 June, 2018 (Lecture material), (Slides)

  Shortest paths (Dijkstra, Bellman-Ford, Floyd-Warshall), minimum cost spanning trees (Prim, Kruskal)

• Lecture 5, 20 June, 2018

  Network flows, Ford-Fulkerson algorithm

• Lecture 6, 20 June, 2018

  Network flows, Max flow-Min cut theorem

• Lecture 7, 21 June, 2018

  Max flow to solve matchings, vertex cover in bipartite graphs, König's theorem

• Lecture 8, 21 June, 2018

  Introduction to classes P, NP. NP completeness, NP hardness, Independent set, vertex cover, clique, reductions

• Lecture 9, 22 June, 2018

  Scheduling problem, Make span, 2 approximation for make span

• Lecture 10, 22 June, 2018

  TSP – Inapproximability of TSP, 2 approximation for metric TSP, reductions and approximations

• Lecture 11, 23 June, 2018

  Linear inequalities, duality, lower bounds from dual problem

• Lecture 12, 23 June, 2018

  Vector spaces, linear equations, Gaussian elimination, LUP decomposition

• Lecture 13, 25 June, 2018

  Linear regression - an LP formulation of linear regression. Separating sets of points by a hyperplane - an LP formulation, Farkas's lemma. Complexity implications of Farkas's lemma.

• Lecture 14, 25 June, 2018

  Sparse solutions to linear equations, LP formulation for minimizing l1 norm, sufficient conditions for sparse solutions, Largest ball in a convex region - an LP formulation.

• Lecture 15, 26 June, 2018

  Regression via higher dimensional curves - a matrix formulation and analytical solutions, gradient descent, convex functions and convex domains, gradient descent analysis for Lipschitz convex functions.

• Lecture 16, 26 June, 2018 (Lecture material)

  Introduction to Machine Learning (ML): supervised and unsupervised learning, examples

• Lecture 17, 27 June, 2018 (Lecture material), (Slides)

  ML: Decision trees, information gain via entropy, handling continuous attributes, evaluating classifiers, precision and recall

• Lecture 18, 27 June, 2018

  Multiplicative weight updates

• Lecture 19, 28 June, 2018

  Ellipsoid algorithm for LP

• Lecture 20, 28 June, 2018 (Lecture material), (Slides)

  ML: overfitting, ensemble models, frequent itemsets, a priori algorithm

• Lecture 21, 29 June, 2018

  Naive Bayes classification, Singular Value Decomposition

• Lecture 22, 29 June, 2018 (Lecture material)

  Expectation maximization, Latent Dirichlet Analysis

  • What is the Expectation Maximization Algorithm?, by Chuong B Do and Serafim Batzoglou
  • The Expectation Maximization Algorithm, A short tutorial by Sean Borman
  • Introduction to Latent Dirichlet Allocation, Edwin Chen's blog

Tutorials

• Problem sheet, 18 June, 2018

• Problem sheet, 19 June, 2018

• Problem sheet, 20 June, 2018

• Problem sheet, 21 June, 2018

• Problem sheet, 22 June, 2018

• Problem sheet, 23 June, 2018

• Problem sheet, 25 June, 2018

• Problem sheet, 26 June, 2018

• Problem sheet, 28 June, 2018

Lecture Notes

• Lecture notes by Pallav D. Shah, P. D. Patel Institute of Applied Sciences, Charotar University of Science and Technology