CSE 20: Discrete Math for CS
In this class, you will use careful mathematical modeling, problem solving, and clear and precise communication to explore key questions in Computer Science: How do we decide (and prove) what's true? How do we use mathematics to give multiple representations of data and computation?
Final exam and grades announcement due to COVID-19 Campus Impacts
In light of the extraordinary measures enacted on campus due to the COVID-19 pandemic, the following policy changes to CSE 20's final exam are being made.
- The final exam will be an online assignment on Gradescope available Wednesday 11:30am-2:30pm . It may have a combination of True/False, multiple choice, select-all-that-apply, and free-response questions. During the exam, I will be available via Zoom for questions about the exam and will display via a public Google doc any answers I give to these questions.
- To take the exam, ensure you are located somewhere with reliable internet for the duration of the exam period. If you will have trouble with this requirement contact me ASAP so we can work something out.
- The exam will be open-book: you may use your notes for CSE 20, along with all provided CSE 20 class material this quarter. No collaboration or help-seeking / help-giving will be allowed. No online resources other than those provided for this quarter's CSE 20 offering are allowed.
- Your overall grade will be the maximum of the following two options:
- Option 1: 1% final + 30% midterm + 65% assignments + 4% participation.
- Option 2: 15% final + 30% max(midterm, average on assignments up to and including 4-warmup)+ 50% assignments + 5% participation.
- FAQ: How is the participation score calculated? A: We will calculate the maximum of (1) warmup assignment average, and (2) average clicker participation credit after dropping the lowest 9 classes (3 weeks) and accounting for survey completion.
- FAQ: Will my lowest assignment score from each category still be dropped? A: Yes. When we calculate your assignment average in either one of the scenarios, we will drop the lowest assignment score from each category and use the relative weighting of the three categories announced at the start of the quarter.
Minimum letter grade cutoffs
After your weighted average is calculated as the maximum of Option 1 and Option 2 above, letter grades will be assigned based on the following grading scale:| A+ | A | A- | B+ | B | B- | C+ | C | C- | D, F |
| >95 | 88-94.99 | 85-87.99 | 82-84.99 | 78-81.99 | 75-77.99 | 72-74.99 | 68-71.99 | 60-77.99 | Below 59.99 |
Syllabus
Welcome to CSE20! If you ever wondered "What sort of mathematics do I need for computer science?", this course will provide some of the answers. In particular, you will have the opportunity to learn basic concepts about algorithms, computer arithmetic, number systems, logic, proofs, modular arithmetic, recursion and induction, among others. These are some of the essential ingredients in the toolkit of every computer scientist.
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) termination and correctness of some algorithms.
- Define and use classical algorithms and algorithmic paradigms e.g. Euclidean algorithm, greedy optimization.
- 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 and use normal forms.
- Apply proof techniques, including direct proofs and proofs by contradiction.
- Distinguish valid from invalid arguments.
- Craft proofs and arguments at different levels of formality, including prose and symbolic notation as appropriate.
- 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, including strings and trees.
- Identify and be able to prove basic properties of sets, functions, and relations.
- Distinguish between finite, countable, and uncountable sets.
Our drop-in office hours are listed in the calendar above. For other questions use Piazza or Prof. Minnes' direct email is minnes@eng.ucsd.edu .
Textbook and supplies
The required textbook for this course is
This book is on reserve in the library and is also available in hardcopy at the UCSD Bookstore or many online retailers. An eBook is available as a purchasing option for this course. You can access this eBook by clicking the RedShelf tool within TritonEd/Canvas. If you opt-in to this eBook by clicking the Opt-in Now button your student account will be charged directly. You will also receive an email with the exact amount of this charge. Within the add/drop period you may also opt-out of this option if you decide you’d rather use an alternate format. There are not many differences between the 7th edition and other recent editions, so you may be able to save some money by purchasing an older edition of the textbook. All posted reading assignments refer to the chapter and section numbers of the 7th edition. This guide lists the corresponding sections in the 5th and 6th editions.
Online Self Assessments and Extra Examples from the book are here.
An iClicker2 is required to record in-class participation, and is available for purchase at the bookstore. You may use second-hand clickers as well. You will register your clicker directly for this class specifically, using this form: Register your iClicker here.
A useful but optional supplementary resource is