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
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
ABET Category Content
Engineering Science: 4 units
Engineering Design: 0 unit
Goals
Students will:
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 