Sample Course 1 - - CSE 20 UCSD

S. Gill Williamson

OVERVIEW: This lower division course covers basic discrete mathematics, Course 1, of Lectures in Discrete Mathematics, Bender and Williamson. Each unit of study has a final Multiple Choice Questions for Review section. We begin our discussion of each unit by presenting these multple choice questions and referring, as needed, to the explanations and exercises in the unit. The students are expected to be able to understand these canonical multiple choice questions, answer similar questions and explain their answers. Two midterms (approximately week 5 and 8) and final exam are given.

Unit BF
Multiple Choice for BF

Boolean Functions and Computer Arithmetic: In this unit, we emphasize Boolean functions over number systems. The discussion of number systems relates to modular arithmetic (Unit NT) and is a special case of the study of decision trees in Course 2 (Unit DT). Our balance between these two subjects reflects the multiple choice questions.

Unit Lo Multiple Choice for Lo

Logic: The material in this unit is very important and used in the rest of the course. We use the notational precision of predicate logic as much as possible in presenting subsequent material. The multiple choice questions give the main ideas.

Unit NT Multiple Choice for NT

Number Theory and Cryptography: We emphasize Section 1 and the material in Section 2 through the Euler phi function. We skip the Cryptography on the Internet material. Again, the multiple choice questions represent our emphasis.

Unit SF Multiple Choice for SF

Sets and Functions: This material is fundamental to discrete mathematics. Combined with the notational conventions of Unit Lo, the students learn how to make precise statements in the context of elementary set theory.

Unit EO Multiple Choice for EO

Equivalence and Order: This material is important for both computer science students and mathematics students. Linear orders and generalized lexicographic orders are very useful. Unit DT in Course 2 extends and applies these ideas.

Induction/Recursion infinite Sequences/Series

Unit IS: Induction, Sequences and Series: This section is generally not covered in a one quarter course. We do use induction on a number of examples and note the relationship between induction and recursion. The first part of this unit is a good reference for reviewing induction. Unit DT in Course 2 treats induction and recursion in more depth.

Solutions MA 15A CSE 20
Index All Units MA 15A CSE 20

Optional introduction to algebra: At UCSD, CSE 20 is co-listed with Math 15A. It is useful for the math students to be exposed to some basic algegraic terminology. It is also useful for them to experience learning some proofs. This experience doesn't hurt the computer science students either. Below is a short introduction to algebra with some suggested proofs to be learned (memorized is fine). The students should show that they can write these proofs closed book. They should have one or two repeated opportunities if they get it wrong.

Short Algebra Introduction

Moment's Notice: Be ready to prove "on a moment's notice" that the ring of polynomials with integral coefficients, Z[x], is not a principal ideal domain (PID). The proof is on the web.

Moment's notice: Prove the Euclid-Euler theorem characterizing even perfect numbers. See Example 13 page Lo-17 for a statement. Lo-22 problem 2.21 relates. There are proofs on the web.

Moment's notice: Prove that the ring of integers, Z, is a principal ideal domain. Namely, given any ideal A in Z there is an integer a in A such that A = {ax | x in Z }. Modify Theorem 5 on page NT-16 or see web.