CSE 445/545 (Coding Theory) Syllabus

Spring 2023

Mondays, Wednesdays and Fridays, 4:00-4:50pm, Cooke 121.

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 the 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.

Policy on improper distribution of course materials

All materials prepared and/or assigned by me for this course are for the students’ educational benefit. Other than for permitted collaborative work, students may not photograph, record, reproduce, transmit, distribute, upload, sell or exchange course materials, without my prior written permission. "Course materials" include, but are not limited to, all instructor-prepared and assigned materials, such as lectures; lecture notes; discussion prompts; study aids; tests and assignments (and their solutions); and presentation materials such as PowerPoint slides, Prezi slides, or transparencies; and course packets or handouts. Public distribution of such materials may also constitute copyright infringement in violation of federal or state law. Violation of this policy may additionally subject a student to a finding of "academic dishonesty" under the Academic Integrity Policy and/or disciplinary charges under the Student Code of Conduct.

For more details, please see the department policy on academic integrity (graduate version).

COVID-19

COVID-19 related policies and guidelines

Please follow UB/SUNY protocols regarding COVID-19. This page has an overview of updates and policies .

Specifically, please note the following parts of the Student Compliance Policy for COVID-19 Public Health Behavior Expectations :

  • Students are required to stay home if they are sick.
  • Should a student need to miss class due to illness, isolation or quarantine, they are required to notify their faculty to make arrangements to make up missed work.
    • Atri's note: Please note though that since we drop the lowest two homeworks, there will be no extension/makeup for late homeworks (unless there is some unforeseen circumstances that prevents you participating for more than a two week stretch in which case please contact Atri to see if something can be worked out).

Lectures will be held in-person. Office hours will be in-person (for some of them you can join by zoom). These are subject to change based on current UB/SUNY policies.

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.

TA Information

Here is your wonderful TA!

Ben Siegel

  • : brsiegel "at" buffalo "dot" edu
  • : Wednesdays and Fridays, 1:00-1:50pm
  • : Salvador Lounge

Ben

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 (iii) 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—3 credits. For CSE 545—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 $50\%$
Homeworks $50\%$
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 for CSE 545:

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

Below is the tentative cutoffs for the letter grades for CSE 445:

GradeQuality PointsPercentage
$A$ 4.0 85.0% -100.00%
$A^-$ 3.67 75.0% - 84.95%
$B^+$ 3.33 70.0% - 74.95%
$B$ 3.00 65.0% - 69.95%
$B^-$ 2.67 60.0% - 64.95%
$C^+$ 2.33 55.0% - 59.95%
$C$ 2.00 50.0% - 54.95%
$C^-$ 1.67 45.0% - 49.95%
$D^+$ 1.33 40.0% - 44.95%
$D$ 1.00 35.0% - 39.95%
$F$ 0 34.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 Ben (CSE 445 HW submissions) and me (all the other submissions) 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 EXACTLY 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

Project grade split and cap

$50\%$ of the score for the mini-project will be the same for everyone in the same group (this is the group score. The rest of the $50\%$ of the grade will be the group score weighted by a multiplier based on peer review of the group (based on a survey).

The way the survey part is setup, technically someone can get more than $100\%$ on the mini-project. In such a case the maximum score will be capped at $105\%$.

Group score details

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

Mini Project Component $\%$ of grade
Team registration $1\%$
Topic registration $4\%$
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.

Survey part of the project

Survey Details

Each group member will fill in a survey rating their own and their other group member's contribution to the project under the categories of team role, leadership, participation, professionalism and quality of work (on scale of $0-3$ on each). These scores will then be used to divide the team’s points so that individual students’ survey grades reflect how well they contributed to the overall result. The table below explains what the different numerical values for various categories mean.

Category0 points
(Unsatisfactory)		1 points
(Developing)		2 points
(Satisfactory)		3 points
(Exemplary)
Role Does not willingly assume team roles;
Rarely completes assigned work		 Usually accepts assigned team roles;
Occasionally completes assigned work		 Accepts assigned team roles;
Mostly completes assigned work		 Accepts all assigned team roles;
Always completes assigned work
Leadership Rarely takes leadership role;
Does not collaborate;
Sometimes willing to assist teammates		 Occasionally shows leadership;
Mostly collaborates;
Generally willing to assist teammates		 Shows an ability to lead when necessary;
Willing to collaborate;
Willing to assist teammates		 Takes leadership role;
Is a good collaborator;
Always willing to assist teammates
Participation Often misses meetings;
Routinely unprepared for meetings;
Rarely participates in meetings and does not share ideas		 Occasionally misses or does not participate in meetings;
Somewhat prepared for meetings;
Offers unclear or unhelpful ideas in meetings		 Attends and participates in most meetings;
Comes prepared to meetings;
Offers useful ideas in meetings		 Attends and participates in all meetings;
Comes prepared to meetings;
Clearly expresses well-developed ideas in meetings
Professionalism Often discourteous and/or openly critical of teammates;
Does not want to listen to any alternate perspectives		 Not always considerate or courteous towards teammates;
Usually appreciates teammates' perspectives, but often unwilling to consider them		 Mostly courteous to teammates;
Values teammates' perspectives and often willing to consider them		 Always courteous to teammates;
Values teammates' perspectives, knowledge, and experiences, and always willing to consider them
Quality Rarely contributes to the video and report components of the project;
Others often required to revise, debug, or fix their work		 Occasionally contributes to the video and report components of the project;
Others sometimes needed to revise, debug, or fix their work		 Often contributes to the video and report components of the project;
Others occasionally needed to revise, debug, or fix their work		 Frequently contributes to the video and report components of the project;
Others rarely needed to revise, debug, or fix their work

Submitting the survey

The peer evaluation survey will have to be filled on https://cse.buffalo.edu/teamwork . You will evaluate yourself and your group mates in all the five categories.

The workflow

  1. Between 11:00am on Saturday May 6, 2023 and 11:59pm on Sunday May 14, 2023 the website above will be ready for you.
  2. Log in with your UB login credentials.
  3. You will then fill in the survey: the website will ask you to evaluate yourself and your group mates in all the five categories above.
  4. Your part is done. Atri will use your survey responses and your group score to calculate your survey project score.

Survey part of the mini project grade

Your survey scores will be converted into a fractional score $\rho\in [0,2]$. We will reveal the exact algorithm after the surveys are submitted, but roughly, if everyone in the group did equal work (as reflected by the survey responses), then all group members will have $\rho=1$. Otherwise, those that did more work will have a $\rho$ value closer to $2$ and those that did less will have a $\rho$ value closer to $0$.

The survey part of the grade will be calculated as $\rho\cdot$group score.

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

Homeworks

Homeworks will be released on Wednesdays 11:59pm on the CSE 4/545 web page and will be due via Autolab by 11:59pm next Wednesday. (In fact all CSE 4/545 submission except the YouTube video and survey are due by 11:59pm on a Wednesday.) In addition, there will be a Homework $0$, which will be partially 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 a 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.)

HW drop policy

$50\%$ of the letter grade will depend on the homeworks, which will be calculated out of $200$ as the best two out of the following three scores (each out of a total of $100$):

  1. HW 1 $+$ HW 2
  2. HW 3 $+$ HW 4
  3. HW 5 $+$ HW 6

Not all homeworks will require the same amount of work

HWs 1-6 will have one problem each (though some of them might have sub-parts). The odd numbered HWs will be worth less points than the even numbered HWs.

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!)

More rules will be stated on the homeworks

More details on what sources are allowed (in short only four sources are allowed: the text book, piazza, lectures (including any notes you might have taken during the lecture) and material on the website) as well as limits on how long the submissions can be will be released with the homeworks.

All homeworks assess student learning outcomes (6).

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, : 716-645-2608, TTY: 716-645-2616, : 716-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.

Critical Campus Resources

Sexual Violence

UB is committed to providing a safe learning environment free of all forms of discrimination and sexual harassment, including sexual assault, domestic and dating violence and stalking. If you have experienced gender-based violence (intimate partner violence, attempted or completed sexual assault, harassment, coercion, stalking, etc.), UB has resources to help. This includes academic accommodations, health and counseling services, housing accommodations, helping with legal protective orders, and assistance with reporting the incident to police or other UB officials if you so choose. Please contact UB’s Title IX Coordinator at 716-645-2266 for more information. For confidential assistance, you may also contact a Crisis Services Campus Advocate at 716-796-4399.

Mental Health

As a student you may experience a range of issues that can cause barriers to learning or reduce your ability to participate in daily activities. These might include strained relationships, anxiety, high levels of stress, alcohol/drug problems, feeling down, health concerns, or unwanted sexual experiences. Counseling, Health Services, and Health Promotion are here to help with these or other issues you may experience. You can learn more about these programs and services by contacting:

Counseling Services

120 Richmond Quad (North Campus), 716-645-2720

Health Services

4350 Maple Road (at Sweet Home Rd.) , 716-829-3316

Health Promotion

114 Student Union (North Campus), 716-645-2837

Preferred Name

If you would like to be addressed by a name that is different from the one in UB records, please let us 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 (all submission will be online so this issue should not come up but please let us know if this is not the case for you).

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 .