Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
ECS 20 — Discrete Mathematics for Computer Science — Course Information — Fall 2021
Lectures
I am teaching two sections of ECS 20, one running on a MWF schedule and the other on a TR schedule.- MW 10 am in Wellman 6 and F 10 am in Wellman 126 (section A) (final: Fri, Dec 10, at 8 am)
- TR 12 pm in Wellman 106 (section B) (final: Mon, Dec 6, at 1 pm)
I realize that being back in the classroom may feel strange and even scary. No doubt many of you are looking forward to it, and many are not. Under “normal” times I would structure the class to push people to consistently come to class. I believe that improves performance, builds community, and enables me to give a class that is more interactive.
But this term is anything but normal. Due to COVID-19 uncertainties, I would like it to be possible to succeed without attending class in person, apart from the final. I have thus requested that all lectures be captured and put up on Canvas using the automated magic that the campus does. I can’t guarantee that it will work perfectly. In fact, I can pretty much guarantee that it won’t. But having both the MWF section and the TR sections recorded gives us good redundancy.
My past experience suggests that missing classes with the intent of learning the material from watching the videos usually results in worse performance.
A Few Online Classes
Due to extraordinary circumstances this term, I expect to be out of town a few times, and will try to hold the class remotely when this happens. I will give you as much notice as I can, but you may need to be flexible.Discussion Sections
Discussion sections this term will be almost like office hours. We will use them for you to ask questions and discuss matters with a TA, or with each other. The TAs will not be preparing material to present (but see Recitation, below, for which they will prepare material). Discussion sections are not recorded.There are six discussion sections each week. You may go to any you wish; it doesn’t have to coincide with the what you registered for. Discussion sections are optional.
- M 11 in Wellman 207 (discussion A1, CRN 30600)
- M 1 in Olson 147 (discussion A2, CRN 30601)
- M 2 in Hoagland 108 (discussion A3, CRN 30602)
- M 3 in Bainer 1130 (discussion B3, CRN 52890)
- T 2 in Hart 1130 (discussion B1, CRN 52888)
- T 3 in Hart 1130 (discussion B2, CRN 52889)
Sunday@4 Recitations (LWR & HH)
Every Sunday at 4:10 pm one or more of our TAs, usually John, will lead an online recitation. The recitation might go past 5 pm. Recitation sections will usually have two parts:- Last Week in Review (LWR): The TA will summarize what was talked about in the prior week.
- Homework Hints (or Homework Help) (HH): The TA will talk about the homework that will be due the following Wednesday. The TA might also work out some related problems.
Attending the recitation is optional. Barring technical problems, a Zoom record will be posted soon after on Canvas.
When you attend a live recitation, turn on your camera, and leave it on. If you are unwilling to do this, please watch the recording instead.
Office Hours
I will offer a mix of in-person and online office hours. My in-person hours will be outdoors. TA office hours will be entirely online. Current office hours will be maintained in a document linked to from the course homepage. They may vary from week to week; always check for last minute changes.A rule for attending office hours is to turn on your camera and leave the video on. Same rule as for recitations. A working camera may also be needed for the midterm; please consider it a course requirement.
Zoom Password
I will announce in class and on Canvas the password you will need to join Zoom meetings.Instructor
My name is Phillip Rogaway. My work is in cryptography. I’ve taught ECS 20 a few times before, but it’s been a few years. Other classes I like to teach include Theory of Computation (ECS 120), Cryptography (ECS 127 and ECS 227), and Ethics and Technology (ECS 188).My office is in 3009 Kemper, but, honestly, I don’t think I’ll be hanging out there much. I can be reached by email at [email protected]. Please put “ECS 20” somewhere in your subject heading (capitalization and whitespace irrelevant). For routine ECS 20 questions, please ask on Piazza, not email.
Teaching Assistants
We are lucky enough to have four TAs for the term:- John Chan - [email protected] (25%)
- Jonathan Rosenzweig - [email protected] (50%)
- Arefeh Yavary - [email protected] (50%)
- Justin Xu - [email protected] (25%)
Course Webpage
The course webpage is where you’ll find assignments, solutions, the list of lectures given so far, and so on. It is a click away from my homepage, on the CS Department’s web server. The course webpage is not on Canvas. Please check Piazza and the course webpage frequently.Lecture Capture, and the Possibility of Students Being Recorded
Please be warned that lectures will be recorded. The recordings run from three minutes before to two minutes after the scheduled lecture time, and the camera will typically be on a wide shot of the room. Room audio will also be recorded.Grading
The grading criteria this term is:- Problem Sets: 30% — Weekly — Collaboration in pairs permitted
- Midterm: 25% — I am planning a take-home exam
- Final: 45% — In-class, at your scheduled exam slot
To get a passing grade in the class, you must pass the final exam. All exams are closed book, notes, and gadgets unless I indicate otherwise.
On homeworks, all answers must be well justified. Explain your answers well. The quality of the writeup matters, and is an integral part of the score for a problem. I expect that only a proper subset of homework questions will be graded each week.
If you believe that a homework or exam problem was misgraded you may resubmit it to the TAs for regarding. Make sure you understand the written solutions first. Regarding requests must be done within three days of when the material was returned.
If you miss the midterm for an excused medical or personal reason, I will either give you an oral exam to replace it, or I will move the points to the final exam. If you miss the final exam for an excused medical or personal reason, and you were doing passing work before, then I will give you an incomplete and you will have the opportunity to take the final at the end of Winter quarter.
Objectives
My objectives for this class this term are for you:- to stay safe and to support one another to the maximal extent that this is reasonably possible
- to gain some mathematical maturity
- to improve your ability to think creatively in a rigorous domain
- to improve your skills with technical writing;
- to learn some standard material in discrete math; and, finally,
- to stop every now and then and ask the questions people rarely seem to ask in CS classes: where are we, as a discipline, and is it an OK place to be?
Prohibition on Use of Phones and Laptops
Your phone should be off and in your bag before entering our classroom. This requirement applies starting ten minutes before lecture begins, and continues until class ends. Within our classroom, phones may not be consulted to check the time, email, or anything else. While this requirement may sound draconian to some, it is supported by a body of research that demonstrates how extreme is the distraction from your phone, even when it is near you but not in use. It is also supported by my personal experience, which suggests that classes evolve a different dynamic when the classroom is a phone-free space.Laptops are similarly disallowed in class. You may take notes on a tablet or flat-folded laptop as long as it is used for no other purpose.
Violating the rules above will result in a misconduct report to OSSJA, which, in turn, will likely result in your failing the class. Breaking classroom rules is treated like other forms of academic misconduct.
Masks Required — Importance of Fit — N95 or KN94 Preferred
You are required to wear, and wear properly, an appropriate face covering. No bandannas, buffs, or transparent nonsense. A mask worn below your nose is the same as not wearing a mask (although it does broadcast that extra bit of contempt for those around you). A mask at the tip of your nose, or with huge gaps around your nose, really isn’t working a mask, either. This is not that hard. If someone around you is not properly wearing an appropriate face covering, please politely remind them. If they don’t promptly fix it, please bring the problem to my attention. Failing to properly wear a mask is considered a form of academic misconduct this term, and may result in a referral to OSSJA.Given what we now know about COVID-19 transmission—in particular, that it is primarily spread through aerosols—I question why we are so unconcerned with what sort of mask people wear, and that they they properly wear them. Now that N95 masks are readily available, I suggest that everyone wear find an unvalved N95 mask that fits and feels comfortable. I would also request that you take some time to watch some video(s) about how to put it on, take it off, and check the fit. After trying lots of N95 masks, my personal favorites are the 3M Aura models. They are supposedly available from the campus bookstore, from Amazon, The Home Depot, and from numerous other sellers.
A good alternative to N95 masks is a KF94 mask, the Korean standard. They provide an alternative option for fit. A mask that doesn’t form a good seal to your face is almost worthless.
Room ventilation is also key for minimizing the spread of infectious respiratory diseases. According to the campus, all of the lecture and discussion rooms used for ECS 20 this term are ventilated with 100% outdoor air and get at least four air changes per hour.
If you haven’t watched the science develop in this area, I might point you to: Airborne transmission of respiratory viruses (27-Aug-2021); A paradigm shift to combat indoor respiratory infection (14-May-2021); How did we get here: what are droplets and aerosols and how far do the go? A historical perspective on the transmission of respiratory infectious disease (15-Apr-2021); and COVID tranmission and risk reduction (24-Aug-2021). The Current CDC guidelines were recently updated (although they continue to downplay the value of wearing a well-fit N95 mask).
Recommended Texts
There are a zillion books on discrete math. I won’t require any, but the one I currently like best is- Mathematics for Computer Science by Eric Lehman, Tom Leighton, and Albert Meyer (2021). It is free and, to me, has that unique feel of MIT. I might even refer to it as the MIT book (as though there were but one). Prof. Meyer was a trusted mentor of mine at MIT, a sort of father-figure, and I have fond memories of him from those days. He retired in 2019, after 50 years at MIT. There are also videos online of Prof. Meyer’s discrete math course, 6.052J, although I don’t know that he sticks closely to his book.
Three other books I really like are:
- Book of Proof by Richard Hammack (2018). Another free (CC-licensed) online book on discrete math. I have a hard time getting over how agrammatical the title sounds to my ears. Yet it’s a lovely discrete-math book, well written, with nice examples and a pleasant conversational style. It’s also way shorter than the MIT book.
- How to Solve It by George Pólya (1945). A wonderful book about making smart guesses, finding proofs, and thinking straight. The book could benefit anyone from high school to grad school, teacher and students both. It is written by a brilliant mathematician, which comes across quite clearly, who actually cared about pedagogy. Unlike any math book you’ve read. Prof. Pólya died in 1985, at the age of 97.
- How to Guard an Art Gallery by T.S. Michael (2009). A handful of beautiful problems from discrete mathematics, with exemplary descriptions of each. Most of the book should be accessible to good students in this class. The problems capture the magic of theoretical computer science. Prof. Michael died of cancer in 2016, at the age of 56.
The most ‘standard’ books for a course like ours are those of Susanna Epp and by Kenneth Rosen. I think they are boring in a way that the books above are not. Yet you might like them.
Problem Sets, Gradescope, and LaTeX
Much of what one learns in this course comes from trying to solve the homework problems. I intend for you to find many of the problems challenging. Most students will not be able to solve every problem. Don’t let that frustrate you. I can’t solve most of the problems I think about, either.
If you can’t solve a problem, please indicate what you’ve tried and where the difficulty lies: know what you know and be clear about it. Never try to bullshit an answer you can’t figure out. Explain yourself clearly. An unjustified answer is not an answer.
Your writeups should be clear, terse, and neat. Aim for elegance. Never turn in a first-draft; that works no better in math or computer science than it does in English. Don’t be surprised to lose points if you provide a “correct” solution with a poor writeup: presentation (always) counts.
Homeworks must be typeset with LaTeX. Observe basic mathematical conventions that too many student seem blind to, like k, K, k, and K (in LaTeX: k, K, $k$, $K$) being four different variables. Figures you wish to include may be drawn neatly by hand and then integrated into the pdf. Microsoft Word generates ugly results and is not used by academic computer scientists. Nor by mathematicians, physicists, or chemists. We all use LaTeX.
Typeset solutions with a single solution per page (the LaTeX command \newpage will skip to the next page). I do not expect any problems to take more than a page, so normally problem i should appear on page i. Regardless, when you upload your problem set to Gradescope you must tell it the pages on which each problem appears. If you fail to do this then Gradescope will not display your solution when we are grading the problem, and the problem won’t get graded.
Overleaf is an online LaTeX editor and collaboration tool. You are welcome to use it, or to install a local copy of LaTeX no your machine, or to both.
Unless indicated otherwise, homeworks are due at 5:00 pm every Wednesday. The first problem set will be due Sept 28, and they will keep on coming. No late homeworks will be accepted. Turn in homeworks online, using Gradescope. The roster has been uploaded so you should already be able to use Gradescope. Send an email if there’s a problem. Don’t wait until the last minute. To avoid unexpectedly missing the deadline, you can repeatedly overwrite your uploaded solutions; don’t wait until a minutes before 5pm to submit.
You may work closely with a single other student on a homework and turn in a joint writeup. Gradescope will let you identify both names when you upload the writeup; do not forget to do that (just writing both names in the uploaded pdf won’t do it). I do not want you doing writeups in a group larger than two. If you talk to someone other than your partner, a TA, or the professor, you need to acknowledge them in your writeup.
Oddly, many students are happier to spend long hours hacking in front of a machine than peacefully thinking beneath a tree. I wonder why. Computer science is about thinking and problem solving, not about spending endless hours pounding some hapless program into submission.
Piazza
Besides Canvas and Gradescope, you will use one further website for this class: Piazza. Your email should already have been added to it. If there’s a problem, I believe you can signup directly via this URL and an access code that is the same as our Zoom-meeting password.Collaboration
As just mentioned, I permit collaboration on homeworks in pairs. When I was a student, we enjoyed working alone. Now it seems as though most people want to work on a team. It is an important skill to be able to do both.If you do work with a partner on a problem set, the manner in which you do so may have a profound impact on how much you get out of the homeworks, and out of class. Here’s what I suggest. First, think about each problem and try to solve it on your own. Only after should you discuss it with your partner. When you write up a truly joint solution. Both people should work to write and refine the writeup for each problem. Note that writing up joint work with a partner will usually take more time than writing things up your own. But it can result in better quality work.
While I haven’t used it myself, I am told that overleaf is an easy-to-use tool to let multiple people simultaneously edit on a single LaTeX file. Even if you’re working alone, the tool would save you from having to do a LaTeX installation. Not that that is hard. An alternative way to collaborate in producing a LaTeX document is using git, with each collaborator running their own copy of LaTeX.
Academic Misconduct
On homeworks you may not consult any problem set solution, at any institution, for any similar problem. You should not seek out problems like ones I ask you on the web. If you accidentally encountered such materials, just acknowledge it in your writeup and that’ll be fine. If you interacted with anyone other than a named partner on a homework problem, identify them on your solution. If you collaborate with someone extensively on a homework then they are your partner, you should turn in a single writeup for the two of you. Acknowledge any book or webpage that proved directly useful.The final will be closed book/devices/neighbors. Bring a picture ID. Any device that can be powered off must be powered off for the duration of the exam. You may not sit next to someone you know. In that sentence, “next to” means to your left, right, directly behind, or diagonally behind; and “someone you know” means that they’re a friend or someone you’ve worked with (in this class or some other), or someone you have some arrangement with concerning cheating. If you see anything inappropriate during an exam, report it immediately to me or a TA.
Uploading course materials for further redistribution to sites like CourseHero is an egregious instance of academic misconduct. It is also illegal. Similarly, you may not download material from CourseHero or the like.
As explained earlier, using a phone in our class is defined as academic misconduct.
UCD’s Code of Academic Conduct describes expectations common to all courses. I report all instances of suspected academic misconduct to OSSJA. If you are guilty of academic misconduct, either by your own admission or by a finding from OSSJA, I will assign you an F grade in the course. This is in addition to whatever OSSJA does. I call this the misconduct-implies-F policy. I myself started this policy, which has become the default policy across the CS Department.
Who am I?
I was trained in theoretical computer science at UCB and then MIT. While I never much liked computers, I loved science, puzzles, and writing. I have worked since the late 1980s in cryptography, particularly a style of cryptography characterized by definitions and proofs, but for problems that spring directly from cryptographic practice, addressing them in ways that directly inform cryptographic practice. It’s a branch of cryptography that I kind of invented, along with my colleague Mihir Bellare.Beginning in 2004 I redesigned and started teaching ECS 188, our ethics-and-technology class. Since that time, about half my teaching has been technical, the other half, 188. While I was never exactly sanguine about what all my colleagues and I were doing, over the years I had become increasingly skeptical about the value and prospects for it. We have turned out machines into powerful instruments for surveilling people and reshaping their behavior to serve a few people’s ends. For those of you who want to save the world with machine learning (ML), crypto-currency, or whatever other hyped techno-wonder you’ve been studying, make sure to disentangle the dream, and your self interest, from the reality.
A strange fact about me is that I am utterly faceblind. Never changing your hair, clothes, or seat might help me to figure out who you are. Introducing yourself to me each time you see me is kind. I would also request that you not wear scented products near me. I find smells overwhelming and asthma-inducing. I will also have a problem being near you if you’re a smoker. But hopefully none of you would do anything so vile.
Closing remark
This class may provide you your first glimpse of theoretical computer science. If you haven’t had good math classes before, which is sadly common, it might even provide you your first experience having to think like a mathematician. Math is not calculation, and computer science is not programming. I hope you like what you see!
Instructor’s homepage