ECS 20

Course Syllabus

Winter 2012

 

Name

Title

E-mail

Room

Office Hours

Sean Davis

Lecturer

ssdavis@ucdavis.edu

3052 Kemper

TR 8:30-10, 3:15-5; and by appointment.

Teng Wang

TA

wangtengthu@gmail.com

53 Kemper

M 2:30-4:30, W 5-7

Julia Matsieva

TA

julia.matsieva@gmail.com

53 Kemper

MW 10-12

 

Web page:  http://csiflabs.cs.ucdavis.edu/~ssdavis/20/homepage.html

Newsgroup:  ecs20 (staff and students), and ecs20.staff (staff only write) on news.cs.ucdavis.edu.  Anything I post to ecs20.staff will also be posted to ecs20.  You can earn 4 points of extra credit by posting a reply to the appropriate topic in ecs20 by midnight January 13th.

E-mail to Sean should only be regarding personal matters and not questions about assignments or tests, and must come from an ucdavis.edu e-mail account.  All course questions should be posted to the ecs20 newsgroup.

Required Materials:  Lipschutz, Seymour, Schaum’s Outline of Theory and Problems of Discrete Mathematics, 3rd ed., NewYork, NY, McGraw-Hill, 2007.  ISBN 978-0-07-161586-0

Prerequisites:  Math 21A or equivalent with a grade of C- or better.

Course Objectives:

  1. Students will be able to apply propositional logic to logic design, and natural language specifications.
  2. Students will be able to choose and apply methods of proof to problems including recurrence and abstract algebra.
  3. Students will be able to determine the time complexity of algorithms including recurrence relations.
  4. Students will be able to solve non-trivial counting problems, and determine discrete probabilities.
  5. Students will be able recognize and understand applications of graphs and binary trees.
  6. Students will be able to covert between any of regular languages, regular grammars, automata, and English descriptions of their productions.

 

Approximate Course Grading

Homework

40%

Two midterms

30%

Final

30%

Class effort/participation

 5% (extra credit)

Letter grades will be approximately: A = 90+% ; B = 80-89%; C = 70-79%; D = 60-69%; F <60%

Work Input/Output

 

Discussion:  M 9-9:50 in 176 Chem (Julia), F 9-9:50 in 176 Chem (Teng)

 

Exams:  Exams are cumulative, closed book, and closed notes.  The final will be Friday, March 23rd , 8:00 – 10:00am in 126 Wellman.

Tentative Schedule

Dates

Subjects

Reading

1/10

Introduction, logic and propositional calculus

Chapter 4

1/12

Propositional calculus cont’d.

Chapter 4

1/17

Proof techniques

Chapter 1.8 and proof handout

1/19

Set theory

Chapter 1

1/24

Set theory cont’d, Functions and algorithms

Chapter 1, 3

1/26

Functions and algorithms cont’d

Chapter 3

1/31

Techniques of  counting

Chapter 5

2/2

Midterm #1, Chapters 1, 3, 4 and proof handout

None

2/7

More techniques of counting

Chapters 5 and 6

2/9

Recursion

Chapter 6

2/14

Probability

Chapter 7

2/16

Probability cont’d

Chapter 7

2/21

Graph theory

Chapter 8

2/23

Graph theory cont’d

Chapter 8

2/28

Binary Trees

Chapter 10

3/1

Midterm #2, Chapters 1, 3-8, and proof handout

None

3/6

Binary Trees cont’d

Chapter 10

3/8

Languages,  automata, and grammars

Chapter 12

3/13

Languages, automata, and grammars

Chapter 12

3/15

Finite State Machines

Chapter 13