CPSC 289 Special Topics on Discrete Structures for Computing

Fall 2008
Syllabus

Instructor: Andreas Klappenecker
Where: Scoates Hall 214
When: MWF 10:20am-11:10am
Office: HRBB, Room 509B
Office Hours: TBA

Prerequisites

Math 151, Programming skills

Required Textbook

Kenneth Rosen, Discrete Mathematics and Its Applications, 6th ed., McGraw-Hill, 2007.

Optional Reading

Jiri Matousek, Jaroslav Nesetril, An Invitation to Discrete Mathematics, Oxford University Press, 2nd edition, 2008
[More advanced than our textbook, but a pleasure to read. Contains many elegant proofs]
Kees Doets, Jan van Eijck, The Haskell Road to Logic, Maths, and Programming, King's College London Publications, 2004
[Experiment with a functional programming language while learning discrete mathematics. Unfortunately, the recommendations concerning proof style given there contradict our philosophy.]

Additional materials will be distributed during the course.

Course Goals

The main goal of this course is to provide some mathematical foundations that are beneficial in the analysis of algorithms.
A secondary goal is to provide an introduction finite automata and Turing machines

Course Description

The course will cover the following tentative list of topics:

Proofs, Elements of Logic (Chapter 1)
Sets, functions, sequences, and sums (Chapter 2)
Relations (Chapter 8)
Algorithms and their complexity (Chapter 3)
Induction and recursion (Chapter 4)
Counting (Chapters 5 and 7)
Solving recurrences (Chapter 7)
Models of computation (Chapter 12)

Grades

Exam 1: 20%
Exam 2: 20%
Final Exam: 20%
Assignments: 25%
Quizzes: 10%
Culture: 5%

The course grades will be assigned according to the scale A=90-100%, B=80-89%, C=70-79%, D=60-69%, F 0-59% of the total points available. A curve is possible, but is not expected. Cheating or plagiarism on any exam or assignment will be punished, and a single offense can lead to a final grade of F*.

Collaboration

For the assignments in this class, discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. Reference every source you use, whether it be a person, a book, a paper, a solution set, a web page or whatever. You MUST write up your assignments in your own words. Copying is strictly forbidden.

Academic Integrity Statements

The Aggie Honor Code is "An Aggie does not lie, cheat, or steal or tolerate those who do." Upon accepting admission to Texas A&M University, a student immediately assumes a commitment to uphold the Honor Code, to accept responsibility for learning, and to follow the philosophy and rules of the Honor System. Students will be required to state their commitment on examinations, research papers, and other academic work. Ignorance of the rules does not exclude any member of the TAMU community from the requirements or the processes of the Honor System. For additional information please visit: http://www.tamu.edu/aggiehonor/ .

Americans with Disabilities Act Policy Statement

The Americans with Disabilities Act (ADA) is a federal antidiscrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact the Department of Student Life, Services for Students with Disabilities in Cain Hall, Rm. B118, or call 845-1637.