CSE 20: Discrete Math for CS --- FALL 2019 ARCHIVED SITE: DEPRECATED
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?
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. Use the link on the class schedule for one-on-one appointments. 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