Syllabus for 336 Spring 2003

Syllabus for 336 Fall 2003

Unique number 52430

Time: MWF 11-12

Room: RAS 213

Instructor: John Werth

Phone: 471-9527

Office: Taylor 4.115D

Office Hours: MF 12-1, W 1-2 and by appointment

TA: Yulin Li

E-mail: yulinli@cs.utexas.edu

Office Hours: T 2-3:30, Th 1:30-3; Both in PAI 5.40

Text: Discrete Mathematics and its Applications, Fifth Edition, Rosen, McGraw Hill

Prerequisite: CS 307, CS 315, Math 408C and Phil 313K all with grade of C or better.

Exams: Midterm 1: Friday October 3, in class

Midterm 2: Friday November 7, in class

Final Exam: Thursday December 11, 2-5

Grading: Homework 25%

Pop Quizzes 15%

Midterms 15% each

Final Exam 30%

No late papers or makeups on the homework. The lowest grade will be dropped.

There will be no makeups on the pop quizzes. The lowest grade will be dropped.

There will be no makeups on the midterms. If a midterm is missed the other

midterm and the final will both have their weights increased to compensate.

Approximate topics and schedule in class days:

4 days - Review of material from Philosophy 313K: Propositional and Predicate Logic, Proofs, Sets and Functions - Rosen Chapter 1
5 days - Growth of Functions, Complexity of Algorithms – Rosen Sections 2.1-2.3
5 days – Proofs, Review of induction, Recursive definitions, Structural induction and recursive algorithms, More on complexity – Rosen Sections 3.1-3.5
5 days – Counting, Permutations and Combinations Rosen 4.1-4.3
3 days - Recurrence Relations - Rosen 6.1-6.2
5 days –Graphs – Rosen sections 8.1 – 8.6
4 days – Trees – Rosen sections 9.1 - 9.5
10 days – Program correctness – Rosen 3.6, Handouts
1 day - Review

Homework 3 !This homework is now due Monday September 22!

Homework 4 !The problems to study for the Pop Quizzes have changed!

Homework 6 !This homework is now due Wednesday October 22!

Homework 7 !This homework is now due Friday October 31!