CSE 445/545 (Coding Theory) Syllabus

Spring 2019

Tuesdays and Thursdays, 12:30-1:50pm, Norton 216.

Please note

It is your responsibility to make sure you read and understand the contents of this syllabus. If you have any questions, please contact the instructor.

Academic Integrity

Penalty for academic integrity violation

In accordance with the current departmental policy on academic integrity violations, we will follow this procedure in CSE 4/545:

  1. If the violation is the student's second academic violation, then it will result in an automatic F letter grade in the course.
  2. If the violation is the first ever academic violation, then it will result in a minimum of a letter grade reduction in the grade for course and zero in the relevant assignment. If the violation is serious enough, then it can result in an F in the course. While it gives me no pleasure in failing students, I will do so since I have to be fair to (the vast majority) of students who do not cheat.

For more details, please see the department policy on academic integrity , as well as the UB UG Academic Integrity policy .

Instructor Information

Atri Rudra

It is preferable to set up an appointment (by email) if you want to talk to me outside of my office hours. However, you can drop by if my office door is open.

Recitations

If you are registered in CSE 445, you will also be registered in the Tuesdays 2-2:50pm recitation section, which will be held as an office hours in Davis 319. Traditionally this course has not had a recitation section and starting Fall 2019, CSE 4xx courses will no longer have a 1-credit recitation. Also given the small class size, an office hour style recitation is more effective.

Course Description

(From the course catalog )

Error correcting codes (or just codes) are systematic ways of introducing redundancy into data so that the original information can be recovered even when the data is corrupted. Codes are used ubiquitously in communication systems and data storage. The study of error correcting codes (or coding theory) started with the seminal works of Shannon and Hamming in the late 1940s and has been an active cross-disciplinary research area since then. This course will discuss the theoretical aspects of codes and will focus mostly on the worst-case noise model pioneered by Hamming. However, we will discuss quite a few results on the stochastic noise model pioneered by Shannon. The course will roughly cover three parts: (i) combinatorial aspects of codes, i.e. the limit of what can and cannot be achieved with codes; (ii) computationally efficient algorithms for using codes; and (ii) application of codes in theoretical computer science. Major developments in coding theory since the 1990s will be emphasized.

CSE 445 and CSE 545 are dual-listed.

Credits

For CSE 445—4 credits (Lectures: 3 credits, Recitation: 1 credit). For CSE 545—3 credits (Lectures: 3 credits, no recitation). Starting Spring 2020, CSE 445 will move to 3 credits.

Pre-requisites

CSE 445: CSE 331 .

CSE 545: There is no specific course pre-requisite for CSE 545. However, some “mathematical maturity" will be essential. In particular, comfort with basics of linear algebra (vector spaces, basis, dual spaces); finite fields, field extensions and polynomials over finite fields; elementary probability; analysis of algorithms; and (some exposure to) computational complexity will be useful. Some of these topics (for example finite fields) can be learned on a need to know basis as the course progresses. Email the instructor if you have any questions on the pre-requisites.

(ABET ) Learning Outcomes

CSE 445 and 545 are electives and after the completion of the course, students should demonstrate mastery of the concepts/skills/knowledge expressed in the following ABET learning outcomes for computer science:

Course Learning Outcome Program Outcomes / Competencies Instructional Method(s) Assessment Method(s)
Be able to apply coding theory to contexts beyond communication ABET (6) Lectures Homeworks, Mini project
Be able to use various bounds on tradeoffs involved in communication ABET (6) Lectures Homeworks
Be able to understand and analyze proofs related to coding theory ABET (6) Lectures Homeworks
Be able to understand use of coding theory in new contexts ABET (6) Lectures Homeworks, Mini project

The Student Outcomes from the Computing Accreditation Commission (CAC) of ABET have been adopted .

Program Outcome Support (Computer Science ABET Outcomes):

Program Outcome123456
Support LevelNo coverageNo coverageNo coverageNo coverageNo coverageDemonstrate mastery of skill/concept

References

Textbook

We will follow draft of a book titled Essential Coding Theory that I am writing with Venkat Guruswami and Madhu Sudan .

The basic material on codes that we will discuss in initial lectures can be found in many textbooks (some of the standard ones are listed below), but the recent algorithmic developments and applications in computer science are not covered in any of these:

Schedule

A more detailed schedule appears here.

Piazza

We will be using Piazza for all CSE 4/545 related announcements. If you are attending the course, you must check Piazza regularly. I would strongly urge you to enable email notifications on piazza (it is on by default). These announcements will include the ones that inform if and when classes/office hours are re-scheduled etc.

There will be an entry for each lecture and homework. Sometimes, the entries may include side comments or stories that I feel are relevant to the course (but are not directly related to the lectures).

We will also be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com. To familiarize yourself with the system, look at their help page .

You will need to sign up for Piazza. To do so, go to the sign up page .

Few other points:

  1. You can post anonymously but note that you will be anonymous to students only. Your identity will be known to me.
  2. Please make sure that you use your UB email to sign up-- this is to make sure that I can verify your identity if necessary.
  3. You can write posts that are private to just the instructors but if we feel that the answer would be relevant to the class then we reserve the right to make the post public. (If you would like not to have your name in the public version of your private post, please post anonymously in the private post too. Note by the first point, we will still know your identity.)

Grading Policy

Here is the split of grades:

Course Component $\%$ of grade
Mini project $40\%$
Homeworks $30\%$
Proof Reading $30\%$
See the next few sections for more details on each of the above components.

Letter Grades

Below is the tentative cutoffs for the letter grades:

GradeQuality PointsPercentage
$A$ 4.0 90.0% -100.00%
$A^-$ 3.67 80.0% - 89.95%
$B^+$ 3.33 75.0% - 79.95%
$B$ 3.00 70.0% - 74.95%
$B^-$ 2.67 65.0% - 69.95%
$C^+$ 2.33 60.0% - 64.95%
$C$ 2.00 55.0% - 59.95%
$C^-$ 1.67 50.0% - 54.95%
$D^+$ 1.33 45.0% - 49.95%
$D$ 1.00 40.0% - 44.95%
$F$ 0 39.95% or below

Changing cutoffs

I reserve the right to change the cutoffs depending on overall class performance. However, I will only move the cutoffs down. In other words, in case you are in a certain percentage range in the last column in the table above, then the letter grade in the corresponding first column is the minimum letter grade you will receive.

Incompletes

Incompletes (the grade of “I”) will not in general be given. This is reserved for the rare circumstance that prevents a student from completing the work in the course. University and Department policy dictates that an “I” can be given only if both of the following conditions are met: (i) only a small amount of work remains, such as the final exam and one or two assignments, and (ii) the student has a passing average in the work completed. In such a circumstance, the student will be given instructions and a deadline for completing the work, which is usually no more than 30 days past the end of the semester. Please see the UB catalog link for more.

Grading Scheme

All submissions in this course will be graded manually by me and we will use the following "level" system. For each question/part of a homework/mini project/proof reading, the student’s submission will be graded at one of the following levels:

The description of what constitutes a certain level is a bit generic so that it applies to the different parts of the course. For each submission, we will clarify exactly what parts are expected in a submission.

Mini Project

Students will form groups of up to three (3) and each group will pick a coding theory topic and create a YouTube video that is intended for a non-expert but mathematically curious audience. (You can make the video unlisted/private.) You should submit the video link in a PDF on Autolab.

Video length

Your video can be of at most 10 minutes. You can of course submit a shorter video as long as you have all the components.

Video components

Your video should have the following parts:

  • Problem Statement You should clearly state and define the problem you are going to cover in your video.
  • Motivation You should motivate why your chosen problem is interesting. Why should a lay person care?
  • Assumed Background Specify what background is expected of the viewer. You should provide background links (ideally to other videos) in the video description that a viewer can look up in case they want to get the assumed background knowledge.
  • Solution You should show how to solve the problem in the first item.
  • References You should link to the relevant references for your video: either directly in the video or in the description.
  • At least the problem statement or the solution should be related to coding theory.

Your video should have the following components:

  • Your video should include a proof. The proof need not be super detailed: you can provide the main ideas behind the proof. Basically, you need to provide some technical ideas in the video on how your problem will be solved.
  • Your video must have at least one illustration in the video. This could be a static figure, though animations are more preferred. You are also encouraged to use visuals for both the problem statement and the solution.

    • Proper citation is a must!

    You should properly cite any source you use in your video. This should include both the reference material that you use to create the main content of the video as well as any use of figures/videos from another source. Not giving proper credit for someone else's material is considered cheating and WILL LEAD TO ACADEMIC INTEGRITY VIOLATION PROCEDURE AGAINST YOU.

    Report

    Before you submit your video, you will have to submit a report in PDF format which must be no more than two (2) pages (excluding the references). The idea behind the report is for me to give y'all some feedback before your group goes ahead and makes the video. Towards this end, your report must address the following:

    Report components

    • Description of the problem you will be considering in your video.
    • Why is the problem interesting? I.e. what is the motivation of your problem? In particular, why should a non-expert care about the problem?
    • Description of the solution of your problem from the first item.
    • What proof(s) will your video cover?
    • What figures/animations will you include in your video? Just a short description is enough: the actual figures/animations are not needed.
    • What are the references that you will use? (Recall the list of references does not count towards the 2 page limit.)
    • What (mathematical) background will you be expecting from viewers of your video?
    • What part of the video will each group member work on? This includes both the research needed into the technical material that will go into the video as well as the actual process of creating the video.

    You are allowed to deviate a bit from what you say in this document in your final video. This document is supposed to me more of a guideline so that I can make sure your video has the right feel to it.

    Deadlines

    To ensure a timely completion of this part of the course, you will have to follow these deadlines:

    Project Grade Distribution

    Everyone in the group gets the same score

    The grade for the mini-project will be the same for everyone in the same group.

    Here is the split of grades for the mini-project:

    Mini Project Component $\%$ of grade
    Team+topic "registration" $5\%$
    Report $25\%$
    Video $70\%$

    Report grading rubric

    Here is the split of grades for the various parts of the report (for a total of 100 points):

    • Problem Description: 20 points.
    • Problem Motivation: 10 points.
    • Solution: 20 points.
    • Proof coverage: 10 points.
    • Figures/Animations: 10 points.
    • References: 10 points.
    • Viewer Background: 10 points.
    • Work distribution in the group: 10 points.

    Video grading rubric

    Here is the split of grades for the various parts of the video (for a total of 100 points):

    • Problem Description: 20 points.
    • Problem Motivation: 10 points.
    • Viewer Background: 10 points.
    • Solution: 30 points.
    • Video Quality: This is a bit subjective but this include the quality of the video including how engaging it would be to a lay person. Also included in this would be the proof coverage, use of figures/animation and proper citation of references. 30 points.

    The mini-project will assess student outcome (6).

    Homeworks

    Homeworks will be released on Thursdays by 11:59pm on the CSE 4/545 web page and will be due via Autolab by 11:59pm next Thursday. In addition, there will be a Homework $0$, which will not be graded and will not count towards your final grade. Homework $0$ is just for y'all to get practice on some basic things that I will assume in the course. This will also be a great opportunity for y'all to test out Autolab. Submitting Homework $0$ is optional.

    Autolab submissions

    All homework submissions will happen on Autolab. All submissions HAVE to be in PDF. The Autolab page has some more details on its quirks. While Autolab is fairly good system it has some non-obvious behavior, which if you are not aware of can lead to loss of all points for a submission. So please make sure you familiarize yourselves with it.

    Late submissions

    No late submission will be accepted. (The entire homework schedule is on the schedule page, so please plan accordingly.)

    CSE 445 vs. 545

    If you registered in CSE 445, you only need to submit HW 1 and 2 (but not HW 3). The two homeworks will be worth $15\%$ of the total grade.

    If you are registered in CSE 545, you are supposed to submit all the three homeworks. Each HW will be worth $10\%$ of the total grade.

    Collaboration in groups of size at most three is allowed (and encouraged). However, every student is expected to do their own writeup and clearly state the names of their collaborators. More details will be provided with the homeworks.

    My homework philosophy for this course is that they are meant for you to work on stuff that I did not have time to cover in the lectures. (Don't worry: you will be provided with hints for the tougher problems!)

    All homeworks assess student learning outcomes (6).

    Proof Reading

    For each lecture, one student will volunteer to proof-read the corresponding part of the book and submit a list of corrections, passages that are not clear, some suggestions for improvement etc. Your submission should have three parts:

    I will typically ask for a volunteer at the beginning of the class. Please don’t try to flatter me by saying that the writeup is perfect :-) It certainly is not and you will be graded on the depth of your comments. Depending on the number of students in the class, each student might have to do 3-4 proof-readings. Take this as an opportunity to understand the lecture material even better!

    Submitting the proof reading

    Your submission is due as a PDF on Autolab. The submission is due by noon of the day of the next lecture. For example, the notes for Tuesday, January 19 are due Thursday January 31 by noon and the notes for Thursday January 31 are due Tuesday, February 5 by noon.

    Proof reading grading rubric

    Here is the split of grades for the various parts of proof reading (for a total of 100 points):

    • Typos: 30 points.
    • Formatting: 10 points.
    • Suggestions for Improvement: 60 points.
    • Bonus Improvements: 10 points.

    Accessibility Resources

    If you have a diagnosed disability (physical, learning, or psychological) that will make it difficult for you to carry out the course work as outlined, or that requires accommodations such as recruiting note-takers, readers, or extended time on exams or assignments, you must consult with Accessibility Resources (: 60 Capen Hall, : 645-2608, TTY: 645-2616, : 645-3116).

    You must advise your instructor during the first two weeks of the course so that we may review possible arrangements for reasonable accommodations.

    Counseling Center

    Your attention is called to the Counseling Center (: 645-2720), : 120 Richmond Quad. The Counseling Center staff are trained to help you deal with a wide range of issues, including how to study effectively and how to deal with exam-related stress. Services are free and confidential.

    Preferred Name

    If you would like to be addressed by a name that is different from the one in UB records, please let me know and we will use your preferred name in our communications with you. Further, you will be able to use your preferred name in all of your submissions.

    Diversity

    The UB School of Engineering and Applied Sciences considers the diversity of its students, faculty, and staff to be a strength, critical to our success. We are committed to providing a safe space and a culture of mutual respect and inclusiveness for all. We believe a community of faculty, students, and staff who bring diverse life experiences and perspectives leads to a superior working environment, and we welcome differences in race, ethnicity, gender, age, religion, language, intellectual and physical ability, sexual orientation, gender identity, socioeconomic status, and veteran status.

    Suggestions or Comments?

    I would be happy to get feedback from you. You can either talk/send email to me, or use piazza .