**Content**: Information theory studies the transmission, processing, extraction, and utilization of information. This course covers the basic theory of information theory and selected applications to data management, machine learning and information retrieval. Topics include entropy, mutual information, cross entropy, data processing theorem, information inequalities, cox' theorem, maximum entropy solutions, and applications such as data normalization, decision trees, maximum likelihood, logistic regression, cross-entropy, VC dimensions.
Students will gain hands-on experience through a project. The latter will be flexible, allowing students to explore information theory in aspects related to their PhD research.

- PART 1: Covers the basic mathematical framework behind entropy and its various forms.
- PART 2: Covers the axiomatic approach from multiple angles: a few simple principles (axioms) leading to entropy or the laws of probability up to factors. Starting from a list of postulates leading to particular solution is a powerful approach that has been used across different areas of computer science (e.g. how to define the right scoring function for achieving a desired outcome)
- PART 3: Covers example applications of basic ideas from information theory to practical problems in data management, machine learning, and information retrieval. Topics and discussed papers may vary over years.

**Prerequisites**:
The course is fast-paced but self-contained. Standard undergraduate CS knowledge of probability theory (e.g., random variables, basic probability distributions, expectation, etc.), algorithms and complexity theory (e.g., from textbooks such as
[Ericson'19],
[Dasgupta, Papadimitriou, Vazirani'06],
[Cormen, Leiserson, Rivest, Stein'09],
[Kleinberg, Tardos'05], or
[Lehman, Leighton, and Meyer'15]) will be helpful

**PhD program**:
The course counts as "non-seminar" Theory course for the PhD breath requirement.

**Time/location**

- Lectures: Mon/Wed 2:50pm - 4:30pm, Ell Hall 410, in person. Classes will not be recorded, but all slides from class (if available, sometimes we just work on the whiteboard) will be made available within 2 days after each lecture, either on this course web page or from within Piazza.
- Office hours: directly after class, or by appointment in person at 450 West Village H, or via Microsoft Teams or Zoom. Please email the instructors with 3 time slots possible for you.

**Instructors**:
Wolfgang Gatterbauer,
Javed Aslam

**Contact**:
Please use Piazza (via direct access from within
Canvas)
for all questions related to lectures, coursework, and the project. Notice you can post questions anonymously to all other students, or anonymously even to the instructors.
Alternatively, please use our anonymous feedback form to send anonymous comments that only the instructors can see.

**50%: Course project**:
The main component of this course will be a research project in the latter part of this class.
This project can be a new application of one of the techniques presented or theoretically-oriented.
The topic will be flexible, allowing students to explore scalable data management and analysis aspects related to their individual PhD research.
This will involve an initial project proposal, an intermediate report, a project presentation and a final report.
The final report should resemble a workshop paper, and will be evaluated on the basis of soundness, significance, novelty, and clarity. Deliverables and dates are posted on the project page.

**35%: Flipped class scribes**:
Students take turns in "illustrating" 7 lectures (to be consistent with standard notation we refer to it as "scribes").
Graduate theory classes often ask students to scribe the lecture content.
However, we change the rule of the game.
Rather than scribing (= repeating and summarizing) the content of the class, we ask you to *"illustrate" some interesting aspect in the covered topics with imaginative and ideally tricky illustrating examples*.
Those illustrations are great if they in turn can help other students practice and solidify their understanding of the topics discussed.
Please start either from our PPTX template or use your own template (as long as you include slide numbers),
and submit it as PDF to Canvas, naming it "cs7840-fa24-[YOUR NAME]-scribe[NUMBER]-[SOME DESCRIPTIVE TITLE].PDF".

Justification: Georg Cantor is quoted as saying: "To ask the right question is harder than to answer it." In that spirit, our class scribes are closer to research than assignments: What particular aspect in a class is worthy to be "illustrated"? That's already part of the question. Scribes are done in PowerPoint and are due 1 week after class at midnight (Mon for Mon classes, Wed for Wed classes). They can be done individually or in teams of two (if you work in teams of two, you are expected to illustrate 14 classes instead of 7 classes). For some more pedagogic motivation see videos by Tim Brown on asking questions and reframing problems being key to creativity, Dan Meyer on formulating problem being more important than just solving them, Derek Muller on increasing learning by including possible misconceptions into stories, a blog post on example-based reasoning, and an older text of mine of the educational value of temporarily misleading the spectator before giving the correct answer.

Procedure:

- Optional (but strongly suggested) preliminary submission on Piazza: You can post your first draft of each assignment as PDF to Piazza. If you prefer, you can make your post anonymous to other students (please then simply remove the title page). The instructors will post comments on each submission on Piazza for you and everyone else to see. You may decide to address our feedback in your final submission to Canvas. By posting it visible to other students, both your document and also my feedback may also be helpful to other students. Notice that submitting the preliminary version to Piazza extends the deadline for submitting on Canvas.
- Final submission on Canvas: Submit your final version to Canvas. Please notice that a scribe can be submitted on a given class topic until maximally 7 days after the slides for that class topic are posted (your earlier submission date counts, either for the preliminary on Piazza, or the final on Canvas)

**15%: Class participation**:
Classes will be interactive and require concentration and participation of the students.
We are a big fan of the Socratic Method (video clip from the 1973 movie "The Paper Chase").
Participate when we discuss the merits or shortcomings of algorithms, or when we have small group break-out sessions with exercises.
Ask questions, during class or on Piazza. Questions that make us ponder or create new illustrating examples are all great examples of class participation.
Also, *never* hesitate to point out to us any errors you spot in the slides, even if minor. You can post anonymously to the other students on Piazza (and even anonymously to the instructors, though then we would not be able to associate you with your greatly appreciated participation).
Also, don't hesitate to point out to us any interesting links to interesting related material. It can only count towards class participation.
Finally notice that while the class provides extensive readings for those interested, these pointers are almost exclusively optional (unless otherwise stated in class).

Recommended textbook: Thomas Cover. Elements of Information Theory, 2nd ed, 2006. Additional material (like papers and selected chapters) are made available on the calendar page.

Earlier versions of this course were taught by Javed Aslam in Fall 2015 and Fall 2011. The pedagogy of this class is inspired by 7240: Principles of scalable data management taught by Wolfgang Gatterbauer.