INFO 295: Mathematical Methods for Information Science
Tue/Thu 2:55-4:10 PM
4 credits, S/U Optional
Co-requisite: Math 231 or equivalent
This course teaches basic mathematical concepts in information
modeling. Topics to be covered include graph theory, discrete
probability, finite automata, Markov models and hidden Markov models.
We will be guided by examples and applications from various areas of
information science such as: the structure of the Web, genome
sequences, natural languages, and signal processing.
Professor: Paul Ginsparg (301 College Ave, 5-7371,
Office hours: Wednesdays 2-3 PM (or by appointment)
Course website: http://courses.cit.cornell.edu/cis295_2005fa/ (this page)
Note: This is the course site for Fall 2005
The course site for Fall 2007 is here
Lecture 1 (Thu 25 Aug 05)
Intro, overview of topics to be discussed. Background discussion of
CIS 295 Fall 2004)
Lecture 2 (Tue 30 Aug 05)
Probability and Counting 1
(Probability space, events, binomial coefficients, conditional probability).
See also counting examples.
Lecture 3 (Thu 1 Sep 05)
More on conditional probability: Bayes' Law and examples. (see also Bayesian inference)
Lecture 4 (Tue 6 Sep 05)
more on independent events, binomial distributions, random variables,
expectation and variance (Probability and Counting 2
and newer notes)
Problem Set 1
Lecture 5 (Thu 8 Sep 05)
on expectation and variance of Bernoulli distributions
(also some comments on
distributions and the
limit theorem, see also), and started review of exponentials and logarithms.
Lecture 6 (Tue 13 Sep 05)
finished discussion of exponentials and logarithms.
Discussed counting equal heads/tails coin flips
using Stirling's formula, and the voter problem.
Lecture 7 (Thu 15 Sep 05)
discuss www-admin spam,
introduce A plan for spam
(See also "naive Bayes" document classification
and Bayesian filtering.)
Lecture 8 (Tue 20 Sep 05)
continue A plan for spam
(specifically "naive Bayes"
probabilities), plus more details on "naive
Problem Set 2
Lecture 9 (Thu 22 Sep 05)
Some final comments on combining probabilities
( p(L or R | O) vs p(O | L and R) ).
Start Graph Theory 1 (Basic definitions, isomorphisms, paths)
Lecture 10 (Tue 27 Sep 05)
Graph Theory 2 (Eulerian and Hamiltonian circuits)
(See also Hamiltonian circuit)
Graph Theory 3 (Trees, planarity, colorings)
Lecture 11 (Thu 29 Sep 05)
finish Graph Theory 3 (Euler's formula),
6 color theorem
(and 5 color theorem), start Graph Theory 4 (Graph algorithms)
Lecture 12 (Tue 4 Oct 05)
Some comments on Erdös-Renyi random graphs and
Milgram's "small world" experiment.
Finished Graph Theory 4 (Graph algorithms)
Problem Set 3
Lecture 13 (Thu 6 Oct 05)
More comments on small world networks:
Collective dynamics of 'small-world' networks (Watts/Strogatz, 1998)
and brief discussion of quantitative methods applied to social networks, node
and link centrality (browse sections 1.1, 1.2, 1.3.6, and 1.4
[pp 1-3, 14-25]
of Who is the best connected Scientist? (Newman, 2003))
Lecture 14 (Thu 13 Oct 05)
No class due to a conflict.
Instead read historical background material in
1) Vannevar Bush, As We May Think, Atlantic Monthly, July 1945
2) The World Wide Web: A very short personal history, Tim Berners-Lee
3) The Anatomy of a
Large-Scale Hypertextual Web Search Engine (Brin/Page, 1998), equivalent
(read sections 1-3, pp 1-6)
Lecture 15 (Tue 18 Oct 05)
Recapped brief history of the web, discussed
Page rank algorithm and Perron-Frobenius theorem.
Lecture 16 (Thu 20 Oct 05)
Completed discussion of
and discussed other features used in ordering heuristics,
"Google bombing" (NYTimes, 22 Jan 04)
sources in a hyperlinked environment (Kleinberg, 1998).
Lecture 17 (Tue 25 Oct 05)
Finite State Automata 1 (alphabet, DFA, regular sets)
Lecture 18 (Thu 27 Oct 05)
Finite State Automata 2 (NFA, subset construction)
Lecture 19 (Tue 1 Nov 05)
example of subset construction,
Finite State Automata 3 (Regular expressions)
Problem Set 4
Lecture 20 (Thu 3 Nov 05)
Comments on random graphs and Poisson distributions (problem 4 of midterm).
connection between NFA's and regular expressions
construction of automaton for A* from automaton for language A.
Lecture 21 (Tue 8 Nov 05)
more examples of the regexp/NFA connection,
ultimately periodiocity and constraints on lengths of elements of regular sets.
NFA's for vending machines, language parsing, and for gapped sequence
alignment. Colorless green ideas sleep furiously
and Chomsky transformational grammars.
Lecture 22 (Thu 10 Nov 05)
Examples of regular grammars, example of context-free grammar
(SCIgen - An Automatic CS Paper
Started discussion of
Markov Chains 1
(Basic definitions, transition matrix).
"Mark V Shaney", and
other examples generated from trigram probability
Problem Set 5
Lecture 23 (Tue 15 Nov 05)
Markov Chains 2 (Ergodic chains, stationary distributions)
(more on PageRank as a Markov process, How to make the top ten:
Approximating PageRank from in-degree)
Lecture 24 (Thu 17 Nov 05)
Introductory parts on Hidden Markov Models from
A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Rabiner, 1989), 257-261
Set up example of Viterbi by hand.
Lecture 25 (Tue 22 Nov 05)
Examples of Markov chains to determine the expected number of coin flips to
reach a given number of heads in a row.
Finished example of Viterbi by hand.
Some HMM examples from "Biological Sequence Analysis", by Durbin, Eddy, Krogh, Mitchison (ISBN: 0521629713) pp 46-57 (Class handout)
Problem Set 6
Lecture 26 (Tue 29 Nov 05)
Completed Examples of Markov chains to determine the expected number of coin flips.
Example of max probability state not on maximum probability path.
Example of CpG islands from Durbin et al pp 46-57 (handout).
Started example from Bursty and Hierarchical Structure in Streams.
Lecture 27 (Thu 1 Dec 05)
More comments on Poisson distributions.
Mentioned recent HMM speech recognition application: An elitist approach for extracting
automatically well-realized speech (Maj et al., 2005)
Finished HMM example from Bursty and Hierarchical Structure in Streams.
Derivation of (Shannon) information uncertainty,
I = -Σi pi log2 pi, and
lightning review of applications (compression, ...).
Take Home: available 2p.m. Tues 6 Dec, due 2 p.m. Fri 9 Dec
(should take no more than a few hours...)
Background text for Lecture 2: Chpt 4 of Rosen, Discrete Mathematics
and its Applications (on reserve at engineering library, also used by
Background text for Lectures 17-20:
D. Kozen, Automata and Computability, pp 1-54.
Background text for Lectures 22-25
Sheldon Ross, Stochastic Processes
This course is a required course for the new Information Science (IS)
major in the College of Arts and Sciences and the College of
Agriculture and Life Sciences. It can also be used to satisfy the
math/stats course requirement for the Information Science
INFO295 and CS280 may not both be taken for credit towards the IS major.