• HOME
• DEPARTMENT
• PEOPLE
• UNDERGRADUATE
• GRADUATE
• COURSES
• RESEARCH
• INDUSTRIAL AFFILIATES

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

Student Outcomes:

• An ability to apply knowledge of mathematics, science, and engineering
• A recognition of the need for, and an ability to engage in life-long learning
• An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice

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.