Announcements

  • Quizzes (1-2) are returned in Gradescope.

  • Lab feedback is available in github (labs 0-3).

  • Read about the end-of-semester projects.

  • Quiz 2 covered standards P2, P5, and C8. If you are "in progress" on any of those standards (see your grade repo), you can schedule a retake sometime Oct 6-10. You will be able to keep retaking quiz questions (once per week) on any standard you have not yet achieved. I recommend that you study before attempting a retake, in order to figure out how to fix your mistakes.

  • Quiz 3 will cover standards P3 (difficult probability questions), C9 (uniquely decodable codes), and C10 (instantaneous codes).

  • Link to this week’s schedule.

Meeting times and office hours

  • Lecture: Sci 204, MW 9:00am - 10:15am

  • Lab: Martin 327, T 2:45pm - 4:15pm

  • Office hours: Martin 210, Thursdays 12:30pm - 2:30pm, or email me or schedule an appointment

  • Ika hours: drop-in (anytime the door is open) Martin 210

Ika

Textbook

There are no required readings for this class. However, there are suggested readings that reinforce lecture material and provide more context.

  • A Computational Introduction to Number Theory and Algebra by Victor Shoup. We will only use self-contained chapter 8 on discrete probability.

  • Information and Coding Theory by Gareth A. Jones and J. Mary Jones. On reserve in Cornell Library.

  • Elements of Information Theory by Thomas M. Cover and Joy A. Thomas. On reserve in Cornell Library.

Course overview

This course provides an introduction to the mathematical tools used to design and analyze communication. How do we design systems to send and receive messages? Can we send clear messages concisely? How does the context of a message help us design efficient communication schemes? Can we correct errors if they are introduced mid-transmission? Topics covered include noisy channels, eavesdroppers, correctness proofs, finite probability distributions, information theory, entropy, and NP-completeness.

Prerequisites: CPSC 35 is required. Mathematics at the level of Linear Algebra or higher is also required.

structure

  • Lectures. Class meeting times will cover course concepts in depth, including activities to practice concepts and facilitate student discussion.

  • Readings. There are no required readings, but suggested readings will reinforce lecture material and provide additional context.

  • The course forum on EdStem is where you can post questions and see continued discussions about course content.

  • Labs. Lab problems will provide practice opportunities to work with the concepts from lecture, develop understanding, and identify points of confusion. Individual lab exercise write-ups will be due one week after each lab meeting.

  • Quizzes. Every two weeks, there will be a quiz during lab, covering new and old material. The quizzes provide opportunities to complete standards. Re-attempts will be offered in non-quiz weeks.

  • Final project. You will develop a final project that explores and analyzes a topic from the class, or a topic at the intersection of course content and an area of your interest.

expectations

  • Attendance contributes to your learning but does not directly affect your final grade. You are encouraged to attend.

  • Quizzes directly affect your final grade, but retakes are allowed.

  • Labs contribute to your learning but only slightly affect your final grade.

  • Late submissions are not allowed.

grading

The goal of the course is for students to increase their understanding of the theory behind communication, and improve their skills at analyzing and proving claims about communication in many different contexts.

Final grades will be determined by number of standards achieved. Read the detailed grading standards and policies.

Schedule

The following is a tentative course calendar. It may change as we progress through the semester.

WEEK DAY ANNOUNCEMENTS TOPIC & READING LABS
1

Sep 03

  

Course Introduction

  • syllabus
  • probability definitions and basics

Reading: Shoup 8.1

Lab 0: Optimizing "Guess Who?"
2

Sep 08

(lecture cancelled)

Discrete probability

  • independence
  • conditional probability
  • rigorous proofs and arguments

Reading: Shoup 8.2

Lab 1: probability (fun)

Sep 10

  
3

Sep 15

Drop/Add Ends

Quiz 1 (Sep 16)

Codes

  • block codes
  • uniquely decodable

More probability (as needed)

  • expectation
  • linearity of expectation

Reading: Shoup 8.3, Jones and Jones 1.1-1.2

Lab 2: building good codes

Sep 17

  
4

Sep 22

  

Codes

  • prefix and instantaneous codes
  • Kraft's inequality
  • McMillan's inequality

Huffman codes

  • definition
  • construction
  • analysis

Reading: Jones and Jones 1.3-2.5, Cover and Thomas 5.1-5.8

Lab 3: Unique decodability, fixing bad codes, building good codes

Sep 24

Quiz 1 retakes (Sep 25)
5

Sep 29

Quiz 2 (Sep 30)

Huffman codes

  • optimality
  • entropy

Shannon-Fano codes

  • definition
  • analysis
  • construction
  • comparison with Huffman codes

Reading: Jones and Jones 3.1-3.4, Cover and Thomas 2.1-2.4

Lab 4: Huffman codes
start brainstorming project ideas

Oct 01

  
6

Oct 06

  

Shannon's First Theorem

  • entropy
  • Shannon's First Theorem
  • sequences of codes

Lab 5: Optimizing and entropy

Oct 08

Quiz 2 retakes (Oct 09)

Preliminary project proposals due (Oct 10)
 

Oct 13

Fall Break

Oct 15
7

Oct 20

Quiz 3 (Oct 21)

NP-completeness

  • we have to cover this
  • connections to communication
  • let's study a standard CS theory topic in the style of coding theory!

Lab 6: verifiers and NOT solving problems yourself

Oct 22

  
8

Oct 27

  

Errors

  • What if the channel introduces errors?
  • revisit all previous codes and re-analyze
  • matrices become relevant in a BIG way
  • probability theory returns: conditional probability and mutual information
  • sequences of codes, but in a headache way
  • Shannon's Theorem (fundamental theorem of information theory)

Lab 7: NP-completeness

Oct 29

Quiz 3 retakes (Oct 30)

Final topic proposal due (Oct 31)
9

Nov 03

Quiz 4 (Nov 04)

Lab 8: mutual information and joint entropy

Nov 05

Last Day to Declare CR/NC (Nov 07)
10

Nov 10

  

Erasure

  • What if the channel erases symbols?
  • all hope is not lost

Lab 9: when codes make mistakes

Nov 12

Quiz 4 retakes (Nov 13)

Project outline due (Nov 14)
11

Nov 17

Quiz 5 (Nov 18)

Error-correcting codes

  • if we want to go there, this can be as mathematical as humanly tolerable

Lab 10: erasure isn't SO bad

Nov 19

  
12

Nov 24

Quiz 5 retakes (sometime before Thanksgiving break) (Nov 25)

other extension topics

  • cryptography (viewed through information theory)
  • Komolgorov complexity
  • Hadamard matrices and linear codes
  • once you see the world as information theory, it's information the whole way down

Lab 11

Nov 26

  
13

Dec 01

Quiz 6 (Dec 02)

Communication Complexity

  • definition
  • model
  • relation to codes
  • complexity

Lab 12

Dec 03

Project written paper due
14

Dec 08

  

Presentations

  • Project presentations.
  • Course review

 

Dec 10

Quiz 6 retakes (Dec 11)

Academic Integrity

The spirit of this policy is that actions which shortcut the learning process are forbidden while actions which promote learning are encouraged. Studying lecture materials together, for example, provides an additional avenue for learning and is encouraged. But using a solution you did not develop yourself is prohibited because it avoids the learning process entirely. It is your responsibility to know what is permissible and what is not. Here is the detailed academic integrity policy. If you have any questions or doubts, please contact your instructor.

Academic Accommodations

If you believe you need accommodations for a disability or a chronic medical condition, please visit the Student Disability Services website for details about the accommodations process. Since accommodations require early planning and are not retroactive, contact Student Disability Services as soon as possible. You are also welcome to contact a member of the course staff privately to discuss your academic needs. However, all disability-related accommodations must be arranged, in advance, through Student Disability Services.

For details about the accommodations process, visit the Student Disability Services website.

To receive an accommodation for a course activity, you must have an official accommodation letter from the Office of Student Disability Services and you need to meet with course staff to work out the details of your accommodation at least two weeks prior to the activity.