cs2102
Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

Syllabus

PDF for Printing

cs2102: Discrete Mathematics (Section 1)

University of Virginia, Fall 2016

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

Course Objective. The goal of this course is to 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 cs3102 and cs4102, 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. (2016/6/16 version). This book is freely available on-line, and generously released under a Create Commons Attribution-ShareAlike 3.0 License.

The course will cover most of the first two parts of this book (Chapters 1-13), with some selected materials from later chapters. In addition to that textbook, we will have selected readings from other sources.

Staff

Teacher: David Evans (evans@virginia.edu). My office is Rice 507.

Assistant Teachers: Adam Guo (BSCS 2018), Adam Rosenberg (MCS 2017), Anindya Prodhan (PhD Student), Brooke Dickie (Systems Engineering 2018), Christopher Long (BACS 2018), Gloria Li (MSCS 2019), Harrison Nam (BSCS 2018), Hussain Humadi (CPE 2018), Jin Han (BSCS 2018), Luke Botti (BACS/Math 2017), Riya Simon (CPE 2019), Saikat Chakraborty (PhD Student), Sarah Barkley (BACS/Math 2018), Sihang Liu (PhD Student), Subhan Poudel (BSCS 2019), Yaser Qazi (BSCS 2019), Yong Jae Kwon (BACS 2017).

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 is posted on-line, and 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 me (evans@virginia.edu) with any personal questions or issues that should not be posted publicly. 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, Logical Formula,
  • Binary Relations
  • State machines
  • Graphs
  • Finite and infinite sets
  • Number 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, 6 October: Exam 1 (in class)
  • Thursday, 10 November: Exam 2 (in class)
  • Saturday, 10 December: 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, I am 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 my research group.