[ADD TEXT]

Intro to Stochastic Processes

Syllabus:

DISCRETE-TIME MARTINGALES: Optional Stopping theorem, Martingale convergence theorem, Doobs inequality and convergence.
BRANCHING PROCESSES: Model definition. Connection with martingales. Probability of survival. Mean and variance of number of individuals.
DISCRETE-TIME MARKOV CHAINS: Classification of states, Stationary distribution, reversibility and convergence. Random walks and electrical networks. Collision and recurrence.
BASIC PROBABILISTIC INEQUALITIES AND APPLICATIONS: First and Second Moment methods. Applications to Longest increasing subsequences, Random k-Sat problem and connectivity threshold for Erdos-Renyi graphs. Chernoff bounds and Johnson-Lindenstrauss lemma.

Reference Texts:

(a) N. Lanchier: Stochastic Modelling.
(b) W. Feller: Introduction to Probability: Theory and Applications - Vol. I and II..
(c) L. Levine, Y. Peres and E. Wilmer: Markov chains and mixing times.
(d) Sheldon Ross: Probability Models.
(e) Santosh S. Venkatesh: Theory of Probability - Explorations and Applications.
(f) R. Meester: A Natural Introduction to Probability Theory.
(g) S. R. Athreya and V. S. Sunder: Measure and Probability.
heart Sebastien Roch: Modern Discrete Probability: A toolkit. (Notes).

https://www.isibang.ac.in/~adean/infsys/database/Bmath/SP.html

Design and Analysis of Algorithms

Syllabus: Basics of Algortihm Analysis: Models of computation, asymptotic order of growth, algorithm analysis, time and space complexity, average and worst case analysis, lower bounds.
Algorithm design techniques: Greedy algorithms, Divide and conquer, dynamic pro- gramming, amortization, randomization.
Complexity classes: Problem classes P, NP, PSPACE; reducibility, NP-hard and NP complete problems. Approximation algorithms for some NP-hard problems.

Reference Texts:

(a) T. H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein: Introduction to Algorithms
(b) J. Kleinberg and E. Tardos: Algorithm Design
(c) R. Sedgewick and P. Flajolet: Introduction to the Analysis of Algorithms
(d) R. Sedgewick: Algorithms
(e) A. Aho, J. Hopcroft and J. Ullmann: Introduction to Algorithms and Data Structures
(f) M. Sipser: Introduction to the Theory of Computation
(g) S. S. Skiena: The algorithm Design Manual

https://www.isibang.ac.in/~adean/infsys/database/Bmath/DAA.html

Field and Galois theory

Syllabus:

- Algebraic extensions: degree, Splitting fields and normal extensions, Algebraic closure.
- Separable extensions, Fundamental theorem of Galois theory.
- Finite fields, Cyclic extensions, Kummer theory.
- Ruler and compass constructions, Solvability by radicals.
- Transcendental extensions: Transcendence bases and transcendence degree

Reference Texts:

(a) M. Artin: Algebra.
(b) S. D. Dummit and M. R. Foote: Abstract Algebra.
(c) I. N. Herstein: Topics in Algebra.
(d) K. Hoffman and R. Kunze: Linear Algebra.
(e) C. Musili: Rings and Modules.
(f) P. Morandi: Field and Galois theory.
(g) N. Jacobson: Basic Algebra.

https://www.isibang.ac.in/~adean/infsys/database/Bmath/FGT.html

Probability III

Syllabus:

- Sigma-algebras, axioms of probability, pi - lamda theorem (proof can be skipped), uniqueness of extension for probability measures. Examples of countable probability spaces, Borel sigma-algebra on the real line and standard probability distributions on the real line.
- Construction of Lebesgue measure (statement alone). Random variables and examples. Push-forward of a probability measure (sketch of proof) . Borel probability measures on Euclidean spaces as push-forward of Lebesgue measure (statement alone); Cumulative distribution function and properties.
- General definition of expectation and properties. Change of variables. Review of conditional distribution and conditional expectation, General definition, Examples.
- Limit theorems: Monotone Convergence Theorem (MCT) (without proof), Fatous Lemma, Dominated Convergence Theorem (DCT), Bounded Convergence Theorem (BCT), Cauchy-Schwartz, Jensen and Chebyshev inequalities.
- Different modes of convergence and their relations, Weak Law of large numbers, First and Second Borel-Cantelli Lemmas, Strong Law of large numbers (proof under finite variance).
- Characteristic functions, properties, Inversion formula and Levy continuity theorem (statements only), CLT in i.i.d. finite variance case. Slutskys Theorem.
- Introduction to Finite Markov chains - Definition. Random mapping representation. Examples. Irreducibility and aperiodicity. Stationary distribution and reversibility. Random walks on graphs.

Reference Texts:

(a) N. Lanchier: Stochastic Modelling.
(b) W. Feller: Introduction to Probability: Theory and Applications - Vol. I and II..
(c) J. Pitman: Probability.
(d) Sheldon Ross: Probability Models.
(e) Santosh S. Venkatesh: Theory of Probability - Explorations and Applications.
(f) R. Meester: A Natural Introduction to Probability Theory.
(g) S. R. Athreya and V. S. Sunder: Measure and Probability

https://www.isibang.ac.in/~adean/infsys/database/Bmath/PT3.html