CSE 20: Discrete Math for CS --- SPRING 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.
Announcements and Q&A are through Piazza (sign up link: piazza.com/ucsd/spring2019/cse20).
Our office hours and locations can be found in the calendar above.
For private questions to the instructors: Prof. Minnes' email is minnes@eng.ucsd.edu and Prof. Politz's email is jpolitz@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.
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 also required, and is available for purchase at the bookstore. You will register your clicker for this class specifically, using this form: Register your iClicker here.
A useful but optional supplementary resource is