Cornell Information Science

INFO 295: Mathematical Methods for Information Science

Fall 2007
Tue/Thu 2:55-4:10 PM Hollister 110
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: (this page)

Lecture 1 (Thu 23 Aug 07)

Intro, overview of topics to be discussed. Background discussion of Set Theory.
(See also INFO 295 Fall 2006)

Lecture 2 (Tue 28 Aug 07)

Probability and Counting 1 (Probability space, events, binomial coefficients, conditional probability).
See also counting examples.

Problem Set 1 (due in class Thurs, 6 Sep 07)

Lecture 3 (Thu 30 Aug 07)

More on conditional probability: Bayes' Law and examples. (see also Bayesian inference)

Lecture 4 (Tue 4 Sep 07)

Finish Bayes' Law and examples.
More on independent events, binomial distributions, random variables, expectation and variance (Probability and Counting 2)

Lecture 5 (Thu 6 Sep 07)

Continue Probability and Counting 2 notes on independent events, expectation and variance of Bernoulli distributions

Problem Set 2 (due in class Thurs, 20 Sep 07)

Lecture 6 (Tue 11 Sep 07)

Some comments on normal distributions and the central limit theorem (see also), and review of exponentials and logarithms.

Lecture 7 (Thu 13 Sep 07)

Discuss www-admin spam, introduce A plan for spam (Graham, 2002) (plus "naive Bayes" and combining probabilities).
(See also section 6.3 of Rosen, and "naive Bayes" document classification and Bayesian spam filtering.)

Lecture 8 (Tue 18 Sep 07)

Completed A plan for spam (Graham, 2002) and follow-up (Graham, 2003), using more details on "naive Bayes".
(Additional updates on this approach, including FAQ and "white papers" can be found at dspam resources.)

Lecture 9 (Thu 20 Sep 07)

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)

Suggested Tue 16 Oct as likely date for in-class midterm exam.

Problem Set 3 (due in class Thus, 4 Oct 07)
Added note: here is a hint for [optional] 5b

Lecture 10 (Tue 25 Sep 07)

Graph Theory 2 (Eulerian and Hamiltonian circuits, see also Hamiltonian circuit)
Comments on De Bruijn sequences and magic tricks.
Example of Gray Coding from course text (pp 642-643).

Lecture 11 (Thu 27 Sep 07)

Graph Theory 3 (Trees, planarity, colorings, Euler's formula)

Lecture 12 (Tue 2 Oct 07)

(Comments on hint for [optional] 5b)
6 color theorem (and 5 color theorem). Started Graph Theory 4 (Graph algorithms).
Plus some comments on Milgram's "small world" experiment.

Lecture 13 (Thu 4 Oct 07)

Continue Graph Theory 4 (Graph algorithms), proof of minimum spanning tree algorithms, and application to clustering.

Fall Break (Tue 9 Oct 07)

Lecture 14 (Thu 11 Oct 07)

Finish Graph Theory 4 (Graph algorithms). Some comments on Erdös-Renyi random graphs, 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)), more on Milgram's "small world" experiment, and Collective dynamics of 'small-world' networks (Watts/Strogatz, 1998).

Problem Set 4 (due in class Tues, 30 Oct 07)

Lecture 15 (Tue 16 Oct 07)


Lecture 16 (Thu 18 Oct 07)

Final comments on small world networks, clustering coefficient. Comments on random graphs and Poisson distributions (problem set 4). Some additional comments on Poisson distributions.

Lecture 17 (Tue 23 Oct 07)

(Graph of C(17,i)/217 : probability of only four of seventeen last names in class starting in latter half of alphabet < ~10%)

Recap brief history of the web, start to discuss Page rank algorithm, see also AMS feature column.

Example iterations from n=4 example at end of class.

See also historical background material:
0) W3C "Little History"
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 html (sections 1-3, pp 1-6)

Lecture 18 (Thu 25 Oct 07)

Continue discussion of Page rank algorithm, AMS feature column.

(Note: office hours shifted to Monday 2 pm, at 301 College Ave office for weeks of 15,22,29 Oct)

Lecture 19 (Tue 30 Oct 07)

Complete discussion of Page rank algorithm, and Perron-Frobenius theorem (for the mathematically inclined, see also The $25B Eigenvector).

Problem Set 5 (due in class Thu 15 Nov)

Lecture 20 (Thu 1 Nov 07)

Discuss other features used in ordering heuristics, mention "Google bombing" (NYTimes, 22 Jan 04) and Authoritative sources in a hyperlinked environment (Kleinberg, 1998).
Begin Finite State Automata 1 (alphabet, DFA, regular sets)

Some additional resources (suggested by a student last year as useful, feel free to forward others you've found): Wikipedia PageRank, Webworkshop pagerank, efactory pagerank-algorithm, ...

Lecture 21 (Tue 6 Nov 07)

Continue Finite State Automata 1 (alphabet, DFA, regular sets), examples of DFAs.

Lecture 22 (Thu 8 Nov 07)

Finite State Automata 2 (NFA, subset construction) and example of subset construction. Finite State Automata 3 (Regular expressions)

Lecture 23 (Tue 13 Nov 07)

Ultimately periodiocity and constraints on lengths of elements of regular sets. Connection between NFA's and regular expressions (examples). Construction of automaton for A* from automaton for language A.

Lecture 24 (Thu 15 Nov 07)

More examples of the regexp/NFA connection, examples of language parsing and number recognition. Colorless green ideas sleep furiously.
Started discussion of Markov Chains 1 (Basic definitions, transition matrix), more on PageRank as a Markov process.

Problem Set 6 (due in class Thurs 29 Nov)

Lecture 25 (Tue 20 Nov 07)

Relation between Markov chains and random walks on weighted graphs, worked example, genomics example from Durbin et al pp 46-57 (handout in class).
Examples of Markov chains to determine the expected number of coin flips to reach a given number of heads in a row.

Lecture 26 (Tue 27 Nov 07)

"Mark V Shaney" and other examples generated from trigram probability distributions, Markov Chains 2 (Ergodic chains, stationary distributions).
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 27 (Thu 29 Nov 07)

Finish example of Viterbi by hand.
Example of max probability state not on maximum probability path.
Example of CpG islands from Durbin et al pp 46-57 (handout).
Example from Bursty and Hierarchical Structure in Streams.

Final Exam

Take Home: available 2p.m. Tues 4 Dec, due 2 p.m. Fri 7 Dec (should take no more than a few hours...). Contact me by e-mail with any questions, and I'll have office hours on Wed afternoon, 2-4.

Background text for Lectures 1-5: Chpt 2, Sections 5.3,5.4, and Chpt 6 of Rosen, Discrete Mathematics and its Applications (6th edition), on reserve at engineering library, also used by cs 280. (These are the sections on Sets, Permutations and Combinations, Binomial Coefficients, Probability Theory, Bayes' Theorem, Expected Value and Variance. Note that in earlier editions of the book these sections were in Chpts 1 and 4.)
For lectures 6--8, see Rosen sections 6.3,6.4 (Bayes' Thm, Expected Value and Variance)
For lectures 9--14, see Rosen chapters 9,10 (Graphs, Trees)
For lectures 21--24, see Rosen sections 12.2-12.4

Advising Notes

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 minor/concentration.
INFO295 and CS280 may not both be taken for credit towards the IS major.