Info 2950: Mathematical Methods for Information Science

Spring 2012
Tue/Thu 1:25-2:40 PM Upson 211
4 credits, S/U Optional

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: David P. Williamson (236 Rhodes Hall)
Email: My three initials at
Phone:(607) 255-4883
Office hours: Tuesday 3-4, Wednesday 11-12, or by appointment
Course website: (this page)
Prerequisite: Math 2310 or a similar linear algebra class.
Textbook: Rosen, Discrete Mathematics and Its Applications, 6th edition
Grades and assignments are available via the Course Management System
This schedule is preliminary and subject to change. Please check back regularly for updates.

Date Lecture Reading assignments
Week 1Tue 1/24 1. Course introduction, set theoryRosen ch 2.1-2.2
Notes on set theory
Slides on CMS
Thu 1/262. Probability and countingRosen 5.3, 6.1, 6.2
Some notes
Week 2 Tue 1/313. More probabilityRosen ch 6.1
Some notes
Thu 2/24. Conditional probability, Bayes' theoremRosen ch 6.2, 6.3
Some notes
Week 3 Tue 2/75. Applications of Bayes' theoremRosen ch 6.3
A plan for spam
Thu 2/96. Expected value, variance, binomial and normal distributionsRosen ch 6.4
Week 4 Tue 2/147. Central limit theorem, exponentials and logarithmsSome notes
Thu 2/168. Graph theory, Eulerian circuitsRosen ch 9.1-9.5
Some notes
Week 5 Tue 2/219. Eulerian and Hamiltonian circuits, planar graphsRosen ch 9.5, 9.7
Some notes
Thu 2/2310. Planar graphs, graph coloringRosen ch 9.7-9.8
Some notes
Week 6Tue 2/2811. Spanning trees, minimum spanning treesRosen 10.1, 10.4-10.5
Some notes
Thu 3/112. Shortest pathsRosen ch 9.6
Week 7Tue 3/613. Traveling salesman problemRosen 9.6
Thu 3/814. Prelim review
Week 8 Tue 3/1315. Inclass prelim
Thu 3/1516. Small world?Some slides
Milgram's paper
Kleinfeld's critique
Week 9 Tue 3/20 Spring break
Thu 3/22 Spring break
Week 10 Tue 3/2717. A brief history of the web, and PageRank Some slides
Articles on the history of the web:
  Web timeline (W3C)
  As we may think (V. Bush, 1945)
  The WWW: a short personal history (T. Berners-Lee, 1998)
  Google paper (Brin & Page, 1998)
Thu 3/2918. PageRank computation and HITS Sample PageRank calculation
Some notes on PageRank and HITS
Other references on HITS and PageRank:
  AMS feature article
  The $25B Eigenvector (Bryan & Leise)
  HITS article (Kleinberg, 1998)
  Article on Google bombing (NY Times)
Week 11 Tue 4/3 19. The Poisson distributionSome notes
Thu 4/520. Markov ChainsSome notes
Week 12 Tue 4/1021. Markov chains and stationary distributionsSome notes
Thu 4/12 22. HMMs and the Viterbi algorithmRabiner tutorial on HMMs, sections I, II, and III(b)
Viterbi example
Week 13 Tue 4/1723. Introduction to deterministic finite state automata Rosen 12.3, 12.4
Also, Sipser Introduction to the Theory of Computation 1.1
Thu 4/1924. Nondeterministic finite automata Notes
Rosen 12.3
Sipser, Introduction to the Theory of Computation 1.2
Week 14 Tue 4/2425. Equivalence of NFAs and DFAs, regular expressions Notes on NFAs and Example of subset construction
Regular expressions Rosen 12.3, Sipser 1.2, 1.3
Thu 4/2626. Equivalence of finite automata and regular expressions Rosen 12.4, Sipser 1.3
Week 15 Tue 5/127. Turing Machines and the halting problemSipser 3.1, 4.2
Thu 5/328. Course summarySlides

45% Homework assignments
20% Midterm exam (inclass)
30% Final exam
5% Class participation and course evals

You may turn in homework assignments up to 24 hours late. A grade penalty of 10% will be assessed. The lowest homework score will be dropped.

Academic integrity policy:

We take academic integrity very seriously. You are required to abide by the Cornell University Code of Academic Integrity. It is your responsibility to understand and follow these policies.

In particular, the work you submit for course assignments must be your own. You may discuss homework assignments with other students at a high level, by for example discussing general methods or strategies to solve a problem, but you must cite the other student in your submission. Similarly if you consult other references (e.g. textbooks) in solving a problem, you must cite that source as well. Any work you submit must be your own understanding of the solution, the details of which you personally and individually worked out, and written in your own words.

Unless noted otherwise, all exams are closed book. During an exam you may not collaborate with other people in any way.

We will assess penalties for academic integrity violations on a case-by-case basis. Possible penalties range from a grade reduction to a referral to the Academic Integrity Hearing Board to consider suspension or expulsion from the university.