CS 2800 - Discrete Structures

General Information

Discrete Structures is a weird name - it would make more sense being named Discrete Mathematics. This basically means math that isn’t continuous (i.e. calculus).

Prerequisites

None

Topics Covered

• Sets, functions, relations
• Proof techniques, induction
• Number theory and public key encryption
• Counting and combinatorics
• Probability
• Logic
• Graph Theory
• Finite automata and regular languages
• Context-free languages
• Computability and NP-Completeness A lot of time spent on proofs and emphasis on proofs by induction.

Workload

Usually there are weekly problem sets, 2-3 prelims, and a final. Historically, homework is a relatively large portion of the grade. There is no programming in the course and the work load is reasonably consistent throughout the semester. Not significantly heavy, but can take up to a few hours a week pending how well you understand the topics.

General Advice

Taking this concurrently with CS 2110 is very manageable and helpful. There is a lot of overlap in topics especially relating to proofs by induction and graph theory (although the overlap has lessened recently, especially as 2110 has come to focus less on proofs) and it is helpful to see the information twice. This class is a foundation for a lot CS, so it is good to take reasonably early. Learning graph theory and proofs is reasonably important for lots of upper level courses and general CS.

I found the recommended/required textbook to be very helpful! A lot of topics that were briefly covered in class were covered in depth in the textbook. Reading the textbook and looking over the examples boosted my scores on the test. Also, I did not have to go to office hours which were usually very crowded.

Do not buy the textbook. Also, office hours will be crowded the days the problem sets are due.

Find out which of the student TA’s are math majors and ask them for help. They’ll know more.

^This. 2800 is a theory class so math majors will know way more about this than CS people. Also, as mentioned before, graph theory, proofs, and most of the other material you learn is very useful for reasoning about various problems.

Testimonials

With Bart Selman, I thought this class was really easy. If you have any exposure to the topics before this class (high school math and/or other CS classes, like CS 1114), you should be able to spend minimal time on this class.

I was very involved in math in high school and did some number theory/combinatorics, and this course did not progress any further than that. Also, I concurrently took MATH 3360, which is basically a much harder version of this course, so I ended up learning next to nothing in 2800.

Took it with Pass. This class was a joke and I learned very little new material, but it was a good review of all the random math that mostly hadn’t officially shown up in my classes before. Low maintenance and interesting enough though.

With Kozen (Fall 2013) the course wasn’t terribly hard but was more difficult than the other testimonials would lead you to believe. We had 8 problem sets over the course of the semester each of which took several hours. The in exams were reasonable difficulty wise, but the in class prelims were hard to finish in the given time. (There was plenty of time for the final.) Realize that unless you’ve already taken a discrete math class, you will being seeing many of the topics for the first time.

Kozen (Fall 2013): Kozen was a very good lecturer and explained everything in detail. The problem was that he went far more into detail than a breadth-class should do, so we were learning a lot of different topics with a decent depth very quickly. Still not too hard, but that meant a lot of material and many specifics to memorize for exams (above testimonial explains this well). Pass’s course notes (see link below) were very useful, but Kozen covered some different subjects. The book wasn’t too useful, but you did need it as a few problems were from the book.

Graeme Bailey (Spring 2014): We were in for quite a surprise. Though this class has a reputation for being relatively easy, this semester the material was very difficult. In addition to the usual topics, Bailey spent a large portion of time on various abstract algebra topics, esp. group theory. Approximately 35% of the class dropped within the deadline.

Weekly homeworks were usually released on Wednesdays to be due the following Monday (we were promised 10 days to do them, but rarely got more than 5). They were very proof intensive and took a significant 10-15+ hours of time. Aside from the very few math majors, most TAs were unable to help with the homeworks as they didn’t know how to do the problems themselves, and spent their office hours just floundering with us.

Regardless, Bailey gave a noticeable effort to help out his students, offering extra office hours and quick Piazza responses. Tests were offered either in-class or evening-style, and were surprisingly fair. Closing remarks: Came out of this class alive, put in a lot more effort than I wanted to, probably learned a lot about discrete math, but would take an easier professor if I could.

George (Spring 2020): I personally really enjoyed this class and found the material interesting, but YMMV. Workload was manageable but you pretty much needed office hours (which were held really late at night pre-COVID) to do well. Biweekly problem sets were released between Monday and Wednesday and due the Friday of the following week, and you could work on them with a partner. For lectures (pre-COVID), we were supposed to read “prep” on the course wiki before class, and spent class mostly doing examples and iClicker questions to reinforce the concept. Lectures after going online taught more of the material during the lecture itself. Overall a pretty difficult class, but rewarding once you finish it.

Past Offerings

Hopcroft typically teaches this in the fall and Pass, in the spring. Kozen is teaching this in Fall 2013, though. Michael George took over in Fall 2014. Anke van Zuylen will be teaching this starting Fall 2020.

Resources

• Rafael Pass’s Course Notes
• The optional textbook