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.

The course site for Fall 2007 is here

(See also CIS 295 Fall 2004)

See also counting examples.

Start Graph Theory 1 (Basic definitions, isomorphisms, paths)

(See also Hamiltonian circuit)

Graph Theory 3 (Trees, planarity, colorings)

Finished Graph Theory 4 (Graph algorithms)

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))

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 html (read sections 1-3, pp 1-6)

connection between NFA's and regular expressions (examples). construction of automaton for A* from automaton for language A.

Started discussion of Markov Chains 1 (Basic definitions, transition matrix). "Mark V Shaney", and other examples generated from trigram probability distributions.

(more on PageRank as a Markov process, How to make the top ten: Approximating PageRank from in-degree)

Set up example of Viterbi by hand.

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)

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.

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 = -Σ

Background text for Lecture 2: Chpt 4 of Rosen, *Discrete Mathematics
and its Applications* (on reserve at engineering library, also used by
cs 280)

Background text for Lectures 17-20: D. Kozen, Automata and Computability, pp 1-54.

Background text for Lectures 22-25
Sheldon Ross, *Stochastic Processes*

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