The University of Michigan, Fall 2021
An introduction to Computer Science theory, with applications. Design and analysis of algorithms, including paradigms such as divide-and-conquer and dynamic programming. Fundamentals of computability and complexity — learn to identify what problems a computer cannot solve at all, what problems are unlikely to be efficiently solvable, and how to apply approximations to such problems. Introduction to randomness in computation, including how algorithms can benefit from randomness and how to analyze randomized algorithms. Applications of computational hardness to cryptography, including specific algorithms that are essential to the internet.
| Amir Kamil <akamil@umich.edu> |
| Euiwoong Lee <euiwoong@umich.edu> |
| Seth Pettie <pettie@umich.edu> |
Our current expectation is that EECS 376 will primarily be in person this semester. However, we will support remote participation to the extent possible.
All dates and times in this course are with respect to Ann Arbor (Eastern) time.
Lectures are offered live in person, and recordings will be made available. We do not take attendance in lecture.
Discussions will be held in person. You may attend any discussion section, even if it's different than your registered section, subject to space availability and social-distancing requirements. We do not take attendance in discussion. We are planning to make recordings available.
Homework assignments will be turned in electronically to Gradescope.
Exams are expected to be held in person, except for those who have received an accommodation from the university or college. Refer to the course schedule for exam dates and times.
Office hours will be held in both in-person and remote formats.
These expectations are subject to change, depending on university and college policies and the state of the pandemic throughout the semester.
Make sure you have a laptop consistent with CAEN recommendations.
Test your internet connection with the U-M Custom Speedtest website and make sure it meets the minimum requirements for any UM service. You'll need more bandwidth if there will be multiple simultaneous users in your household.
Resources for help with computing equipment:
Every complex problem has a clear, simple and wrong solution. — H. L. Mencken
Welcome to EECS 376: Foundations of Computer Science! This course covers foundational aspects of Computer Science that will help you reason about any computing task. In particular, we are concerned with the following with respect to problem solving:
The only way to answer these questions is to construct a model and apply a proof-based (i.e. math-like) methodology to the questions. Thus, this course will feel much like a math course, but we apply the techniques directly to widely applicable problems in Computer Science.
As an example, how can we demonstrate that there is no general algorithm for determining whether or not two programs have the same functionality? A simple but incorrect approach would be to try all possible algorithms to see if they work. However, there are infinitely many possible algorithms, so we have no hope of this approach working. Instead, we need to construct a model that captures the notion of what is computable by any algorithm and use that to demonstrate that no such algorithm exists.
The main purpose of this course is to give you the tools to approach problems you've never seen before. Rather than being given a particular algorithm or data structure to implement, approaching a new problem requires reasoning about whether the problem is solvable, how to relate it to problems that you've seen before, what algorithmic techniques are applicable, whether the algorithm you come up with is correct, and how efficient the resulting algorithm is. These are all steps that must be taken prior to actually writing code to implement a solution, and these steps are independent of your choice of programming language or framework. Were we to require you to implement all the algorithms you design in this course, the workload would be far greater, and it would only replicate the coding practice you get in your programming courses. Instead, we focus on the aspects of problem solving that you have not had much experience in thus far.
The training we give you in this course will make you a better programmer, as algorithmic design is crucial to effective programming. This course also provides a solid framework for further exploration of theoretical Computer Science should you wish to pursue that path. However, you will find the material here useful regardless of which subfields of Computer Science you decide to study.
Please refer to the course schedule for a full list of topics that we plan to explore.
Passing EECS 203 and EECS 280 are all you need to be prepared for this course. Everyone who has made it through EECS 203 and 280 is able to complete EECS 376 successfully.
We use a set of course notes developed specifically for this class. Required reading assignments are listed on the schedule. We encourage you to read them in advance of lecture, but it's fine if you read them afterwards instead.
If you would like additional resources, we recommend The Nature of Computation by Cris Moore and Stephan Mertens and Introduction to the Theory of Computation by Michael Sipser (2nd or 3rd edition). The former textbook is available from the university library.
The course website links to all course resources. Please check the website regularly for updates.
We use Piazza as a collaborative discussion forum for the course, and it is the best place for technical questions, assignment updates, and policy questions. Please do not publicly post your solution; if you have a specific question about your solution, please make a private post instead. Please search the forum before posting; duplicate questions create extra work for everyone, and they make it harder for others to find answers to their questions.
eecs376f21@umich.edu reaches the full course staff.
Please reach out to us using our individual email addresses for confidential matters.
We publish important announcements and grades on Canvas. Please ensure that you can receive Canvas announcements.
We will have one midterm and one final examination. Exam dates are on the course website. Make sure to verify you can attend both exams before registering.
We are only capable of providing alternate exams for documented conflicts due to required attendance for other courses, time zone, a religious holiday, or university-affiliated athletics.
We will also work with you if you have SSD accommodations.
We will post forms for requesting alternate exams and letting us know about SSD accommodations in the first few weeks of the semester. To ensure that we can accommodate requests, we will announce a deadline for submitting the forms.
In addition to lectures, we will hold discussion sections each week. While the main goal of lectures is to introduce new concepts, discussion sections are intended to give you deeper insight into the concepts as well as some hands-on experience with exercises. Though attendance is not required, you do need to be familiar with the material covered in discussion.
Homework assignments enable you to further your understanding of the material and to put the concepts into practice. We will have eleven weekly assignments. Assignments are due at 8pm Eastern Time on Wednesdays. We will accept submissions until 9:59pm on the due date, subject to a 5% penalty. We post solutions shortly after the deadline as a form of immediate feedback, allowing you to learn from them and put what you learned into practice on the next assignment. As such, we cannot accept submissions made later than 9:59pm. However, we do drop your two lowest scores on the homework.
In addition to the standard two drops, we consider accommodations for the following reasons:
In general, we follow the same overall grading philosophy as most humanities and social science classes: an answer must be written clearly and concisely to get the point across. It is not sufficient that a correct argument appear somewhere in the answer, if it is also accompanied by incorrect or faulty reasoning. Thus, to obtain full credit, your responses must be clear, concise, and correct.
Assignments consist of progress, group, and regular questions.
Not all assignments will have every kind of question. The assignment specification will indicate the category of each question.
Outside of exams, we encourage collaboration in EECS 376, especially on concepts, strategies, and solution ideas. We encourage you to form study groups to support each other and work together according to the rules outlined below.
Unless otherwise specified in an assignment or this document, all work you submit must be your own, original work. Collaboration must not result in solutions that are identifiably similar to other solutions, past or present. If you are referencing others' work, put it in quotes! If you are directly quoting, or building on others' writing, provide a citation. See the Rackham Graduate policy on Academic and Professional Integrity for the definition of plagiarism and associated consequences. Violations of the Honor Code will be taken seriously; please see details about the Honor Code here.
The core rules for collaboration in this course are:
Further details about what constitutes acceptable collaboration are below:
| Encouraged Collaboration | Unacceptable Collaboration |
|---|---|
| Brainstorming solution ideas, e.g., whether to use a reduction for a problem and ideas about what a suitable language for the reduction might look like | Walking through an important piece of the solution step-by-step, sharing solution sketches or drafts, or otherwise directly giving away your solution to someone, whether written or verbally |
| Helping others understand the problem statement and nuances of the problem | Providing your solution as a reference |
| Sharing hints provided by the course staff | Copying solutions in whole or in part, even if the solution is modified Writing a solution for someone else, or having someone else write your solution |
| Looking at someone else's solution after the deadline (plus any grace period) to learn from it and/or provide feedback | Sharing your solution in a way that could be copied, e.g., sending answers over email or taking a picture of a solution |
Some homework assignments will have problems that are labeled as "group" that can be done in groups of size 1 to 3. We strongly encourage you to work in groups of three on these problems. Each member of the group must make significant contributions to the solution; otherwise, their name should not be on the submission. Groups may not work with other students who are not in their group on these problems. However, you may start on a group problem individually, then come together with your other group members, discuss your ideas, and collaborate on a group submission.
If you are unsure about what constitutes an Honor Code violation, please contact the course staff with questions.
While we do not consider grades to be the metric for success in this course, we do have to assign grades at the end of the semester. We will do so based on scores from homework assignments, survey participation, and two exams. The tentative point distribution is included in the following table. It is not likely that this will change, but circumstances might occur that would make changes necessary (see the Revisions section for how we handle changes).
| Assignment | Weight |
|---|---|
| Homework assignments | 40% |
| Midterm exam | 28% |
| Final exam | 30-32% |
| Course surveys | 0-2% |
| Total | 100% |
We encourage you to complete the course surveys, as they help us improve the course and CSE as a whole. For each survey, you will receive full credit if you fill it out and submit it before the deadline. Otherwise, your final exam score will count as your score for that survey. For example, if two surveys are assigned but you only submit one, that survey will count for 1% of your grade and the final exam will count for a total of 31% (30% normally plus 1% for the survey you missed).
There are no letter grades for individual assignments or exams. The final course letter grade is based on the total weighted score earned. Passing EECS 376 requires meeting the following criteria:
We may adjust thresholds in your favor.
After computing the total weighted score, we use these ranges to assign letter grades, as long as the passing threshold for exams is met. Each range is inclusive at the bottom and exclusive at the top; for example a score of 87.9% is a B+ and a score of 88.0% is an A-. We do not round scores. We may adjust thresholds in your favor.
| Total Weighted Score | Letter Grade |
|---|---|
| 0 - 40% | E |
| 40 - 48% | D |
| 48 - 55% | C- |
| 55 - 64% | C |
| 64 - 70% | C+ |
| 70 - 76% | B- |
| 76 - 82% | B |
| 82 - 88% | B+ |
| 88 - 93% | A- |
| 93 - 100% | A |
If you score 55% overall, and your weighted exam average is above 40%, you will pass the course with a C or better.
If you score at least 48% overall, but your weighted exam score is not a passing score, you will receive a C- grade.
There is no guaranteed threshold for an A+. A grade of A+ is only awarded for exceptional work at the discretion of the instructors.
Please note:
A final thought on grades: we assign grades solely based on scores on the course assignments. We do not consider grades to be a value judgment. We value everyone's participation, and we treat everyone with respect and consideration regardless of what scores or grades they obtain.
Some components of assignments and exams are graded by hand. Request a regrade via the mechanism announced for the assignment. We accept requests only to correct grading errors, not disagreement with the rubric. Your score may go up or down.
We do not accept regrade requests for automatically graded components of assignments or exams.
In all cases, regrade requests are due no later than 7 days after a grade is released unless a shorter deadline is specified.
We encourage you to attend lectures and discussion sections synchronously if possible. When participating in remote lecture, discussion, or office hours, please keep yourself muted unless you are actively talking to the other participants, so as to avoid background noise that can be distracting.
We may record course lectures and discussions and make them available to other students to facilitate their participation in this course. If you do not wish to be recorded, you can keep yourself muted during class sessions. We also record chat transcripts and make them available to students in the course. If you would like to ask a question in chat but do not want it in the recording, you can send a private chat message to the instructor, which will not show up in the recording.
Students may not record or distribute any class activity without written permission from the instructor, except as necessary as part of approved accommodations for students with disabilities. Any approved recordings may only be used for the student’s own private use.
If you think you need an accommodation for a disability, please let us know during the first three weeks of the semester. Some aspects of this course may be modified to facilitate your participation and progress. As soon as you make us aware of your needs, we can work with the Services for Students with Disabilities (SSD) office to help us determine appropriate academic accommodations. SSD (734-763-3000; http://ssd.umich.edu) typically recommends accommodations through a Verified Individualized Services and Accommodations (VISA) form. Any information you provide is private and confidential and will be treated as such.
As indicated in the General Standards of Conduct for Engineering Students, we are committed to a policy of equal opportunity for all persons and do not discriminate on the basis of race, color, national origin, age, marital status, sex, sexual orientation, gender identity, gender expression, disability, religion, height, weight, or veteran status. Please feel free to contact us with any problem, concern, or suggestion. We ask that all of us treat each other with respect.
We all experience stressors that can impact both our academic experience and our personal well-being. These may include academic pressure and challenges associated with relationships, mental health, alcohol or other drugs, identities, finances, etc.
If you are experiencing concerns, seeking help is a courageous thing to do for yourself and those who care about you. If the source of your stressors is academic, please contact us so that we can find solutions together. For personal concerns, U-M offers many resources, some of which are listed at Resources for Student Well-being on the Well-being for U-M Students website. You can also search for additional resources on that website.
We are always working hard to improve the course, our teaching methods, and the curriculum as a whole. Often, this requires using your class work for research purposes. However, we will not publish any identifying information about you or your work. For example, we may use anonymized student assignments to design algorithms or build tools to help programmers. Or we might survey responses to help us improve the course and better understand instructional techniques. If you wish to opt out, contact the course staff (eecs376f21@umich.edu) at any time up to seven days after final grades have been issued. Opting out has no impact on your grade in any manner.
While we try to do our best to plan ahead, unfortunately, sometimes circumstances do arise that motivate a policy change. When this happens, the change will be announced, and this document will be updated with the new policy.
We wish you the best of luck this semester! We will do our best to make it a positive and meaningful experience, and we hope that the course helps you in your future endeavors.