ECS 20 DISCRETE MATHEMATICS FOR COMPUTER SCIENCE (4) I,II,III

Lecture: 3 hours

Discussion: 1 hour

Prerequisite: Math 21A

Grading: Letter; homework (30%), midterm (25%) and final (45%)

Catalog Description:
Discrete structures and applications in computer science. Proofs, particularly induction. Introduction to propositional logic, logic circuit design, combinatorics, recursion and solution of recurrence relations, analysis of algorithms, graph theory and trees, finite state machines. Not open for credit to students who have taken course 100.

Expanded Course Description:

1. Brief review of important basic functions: exponentials, algorithms, arithmetic sums, geometric sums, elementary number theory.
2. Propositional logic and applications to logic circuit design.
3. Mathematical proofs. Induction and related proof techniques. Examples of induction taken from applications where the underlying order is not clear. Non-trivial proofs from number theory or abstract algebra.
4. Recursion and its relation to induction.
5. Recurrence relations and their solution: emphasis on divide and conquer relations and solution through expansion and induction; master method.
6. Algorithms and introduction to complexity: asymptotic notation; derivation and solution of recurrence relations to capture running time.
7. Combinatorics and counting: permutations, combinations, non-trivial counting problems; discrete probability.
8. Graphs and trees: planarity, Euler tours, five color theorem; relation between tree height and size; binary trees and applications.
9. Finite state machines: regular languages and grammars, proofs of non-regularity context- free grammars.

Textbook:
Rosen, Discrete Mathematics and It’s Applications Custom, McGraw-Hill, 20032

Computer Usage:
None

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

Program Outcomes:s:


• The ability to work independently
• The ability to effectively express ideas through written communication
• The ability to construct appropriate abstractions to manage complexity and to think creatively about new problems
• The ability to acquire the foundations to do well in graduate school
• The ability to acquire the foundations to be a life-long learner

Instructors: D. Gusfield, K. Levitt, C. Martel, P. Rogaway, Z. Bai

Prepared By: D. Gusfield, P. Rogaway, Z. Bai (May 2001)

Overlap Statement:

ECS 20 overlaps with Mathematics 108 (Introduction to Abstract Mathematics) in the introduction to propositional logic and mathematical proofs which are a minor part of both courses. ECS 20 is a fundamental, preparatory course for upper division ECS courses.

5/06