ECS 20 DISCRETE MATHEMATICS FOR COMPUTER SCIENCE (4 units)
Format
Lecture: 3 hours
Discussion/Laboratory: 1 hour
Catalog Description
Discrete mathematics of particular utility to computer science. Proofs by induction. Propositional and firstorder logic. Sets, functions, and relations. BigO and related notations. Recursion and solutions of recurrence relations. Combinatorics. Probability on finite probability spaces. Graph theory.
Prerequisite: Grade of C or better in Mathematics 16A, 17A or 21A
Credit restrictions / cross listings: None
Summary of course contents
 Propositional and firstorder logic
 Elementary set theory.
 Functions, relations, and equivalence relations.
 Induction and recursion. Inductive definitions. Examples of induction taken from domains it is not obvious what one is inducting on.
 The pigeonhole principle.
 Asymptotic notation: O, W, Q.
 Derivation and solution of recurrence relations. Divide and conquer relations. Solutions through expansion and proofs by induction.
 Combinatorics and counting. Permutations, combinations. Nontrivial counting problems.
 Discrete probability
 Graphs and trees. Terminology. Eulerian and Hamiltonian graphs. Graph colorings. Basic properties of trees.
Goals: Students will: (1) learn fundamental ideas and techniques from discrete mathematics; (2) improve their ability to write concise and rigorous proofs; (3) improve their ability to understand mathematical definitions and proofs; and (4) enhance their general mathematical sophistication.
Illustrative reading
 K. Rosen, Discrete Mathematics and Its Applications, 7th edition, McGrawHill, 2011.
 M. Lipson, Schaum’s Outline of Discrete Mathematics, revised 3rd edition, 2009.
 D. Velleman, How to Prove it: A Structured Approach. Cambridge University Press, 1994.
ABET Category Content
Engineering Science: 4 units
Engineering Design: 0 unit
Goals
Students will:
 rn fundamental techniques in discrete mathematics for application to computer science
 learn proof methods to transform intuition into proofs and know the distinction between proof and opinion
 enhance their general mathematical sophistication in order to deal with and create complex and convincing arguments
GE3
Science & Engineering
Quantitative Literacy
Overlap: The course overlaps with Math 108 (Introduction to Abstract Mathematics) but focusses more on problems and techniques of utility in computer science. The course includes topics like asymptotic notation, graphs, and trees, which Math 108 does not include, while it omits topics like cardinal numbers, which Math 108 does include. ECS 20 is a fundamental, preparatory course for upperdivision ECS courses.
Instructors: Staff
History: 2012.10.11 (P. Rogaway): Replaced catalog description and summary of course contents with more accurate versions; revised overlap description. Prior course description went back to May 2001 (Z. Bai, D. Gusfield, P. Rogaway).
Outcomes
1 
X 
an ability to apply knowledge of mathematics, science, computing, and engineering 
2 

an ability to design and conduct experiments, as well as to analyze and interpret data 
3 

an ability to design, implement, and evaluate a system, process, component, or program to meet desired needs, within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability 
4 

an ability to function on multidisciplinary teams 
5 

an ability to identify, formulate, and solve computer science and engineering problems and define the computing requirements appropriate to their solutions 
6 

an understanding of professional, ethical, legal, security and social issues and responsibilities 
7 

an ability to communicate effectively with a range of audiences 
8 

the broad education necessary to understand the impact of computer science and engineering solutions in a global and societal context 
9 
X 
a recognition of the need for, and an ability to engage in lifelong learning 
10 

knowledge of contemporary issues 
11 
X 
an ability to use current techniques, skills, and tools necessary for computing and engineering practice 
12 

an ability to apply mathematical foundations, algorithmic principles, and computer science and engineering theory in the modeling and design of computerbased systems in a way that demonstrates comprehension of the tradeoffs involved in design choices 
13 

an ability to apply design and development principles in the construction of software systems or computer systems of varying complexity 