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.

(See also INFO 295 Fall 2006)

See also counting examples.

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

More on independent events, binomial distributions, random variables, expectation and variance (Probability and Counting 2)

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

(See also section 6.3 of Rosen, and "naive Bayes" document classification and Bayesian spam filtering.)

(Additional updates on this approach, including FAQ and "white papers" can be found at dspam resources.)

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

Comments on De Bruijn sequences and magic tricks.

Example of Gray Coding from course text (pp 642-643).

6 color theorem (and 5 color theorem). Started Graph Theory 4 (Graph algorithms).

Plus some comments on Milgram's "small world" experiment.

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

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)

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

Problem Set 5 (due in class Thu 15 Nov)

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, ...

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)

Examples of Markov chains to determine the expected number of coin flips to reach a given number of heads in a row.

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.

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.

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

INFO295 and CS280 may not both be taken for credit towards the IS major.