CSE 20 - Discrete Mathematics - Borkowski [WI24]
Instructor: Michael Borkowski
Email: mborkows@ucsd.edu
Office Hours: Sunday 3/16 3:00-5:00 pm | CSE 3236 only
Sunday 3/16 5:00-6:00 pm | Zoom only
https://ucsd.zoom.us/j/4818941689
Lecture: Mon/Wed/Fri 2:00 - 2:50pm
Location: Center Hall 115
Discussion A01: Wednesdays 5:00 - 5:50pm
Location: CSB 002
Discussion A02: Fridays 3:00 - 3:50pm
Location: Center Hall 105
Teaching Assistants
TA: Andrea Frank
Email: a2frank@ucsd.edu
Office hours: Tuesday 2:00-4:00pm | FAH 4002
TA: Kalen Cantrell
Email: kcantrel@ucsd.edu
Office hours: Monday 3:30-5:00pm | CSE 4258
Tutors
Jason Chang
Email: jsc008@ucsd.edu
Office hours: Monday 5:30 PM - 6:30 PM | CSE B240A & Wednesday, 12:00 PM - 1:00 PM | CSE B215
Isabelle Krochmal
Email: ikrochma@ucsd.edu
Office hours: Thursday 12:15-1:45PM | CSE B260A
Henry Lin
Email: hhlin@ucsd.edu
Office hours: Wednesday 10:30 AM - 12:00 PM | CSE B260A
Alan Mohamad
Email: amohamad@ucsd.edu
Office hours: Thursday 4:30 PM - 6 PM | CSE B260A
Alexis Vega
Email: a9vega@ucsd.edu
Office hours: Thursday 10:00-11:00 AM | CSE B275
David Wang
Email: dyw001@ucsd.edu
Office hours: Tuesday 9:30 - 11 AM | CSE B275
One-on-One Signup Sheet: Google Sheets link
Course Description
This course will cover mathematical concepts used to model and analyze algorithms and computer systems. This course will introduce the ways logic is used in computer science: for reasoning, as a language for specifications, and as operations in computation. Concepts include sets, relations, functions, equivalence relations, partial orders, number systems, and proof methods (especially induction and recursion). Propositional and predicate logic will be introduced and applied to various computer science domains such as circuit design, databases, cryptography, and program correctness.
This course is a direct tie-in to CSE 21, as well as the upper division algorithms and theory classes, such as 100, 101, 103, 105 and 107, but will also provide basic concepts that are used in the majority of later classes. The CSE department allows MATH 109 in place of CSE 20 for all prerequisites.
Prerequisites
The main prerequisite is CSE 11 or CSE 6R or CSE 8A or CSE 8B or ECE 15. Prerequisite courses must have been completed with a grade of C– or better.
Learning Outcomes
Upon successful completion of this course, you will be able to:
- Describe and trace simple algorithms using English and pseudocode.
- Identify and prove (or informally justify) the termination and correctness of some algorithms.
- Define and use classical algorithms and algorithmic paradigms (e.g. Euclidean algorithm).
- Use multiple representations of numbers to illustrate properties of the numbers and develop algorithms.
- Understand the logical structure and meaning of a sentence expressing a property, fact, or specification.
- Reason about the truth or falsity of complicated statements using Boolean connectives, quantifiers, and basic definitions.
- Relate Boolean operations to applications, e.g. logic puzzles, set operations, combinatorial circuits.
- Prove propositional equivalences.
- Apply proof techniques, including direct proofs and proofs by contradiction.
- Distinguish valid from invalid arguments.
- Reason about modular arithmetic.
- Use mathematical induction to prove statements about mathematical identities and inequalities.
- Apply structural induction to prove statements about recursively defined objects.
- Identify and be able to prove basic properties of sets, functions, and relations.
- Distinguish between finite, countable, and uncountable sets.
Tentative Lecture Schedule:
| Week | Date | Topics | Rosen Sections | Materials |
| 1 | Jan 8-12 | Mathematical Objects, Numbers, Base Expansion Algorithms and Conversions |
4.1, 4.2 |
|
| 2 | Jan 17,19 | Circuits and Logic | 1.1, 1.2, 1.3 | |
| 3 | Jan 22-26 | Normal Forms and Predicates | 1.3, 1.4 | |
| 4 | Jan 29-Feb 2 | All About Quantifiers (Test 1) | 1.4, 1.5 | |
| 5 | Feb 5-9 | Proof methods: Universals, Counterexamples, Sets | 1.7, 1.8 | |
| 6 | Feb 12-16 | More Proofs Methods (Test 2) | 1.8 | |
| 7 | Feb 19-23 | Mathematical Induction | 5.1, 5.2 | |
| 8 | Feb 26 - Mar 1 | Recursive Definitions and Structural Induction | ||
| 9 | Mar 4-8 | Functions, Uncountable Sets, (Test 3) | 2.3, 2.5 | |
| 10 |
Mar 11-15 |
Diagonalization and Cryptography |
References and Recommended Reading
There is no required textbook for this course. However, a particularly useful resource is:
Discrete Mathematics and its Applications, Kenneth Rosen, McGraw Hill, 8th edition.
The textbook's companion website has extra practice problems and resources. In particular, the Self Assessments and the Extra Examples for each chapter are great practice materials. Access the companion website here. Earlier editions contain almost all of the material we will reference, and can be bought used often quite reasonably. We will use the chapter and page numbers for 7th/8th edition.
You may also wish to look at the following textbook as a supplementary resource.
Jenkyns, Stephenson Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer
The full pdf of this book is available for free download from a UCSD internet connection at:
Another helpful book is: Daniel Solow's
How to Read and Do Proofs: An Introduction to Mathematical Thought Processes
While primarily for mathematics majors, it also is a general reference that can be used by anyone reading or doing proofs.
Grading
Homework Assignments (40%)
There will be seven homework assignments, assigned weekly and usually due on Wednesdays. These can be turned in on Gradescope.
Partners
- You can work on the assignments either alone or in groups of up to four.
- Each group will make one submission.
- You do not need to keep the same group throughout the quarter.
Second Chance Points
For certain problems (usually proofs), we will have a second chance deadline for resubmission, within a week after the assignment is returned. You can receive some points back.
Weekly Review Assessment (5%)
A weekly review assessment to reinforce your understanding of the week's material will be available online on the Prairie Learn platform every Friday. These will be much shorter than the homework assignments and should be completed by Monday night.
These assessments are to be completed individually. You may use any notes or references. You may resubmit until the deadline to aim for a better score.
Tests (30%)
Three tests will be held (tentatively) in person on Wednesday January 31, Friday February 16, and Wednesday March 6 during the usual lecture time. The entire 50 minutes of class time will be used for these tests.
The lowest of the three test grades will be dropped.
Please contact me as soon as possible if you cannot attend a test, such as for illness and family emergencies. Any makeup tests will be conducted in person at the Triton Testing Center.
Final Exam (25%)
Will be held on Monday, March 18 from 3 - 6 pm. The location will be finalized later in the quarter.
Class Participation (Extra Credit: up to 3%)
Active participation during class is crucial to learning mathematics. I encourage you to be active in every class session. This extra credit for participation serves as a way to credit you with the effort and work you are putting into the class in and out of the classroom. However, I understand that we all have different levels of comfort regarding speaking in class. Participation will thus be counted through Webclicker questions.
You will earn full credit for participation if you attend 75% (21 of 28) of class lectures. If any lectures are pre-recorded and not held in person, then all students will receive credit for attendance. We will count attendance through answers to any of the poll questions on the free Webclicker platform.
If you have to miss class repeatedly, please email me as soon as possible to discuss ways to help you participate in classroom activities.
Modality
This course is conducted in person. Recordings of the lectures will be available for students to review as a Podcast and uploaded to the Canvas Media Gallery. On occasion, it will be necessary to hold class asynchronously by posting a pre-recorded lecture in the Canvas Media Gallery.
Integrity of Scholarship
University rules on integrity of scholarship will be strictly enforced. By taking this course, you implicitly agree to abide by the UCSD Policy on Integrity of Scholarship described here. In particular,
all academic work will be done by the student to whom it is assigned, without unauthorized aid of any kind.
Incidents which violate the University’s rules on integrity of scholarship will be taken seriously. In addition to receiving a zero (0) on the assignment/exam in question, students may also face other penalties, up to and including, expulsion from the University. Should you have any doubts about the moral and/or ethical implications of an activity regarding the course, please see the instructor.
Some examples of specific ways this policy applies to CSE 20 include:
- Do not discuss solutions to homework problems with people besides your homework partner (except during office hours, with the instructional team).
- Do not share written solutions with other groups.
- Do not collaborate on or copy parts of or whole exams.
- Do not use online answer resources such as Chegg or CourseHero for any assignments
- Do not use an AI such as ChatGPT for any assignments
Inclusive Teaching
We are committed to fostering a learning environment for this course that supports a diversity of thoughts, perspectives and experiences, and respects your identities (including race, ethnicity, heritage, gender, sex, class, sexuality, religion, ability, age, educational background, etc.). Our goal is to create a diverse and inclusive learning environment where all students feel comfortable and can thrive.
Our instructional staff will make a concerted effort to be welcoming and inclusive to the wide diversity of students in this course. If there is a way we can make you feel more included please let one of the course staff know, either in person or by email.
We also expect that you, as a student in this course, will honor and respect your classmates, abiding by the UCSD Principles of Community (https://ucsd.edu/about/principles.html). Please understand that others’ backgrounds, perspectives and experiences may be different than your own, and help us to build an environment where everyone is respected and feels comfortable.
If you experience any sort of harassment or discrimination, please contact the instructor as soon as possible. If you prefer to speak with someone outside of the course, please contact the Office of Prevention of Harassment and Discrimination: https://ophd.ucsd.edu/.
Students with Disabilities
We aim to create an environment in which all students can succeed in this course. If you have a disability, please contact the Office for Students with Disability (OSD), which is located in University Center 202 behind Center Hall, to discuss appropriate accommodations right away. We will work to provide you with the accommodations you need, but you must first provide a current Authorization for Accommodation (AFA) letter issued by the OSD. You are required by University policy to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance so that accommodations may be arranged.
Course Summary:
| Date | Details | Due |
|---|---|---|