cs2102
Discrete Mathematics

Syllabus

PDF for Printing

cs2102: Discrete Mathematics
University of Virginia, Fall 2017

Meetings: Tuesdays and Thursdays, 2:00-3:15pm in Chemistry 402.

Course Objective. The goal of this course is to help students to understand, explain, and apply the foundational mathematical concepts at the core of computer science.

The skills students learn in this course are essential for later courses (especially CS 3102 and CS 4102, but also in other courses), where they will be used to reason about and develop algorithms, prove properties about programs, and understand the limits of different models of computation.

Expected Background: The official prerequisite for this course is earning credit for CS 1110, 1111, 1112 or 1120 with a grade of C- or higher. If you have not satisfied the official prerequisite, you need permission from the instructor to enroll in the class.

Materials: The primary textbook is:

Eric Lehman, F. Thomson Leighton, and Albert R. Meyer. Mathematics for Computer Science. (2017/6/15 version). This book is freely available on-line, and generously released under a Creative Commons Attribution-ShareAlike 3.0 License.

The course will mostly cover the first part of this book (Chapters 1-8), and some selected materials from later chapters (in particular chapters 9, 15, 17). In addition to that textbook, we will have selected readings from other sources.

Staff

Teachers:
David Evans (evans@virginia.edu, Rice 507)
Mohammad Mahmoody (mohammad@virginia.edu, Rice 511)

You can reach both of us using uvacs2102staff@gmail.com. Please use that address for course-related messages.

Assistant Teachers:

Amar Singh, Anna Wu, Bhuvanesh Murali, Colin Harfst, Fan Feng, Helen Simecek, Henry Spece, Jack Herd, Joseph Tobin, Michael Woon, Nate Olsen, Sarah Meng, Xiao Zhang, Xueying Bai, Yasasvini Puligundle, and Zheng Wang.

Amar Singh
Anna Wu
Bhuvanesh Murali
Colin Harfst


Fan Feng
Helen Simecek
Henry Spece
Jack Herd


Joseph Tobin
Michael Woon
Nate Olsen
Sarah Meng


Xiao Zhang
Xueying Bai
Yasasvini Puligundle
Zheng Wang

Office Hours: The course staff is here to help you. Please don’t wait until too late to take advantage of the available help or ask for help. For nearly everyone, this course will involve learning new ways of thinking that are dramatically different from those to which you are accustomed. It is natural to miss things, and then become lost since new ideas build on previous ones. Come to office hours early to get help before you find yourself frustrated and confused.

The office hours schedule will be posted on-line, and it will be kept updated throughout the semester.

Communications

Course Website: https://uvacs2102.github.io/. All course materials will be posted on the course website. This page is updated often and students are expected to visit it regularly. All lectures, notes and assignments for the course will be posted on the web site.

Slack: https://csmath.slack.com. We will use a slack group for “real-time” communication for quick help and discussion (including during lectures). Unlike the course site, which is public and visible to the world, this group will only be visible to people in the class. There are slack apps for web, iOS and Android. We encourage students to ask questions about the classes and assignments by posting comments on slack, and the course staff will read and respond to questions there.

Email: Feel free to email us with any personal questions or issues that should not be posted publicly. To reach both professors, use uvacs2102staff@gmail.com (please use this instead of our personal emails unless it is an issue that is specific to one of us). For general questions or issues that might be relevant for others in the class, it is better to post publicly to the course website or slack group (both so that others may be able to answer your question, and others may be able to see a response that will be useful to them).

Calendar: The course calendar is available as a Google calendar. Students are encouraged to incorporate this into your own calendar. If you use Google Calendar, just click the “+” at the bottom right of the calendar page. If you use another calendar program, you can incorporate this calendar using ical.

Honor

We believe strongly in the value of a community of trust, and expect all of the students in this class to contribute to strenghtening and enhancing that community. The course will be better for everyone if everyone can assume everyone else is trustworthy. The course staff starts with the assumption that all students at the university deserve to be trusted.

To ensure that expectations are clear to everyone, all students are required to sign the course pledge.

Topics

The topics covered in cs2102 focus on developing the mathematical foundation and skills that are most important for computer science. Expected topics include:

  • Propositions and proofs
  • Proof methods (including proof by construction, contradiction, and induction)
  • Logic (Boolean logic, logical formulas, quantifiers)
  • Binary relations
  • State machines
  • Finite and infinite sets
  • Number theory
  • Counting techniques
  • Probability theory

Assignments and Exams

A detailed schedule is maintained on the course website and calendar.

Key dates:

  • Most Fridays (6:29pm): There will be a homework assignment due on Fridays, except for weeks when there are exams (and Thanksgiving week).
  • Thursday, 5 Oct: Exam 1 (in class)
  • Thursday, 9 Nov: Exam 2 (in class)
  • Thursday, 7 Dec: Final Exam (9am-noon, scheduled by the registrar)

Grading

Grading will be based on your performance on the exams and homework assignments, with additional adjustments made based on exceptional contributions to the class.

Grades will be calculated with several different weightings, where your grade is based primarily on whichever weighting results in the highest score. The range of possible weightings is:

  • Homeworks: 15-40%
  • Exam 1: 10-25%
  • Exam 2: 15-30%
  • Final Exam: 20-50%
  • Class Contribution: 0-25%

Spend your energy focusing on what you are learning, instead of worrying about your grade.

Although the material we cover is challenging, and the pace may seem overwhelming at times, we are confident that all students who put effort into this class and take good advantage of available help will do well. Students who do especially outstanding work in the course will be offered positions in our research groups (Dave, Mohammad).