The University of Michigan, Fall 2023
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.
| Nikhil Bansal <bansaln@umich.edu> |
| Michał Dereziński <derezin@umich.edu> |
| Ben Fish <benfish@umich.edu> |
| Seth Pettie <pettie@umich.edu> |
EECS 376 lectures and discussions sections will be live.
All dates and times in this course are with respect to Ann Arbor (Eastern) time.
Lectures are offered in person, and lecture slides will be posted the same day as the lecture. You may attend any of the 5 lectures; we do not take attendance. Lectures will not be recorded.
Discussions will be held in person on various times on Thursdays and Fridays. You may attend any discussion section, subject to space availability and social-distancing requirements. We do not take attendance in discussion.
Homework assignments should be turned in electronically to Gradescope.
Exams will be held in person. Refer to the course schedule for exam dates and times.
Office hours will be held primarily in-person. Some office hours will be available on Zoom.
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. mathematical) 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.
EECS376-F23-staff@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, 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 twelve weekly assignments. Assignments are due at 8pm Eastern Time on Wednesdays, unless stated otherwise. We will accept submissions until 9:59pm on the due date without 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.
We understand that you may be unable to finish a homework assignment in time due to medical procedures, unplanned sickness, or family emergencies. Your two lowest homework scores are dropped and will not influence your final grade.
To obtain full credit on a problem, your response must be clear, concise, and correct. It is not sufficient that a correct argument appear somewhere in the answer, if it is also accompanied by incorrect or faulty reasoning.
Assignments consist of several questions intended to give you practice on applying the concepts covered in lecture, as well as to build and evaluate your understanding of the material.
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 |
If you are unsure about what constitutes an Honor Code violation, please contact the course staff with questions.
Your final grade is computed from a weighted average of homework assignment grades, exam grades, and returning a receipt that you submitted course evaluations.
| Assignment | Weight |
|---|---|
| Homework assignments | 40% |
| Midterm exam | 29% |
| Final exam | 30-31% |
| Course evaluations | 0-1% |
| Total | 100% |
We encourage you to complete the course evaluations, as they help us improve the course and CSE as a whole. For each evaluation, 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 you submit no course evaluation receipt, your final exam will count for 31% rather than 30%.
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 these thresholds, but only in your favor.
Your letter grade will be determined by your total weighted score. The exact thresholds between letter grades will be set at the end of the semester. We may adjust the following thresholds, but only in your favor.
| Total Weighted Score | Letter Grade |
|---|---|
| ≥55% | C or better |
| ≥76% | B or better |
| ≥93% | A |
If you score 55% overall, and your weighted exam average is above 45%, you will pass the course with a C or better.
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:
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.
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.
While we try to do our best to plan ahead, unfortunately, sometimes circumstances do arise that necessitate a policy change. When this happens, the change will be announced, and this document will be updated with the new policy.