ECS 020: Discrete Mathematics For Computer Science

Subject
ECS 020
Title
Discrete Mathematics For Computer Science
Status
Active
Units
4.0
Effective Term
2017 Winter Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
Description
Discrete mathematics of particular utility to computer science. Proofs by induction. Propositional and first-order logic. Sets, functions, and relations. Big-O and related notations. Recursion and solutions of recurrence relations. Combinatorics. Probability on finite probability spaces. Graph theory. GE Prior to Fall 2011: SciEng. GE: SE, QL.
Prerequisites
C- or better in MAT 016A or MAT 017A or MAT 019A or MAT 021A
Enrollment Restrictions
Pass One open to Computer Science, Computer Science Engineering, Computer Engineering, and Cognitive Science Majors only.
  • Propositional and first-order 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. Non-trivial 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, McGraw-Hill, 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:

  • Learn 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 upper-division ECS courses.

Outcomes

1Xan 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 multi-disciplinary 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
9Xa recognition of the need for, and an ability to engage in life-long learning
10 knowledge of contemporary issues
11Xan 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 computer-based 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

Course Category

Lower Division