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 20 | Homework #6 is due Thursday Dec. 4. You can download it from CMS. |

– Nov 18 | The final exam is scheduled for Thursday December 11, 7:00-9:30PM, in 205 Upson. |

– Nov 6 | Homework #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/28 | 1. Course introduction, set theory | Rosen ch 2.1-2.2 Notes on set theory |

Week 2 | Tuesday 9/2 | 2. Probability and counting | Rosen ch 5 Some notes Some examples |

Thursday 9/4 | 3. Conditional probability, Bayes' theorem | Rosen ch 6.1-6.2 Some notes | |

Week 3 | Tuesday 9/9 | 4. Bayes' theorem, expected value, variance | Rosen ch 6.2, 6.3 Some notes Some more notes |

Thursday 9/11 | 5. Applications of Bayes' theorem | Rosen ch 6.3 A plan for spam Slides | |

Week 4 | Tuesday 9/16 | 6. Binomial and normal distribution | Rosen ch 6.4 |

Thursday 9/18 | 7. Exponentials and logarithms | Some notes | |

Week 5 | Tuesday 9/23 | 8. Graph theory | Rosen ch 9.1-9.4 Some notes |

Thursday 9/25 | 9. Eulerian and Hamiltonian circuits | Rosen ch 9.5 Some notes | |

Week 6 | Tuesday 9/30 | 10. Trees, planarity | Rosen ch 9.7, 10.1-10.2 Some notes |

Thursday 10/2 | 11. Colorings, graph algorithms, spanning trees | Rosen ch 9.6, 10.3-10.4 Some notes Slides | |

Week 7 | Tuesday 10/7 | 12. Graph algorithms | Rosen ch 9.6, 9.8, 10.4-10.5 Slides |

Thursday 10/9 | 13. More graph algorithms | Slides | |

Week 8 | Tuesday 10/14 | Fall break | |

Thursday 10/16 | 14. Applications of graphs | Who is the best connected scientist? Collective dynamics of small-world networks Could it be a Big World After All? Slides | |

Week 9 | Tuesday 10/21 | 15. Prelim review | |

Thursday 10/23 | Midterm exam (in class) | ||

Week 10 | Tuesday 10/28 | 16. Applications of graphs: social networks and the web | 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) |

Thursday 10/30 | 17. PageRank, other applications of eigen decomposition | Slides 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/4 | 18. Introduction to finite state automata | Some notes
Rosen 12.3 Kozen, Automata and Computability, ch 2, 3
(available in Engineering library) |

Thursday 11/6 | 19. Regular languages, product construction | Rosen 12.3 Kozen ch. 11 | |

Week 12 | Tuesday 11/11 | 20. Nondeterministic finite automata | Rosen 12.3 Kozen ch. 5, 6 |

Thursday 11/13 | 21. Regular expressions | Rosen 12.4 Kozen ch. 7, 8 | |

Week 13 | Tuesday 11/18 | 22. Regular expressions, applications of FSAs | |

Thursday 11/20 | 23. Markov Chains | Some notes More notes Durbin excerpt (handed out in class) Markov chain example | |

Week 14 | Tuesday 11/25 | 24. HMMs, the Viterbi algorithm | Some notes Viterbi example Rabiner tutorial on HMMs, sections I, II, and III(b) |

Thursday 11/27 | Thanksgiving break | ||

Week 15 | Tuesday 12/2 | 25. Applications of markov models | Russel & Norvig, "Artificial Intelligence", section 24.7 (on speech recognition) (available in Engineering library) |

Thursday 12/4 | 26. 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.