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: |
| Date | Lecture | Reading assignments | |
|---|---|---|---|
| Week 1 | Tue 1/24 | 1. Course introduction, set theory | Rosen ch 2.1-2.2 Notes on set theory Slides on CMS |
| Thu 1/26 | 2. Probability and counting | Rosen 5.3, 6.1, 6.2 Some notes | |
| Week 2 | Tue 1/31 | 3. More probability | Rosen ch 6.1 Some notes |
| Thu 2/2 | 4. Conditional probability, Bayes' theorem | Rosen ch 6.2, 6.3 Some notes | |
| Week 3 | Tue 2/7 | 5. Applications of Bayes' theorem | Rosen ch 6.3 A plan for spam |
| Thu 2/9 | 6. Expected value, variance, binomial and normal distributions | Rosen ch 6.4 | |
| Week 4 | Tue 2/14 | 7. Central limit theorem, exponentials and logarithms | Some notes |
| Thu 2/16 | 8. Graph theory, Eulerian circuits | Rosen ch 9.1-9.5 Some notes | |
| Week 5 | Tue 2/21 | 9. Eulerian and Hamiltonian circuits, planar graphs | Rosen ch 9.5, 9.7 Some notes |
| Thu 2/23 | 10. Planar graphs, graph coloring | Rosen ch 9.7-9.8 Some notes | |
| Week 6 | Tue 2/28 | 11. Spanning trees, minimum spanning trees | Rosen 10.1, 10.4-10.5 Some notes |
| Thu 3/1 | 12. Shortest paths | Rosen ch 9.6 | |
| Week 7 | Tue 3/6 | 13. Traveling salesman problem | Rosen 9.6 |
| Thu 3/8 | 14. Prelim review | ||
| Week 8 | Tue 3/13 | 15. Inclass prelim | Thu 3/15 | 16. 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/27 | 17. 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/29 | 18. 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 distribution | Some notes |
| Thu 4/5 | 20. Markov Chains | Some notes Example | |
| Week 12 | Tue 4/10 | 21. Markov chains and stationary distributions | Some notes Example |
| Thu 4/12 | 22. HMMs and the Viterbi algorithm | Rabiner tutorial on HMMs, sections I, II, and III(b) Viterbi example | |
| Week 13 | Tue 4/17 | 23. Introduction to deterministic finite state automata | Rosen 12.3, 12.4 Notes Also, Sipser Introduction to the Theory of Computation 1.1 |
| Thu 4/19 | 24. Nondeterministic finite automata |
Notes
Rosen 12.3 Sipser, Introduction to the Theory of Computation 1.2 | |
| Week 14 | Tue 4/24 | 25. 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/26 | 26. Equivalence of finite automata and regular expressions | Rosen 12.4, Sipser 1.3 | |
| Week 15 | Tue 5/1 | 27. Turing Machines and the halting problem | Sipser 3.1, 4.2 | Thu 5/3 | 28. Course summary | Slides |
Grading:
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.