Info 2950: Mathematical Methods for Information Science

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.

Announcements:
 – Nov 20Homework #6 is due Thursday Dec. 4. You can download it from CMS.
 – Nov 18The final exam is scheduled for Thursday December 11, 7:00-9:30PM, in 205 Upson.
 – Nov 6Homework #5 is due Thursday Nov. 20. You can download it from CMS.

Instructor:
  David Crandall
  340 Upson Hall
  crandall "at" cs.cornell.edu
  Office hours: Wednesdays 1:30-3:30pm
TA:
  Avi Levitan
  aal29 "at" cs.cornell.edu
  Office hours: Mondays 3:35-4:35 in 328 Upson

Lectures: Tuesdays and Thursdays 2:55-4:10pm, Upson 109
Prerequisites: Math 2310 (Math 231) 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

Schedule:
This schedule is preliminary and subject to change. Please check back regularly for updates.

Date Lecture Reading assignments
Week 1 Thursday 8/281. Course introduction, set theoryRosen ch 2.1-2.2
Notes on set theory
Week 2 Tuesday 9/22. Probability and countingRosen ch 5
Some notes
Some examples
Thursday 9/43. Conditional probability, Bayes' theoremRosen ch 6.1-6.2
Some notes
Week 3 Tuesday 9/94. Bayes' theorem, expected value, varianceRosen ch 6.2, 6.3
Some notes
Some more notes
Thursday 9/115. Applications of Bayes' theoremRosen ch 6.3
A plan for spam
Slides
Week 4 Tuesday 9/166. Binomial and normal distributionRosen ch 6.4
Thursday 9/187. Exponentials and logarithmsSome notes
Week 5 Tuesday 9/238. Graph theoryRosen ch 9.1-9.4
Some notes
Thursday 9/259. Eulerian and Hamiltonian circuitsRosen ch 9.5
Some notes
Week 6 Tuesday 9/3010. Trees, planarityRosen ch 9.7, 10.1-10.2
Some notes
Thursday 10/211. Colorings, graph algorithms, spanning treesRosen ch 9.6, 10.3-10.4
Some notes
Slides
Week 7 Tuesday 10/712. Graph algorithmsRosen ch 9.6, 9.8, 10.4-10.5
Slides
Thursday 10/913. More graph algorithmsSlides
Week 8 Tuesday 10/14Fall break
Thursday 10/1614. Applications of graphsWho is the best connected scientist?
Collective dynamics of small-world networks
Could it be a Big World After All?
Slides
Week 9 Tuesday 10/2115. Prelim review
Thursday 10/23Midterm exam (in class)
Week 10 Tuesday 10/2816. Applications of graphs: social networks and the webSlides
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)
Thursday 10/3017. PageRank, other applications of eigen decompositionSlides
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 Tuesday 11/418. Introduction to finite state automataSome notes
Rosen 12.3
Kozen, Automata and Computability, ch 2, 3
  (available in Engineering library)
Thursday 11/619. Regular languages, product constructionRosen 12.3
Kozen ch. 11
Week 12 Tuesday 11/1120. Nondeterministic finite automataRosen 12.3
Kozen ch. 5, 6
Thursday 11/1321. Regular expressionsRosen 12.4
Kozen ch. 7, 8
Week 13 Tuesday 11/1822. Regular expressions, applications of FSAs
Thursday 11/2023. Markov ChainsSome notes
More notes
Durbin excerpt (handed out in class)
Markov chain example
Week 14 Tuesday 11/2524. HMMs, the Viterbi algorithmSome notes
Viterbi example
Rabiner tutorial on HMMs, sections I, II, and III(b)
Thursday 11/27Thanksgiving break
Week 15 Tuesday 12/225. Applications of markov models
Russel & Norvig, "Artificial Intelligence", section 24.7 (on speech recognition)
  (available in Engineering library)
Thursday 12/426. More applications of markov models

Grading:
40% Homework assignments
10% Quizzes (in-class)
20% Midterm exam (in-class)
30% Final exam

You may turn in homework assignments up to 24 hours late. A grade penalty of 10% will be assessed. Missed quizzes may not be made up, but your lowest quiz score will be dropped before computing the final grade.

Academic integrity policy:

We take academic integrity very seriously. You are required to abide by the Cornell University Code of Academic Integrity and the Department of Computer Science 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 penalities 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.