DMT1 Syllabus

Overview

Official Course Description. This is the official course description from the Undergraduate Record:

Introduces discrete mathematics and proof techniques involving first order predicate logic and induction. Application areas include sets, tuples, functions, relations, and combinatorial problems. Prereq: CS 1100 - CS 1199

Unofficial Course Description. Our course will match the official description, but the core goal of this course is to help students to understand, explain, and apply the foundational mathematical concepts at the core of computer science. The course has two main purposes:

  1. Develop your ability to think and communicate in a clear, mathematical way. We hope this will be useful throughout your life, but it is essential to becoming a strong computer scientist.

  2. Introduce and gain understanding of the mathematical objects, definitions, notations, and techniques that will be essential for later computing 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. Students entering the course are expected to have some experience with computer science including what is typically covered in a programming-focused first computing course such as cs 1110. You should be able to read and reason about short programs, and have a high-level undersanding of how programs execute. Students are also expected to have reasonable high school math background, but we do not assume background in calculus and rarely use any math beyond addition, subtraction, multiplication, exponentiation, and algebra.

Materials. The primary textbook is:

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

A web-based version of the textbook is also available from LibreTexts. We believe the content is nearly identical to the PDF version, but cannot guarantee it is entirely consistent.

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) and Aidan San (aws9xm@virginia.edu).

Class Sections: There are two sections of the course:

  • 10:00-10:50am on Mondays, Wednesdays, and Fridays in Olsson Hall 120 (David Evans)
  • 2:00-2:50pm on Mondays, Wednesdays, and Fridays in Rice Hall 130 (Aidan San)

On days with tests or in-class activities, you must attend your registered lecture section unless you make prior arrangements with the instructors. On other days, you may attend attend whichever lecture section you prefer or even both (as long as there are enough classroom seats). Note that although we will generally cover the same material in casses, the one section might be slightly ahead of the other or do things in slightly different orders, so we recommend that you consistently attend the section in which you are registered.

Main Topics

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

  • Mathematical definitions
  • Propositions and proofs using first-order logic
  • Proof methods (including construction, contradiction, and induction)
  • Logic (Boolean logic, logical formulas, satisfiability, quantifiers)
  • Binary relations
  • Finite and infinite sets

Communication

We will primarily use the course website for posting course materials, and use the course discord for interactive communications.

Course Website: We will post nearly all course materials at https://uvadmt.github.io. This is an open public website.

Canvas: We will use UVA Canvas for managing course assignments. Everyone in the course should be in the canvas course site for their section.

Discord: We will use the course discord server for most other course communications (you will receive information on joining the server by email). We expect students to receive messages we send to the #announcements channel as well as any direct messages we send to you on discord.

If you have questions about course materials or assignments that will be relevant to other students, please ask them in the #general channel. This will get the fastest response, since all of the course staff and students will see your question there and be able to respond to it.

Email: Managing email for a large class like this is difficult, and you should use the course discord for questions about the course content that are relevant to all students. If you have personal questions or things to discuss with the course staff, please do this by emailing your section instructor.

Contacting Us: The table below gives some examples of topics and the best contact methods to use.

Topic Contact Method
Questions about course topics In-class questions, Instructor and TA Office Hours, Discord
Questions about grading Instructor Office Hours, Regrade requests through Gradescope
Help with problem sets Instructor and TA Office Hours, Discord
Extension requests for problem sets Submit the Extension Request Form
Slept through a test Private email to your instructor
Personal issues impacting coursework Private email to your instructor
Conversations about mentoring, research, student life, etc. Office Hours or schedule individual visit

Getting Help: If you are struggling with the course we highly encourage you to utilize instructor and TA office hours. We want you to learn well and have a good experience in the course, and are here to help you.

For additional help, the engineering school also provides tutors (https://engineering.virginia.edu/undergraduate-study/student-support/tutoring).

If you are struggling with personal issues we encourage you to talk to your academic dean or SDAC if appropriate (https://www.studenthealth.virginia.edu/student-disability-access-center).

Assignments and Exams

Problem Sets. Most learning in this course is done by working to solve problems on your own and in collaboration with others. We will have a problem set due (typically on Thursdays by 8:29pm) most weeks in the course, except for weeks when there is a test. See the course calendar in Canvas for specific due dates.

Each problem set will include specific directions for how to submit your solutions, and we expect students to read and follow these carefully. Each problem set will state a clear collaboration policy (which typically will allow you to discuss problems with others, but require that you write up your solutions by yourself and understand everything in it) and we trust and expect students to follow these policies vigilantly.

Tests. We will have four in-class tests scheduled approximately every three weeks throughout the courses. These tests will be designed to check your understanding and ability to solve problems using ideas we have covered in class. They will emphasize material from the prior two problem sets, but will also include reivew questions on earlier class material. Tests will be done on your own, without using any resources other than a permitted single page of notes you prepare that will be permitted for some of the tests.

Final Exam. The final exam, scheduled by the Registrar, is scheduled for Tuesday, May 6, 7:00-10:00 PM. Depending on your performance, you the final might be optional for you, but until you hear otherwise, you should assume you will need to take a final as scheduled. The final exam will be a valuable opportunity for students to demonstrate what they have learned throughout the course.

Extensions and Late Submissions. Extensions will be granted to individual students on a case-by-case basis. We are more likely to respond positively to an extension request if it is made well before an assignment is due and provides a reasonable justification for the extension. To request an extension, use the form for your section:

Extension Request Form

We are sympathetic to situations where a traumatic late event prevents you from being able to complete an assignment, and appreciate you bringing these to our attention even if the deadline has passed.

Other than the correct interpretation that an assignment submitted by the deadline or by the date given in a granted extension request, our late policy is to not have a late policy. This doesn’t mean there is no way to get credit for a late assignment, and even if you have no excuse, it is always better to submit an assignment late than to not submit the assignment at all. Beyond that guideline, we will consider late assignments on a case-by-case basis that takes into account how late the assignment it, whether it is just one late assignment or a habitual problem, and any contextual information provided about the reason for the lateness.

If you find that you will be unable to make one of the scheduled tests or final exam, contact the course instructors immediately.

Class Contribution. There are many ways for students to contribute to the class, and we value any contributions that improve the learning and experience of yourself, other students, and the instructors. This can include being an engaged and active participant in class, but also includes sending the instructors useful feedback (including on things like a broken link or error in class materials), asking and answering questions in the discord, solving or attempting to solve “Challenge Problems”, helping other students, and other things you do to contribute to the class. For a large class like this, the instructors will be aware of some things you do but may not be aware of all of them, so you’ll have an opportunity near the end of the semester to explain how you contributed to the class.

Grading

We encourage students to spend your energy focusing on what you are learning, instead of worrying about your grade.

That said, we understand students are often stressed about grading and understandably want to know how grades will be determined. We aim to grade in a way that is useful (provides students with accurate measure of how well they understood what they should), motivating (encourages the behaviors we prefer, including hard but not obsessive work), fair (assigned higher grades to more deserving students), robust (arbitrary small perturbations do not have a material impact on someone’s grade), and low stress (for both students and the course staff).

For this reason, we choose not to prescribe a singular mathematical formula for quantitatively assigning letter grades but do provide a formula that can be used to compute a lower bound on the grade you receive in the course:

Item Default
Problem Sets (7 expected) 35%
Tests (4 scheduled) 40%
Final Exam 20%
Class Contribution 5%

With the exception of cases of academic dishonesty or inappropriate behavior, you can be assured that your final grade will not be below the grade that would result from computing your score using the default weightings in the table, where your score for each item is the ratio of the score you received to the target score for that item, and the grading scale is based on the standard decades (e.g., 0.87 = B+, 0.9 = A-, 0.93 = A).

This is a minimum grade expectation, though, and we generally want to assign a grade that reflects the best possible interpretation of all you have done during the semester. This means we consider your performance throughout the course, and will examine grades using a variety of different methods that weights different aspects differently and rewards performance improvements, but also allows consistent performance to make up for one slip-up.

An “A” grade means we are convinced that you can use the material in this class to solve new problems and understand it well enough to explain most concepts in the class. A “B” grade means we are convinced that you understand the main ideas in this class well enough to be well prepared for a follow-on course (i.e., DMT2 and other courses that include this course as a pre-requisite).

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.

Honor Expectations

We believe strongly in the value of a community of trust, and expect all of the students in this class to contribute to strengthening 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 read, understand, and agree to the course pledge.

Collaboration Policy: We believe it is important for students to learn by thinking about problems on their own, so it is expected that each student studies the provided materials and attempts to solve the problems on their own. After that, you are welcome to also discuss problems on the problem sets with students and others.

Many problems in this course will be selected from problems used in previous courses, as well as well known problems. The goal of these problems is to lead students to develop understanding of the underlying concepts by working through the problems themselves and in discussions with others, and this goal would be defeated if you instead use posted solutions to the problems. Other than using solutions to the specific problems you are given, students are encouraged to use any other resources they find helpful.

The collaboration policy will be described on each assignment document. We aim to make the language describing the policy as clear and unambiguous as possible, but if anything is ever unclear about the stated policy for an assignment, please clarify with the course staff. The penalty for policy violations will be considered on a case-by-case basis, with a penalty commensurate the severity of the offense.

AI Tools

Use of generative AI tools such as ChatGPT, Claude, and Gemini on problem sets is encouraged, but like any resources you use these should be used in a way that supports your learning, is consistent with the course goals, and is fair to other students. These are powerful tools that can be great assistants and tutors to humans to use them well, and learning when and how to use these tools is itself a valuable skill.

However, since the goals of the course are to improve your ability as an individual to think mathematically and to understand and be able to use the methods we teach in the class, it would be counterproductive to use any resources, including AI tools, in ways that are counter to these goals. Tools can be used as shortcuts to accomplishing short term goals, such as getting a correct answer to a problem, in ways that are counter to long term goals, such as empowering yourself with new skills and understanding. Getting an answer in a way that depends on using a powerful tool can also be misleading, and make someone think they understand or are capable of doing something on their own without actually developing this. There is also a severe risk today that AI tools will give outputs that are wrong, but with language that seems convincing. Without the deeper understanding needed to interrogate the models well, users are prone to being mislead by incorrect outputs.

If you are not motivated by developing your abilities and gaining an appreciation of the beauty and power or mathematical thinking, though, and only want to maximize your grade while minimizing your effort, you should be aware that the tests to assess your learning in the class will be done in class and without any access to external resources. We want to see what you understand and can do on your own. The way overall grading is done in the course, it will not benefit you to get higher grades on the problem sets by using tools that prevent you from learning what you will need to understand to be able to do well on the assessments.

All assignments in the course will include a collaboration and resource policy which you should read and follow carefully. These will expect you to document any use of AI tools, and include links to transcripts that show your interactions with the tool. We plan to include some demonstrations using AI tools in the class, as well as specific examples of encouraged and inappropriate uses on the problem sets.

Additional Information

Special Circumstances: The University of Virginia strives to provide accessibility to all students. If you require an accommodation to fully access this course, please contact the Student Disability Access Center (SDAC) at (434) 243-5180 or sdac@virginia.edu. If you are unsure if you require an accommodation, or to learn more about their services, you may contact the SDAC at the number above or by visiting their website https://studenthealth.virginia.edu/sdac

Accommodations: It is the University’s long-standing policy and practice to reasonably accommodate students so that they do not experience an adverse academic consequence when serious personal issues conflict with academic requirements. Although University policy only recognizes religious accomodations, the course instructors believe they are many other valid reasons for accomdations that are at least as justifiable as ones for religious observance and consider family obligations, personal crises, and extraordinary opportunities to all be potentially valid reasons for accomodations. Students who wish to request accommodations should submit their request to their instructor as far in advance as possible.

If you have questions or concerns about the University policy on academic accommodations for religious observance or religious beliefs, visit https://eocr.virginia.edu/accommodations-religious-observance or contact the University’s Office for Equal Opportunity and Civil Rights (EOCR) at UVAEOCR@virginia.edu or 434-924-3200.

Safe Environment: The University of Virginia is dedicated to providing a safe and equitable learning environment for all students. To that end, it is vital that you know two values that we and the University hold as critically important:

  1. Power-based personal violence will not be tolerated.
  2. Everyone has a responsibility to do their part to maintain a safe community on grounds (including in virtual environments).

If you or someone you know has been affected by power-based personal violence, more information can be found on the UVA Sexual Violence website that describes reporting options and resources available: https://www.virginia.edu/sexualviolence.

As your professors and as humans, know that we each care about you and your well-being and stand ready to provide support and resources as we can. As faculty members, we are responsible employees, which means that we are required by University policy and federal law to report what you tell us to the University’s Title IX Coordinator. The Title IX Coordinator’s job is to ensure that the reporting student receives the resources and support that they need, while also reviewing the information presented to determine whether further action is necessary to ensure survivor safety and the safety of the University community. If you would rather keep this information confidential, there are Confidential Employees you can talk to on Grounds (see https://eocr.virginia.edu/chart-confidential-resources). The worst possible situation would be for you or your friend to remain silent when there are so many here willing and able to help.

Well-being: If you are feeling overwhelmed, stressed, or isolated, there are many individuals here who are ready and wanting to help. The Student Health Center offers Counseling and Psychological Services (CAPS) for all UVA students. Call 434-243-5150 (or 434-972-7004 for after hours and weekend crisis assistance) to get started and schedule an appointment. If you prefer to speak anonymously and confidentially over the phone, Madison House provides a HELP Line at any hour of any day: 434-295-8255.