CPSC 289 Sec 502: Special Topics on Discrete Structures for Computing
Spring 2007

Announcements

• 5/1: Review for Final Exam is now available.

• 4/24: I just added the final problems to HW 9 (for Sec 8.4).

• 4/18: Homework 9 is now available, due Thursday, Apr 26.

• 4/18: I just updated notes10.txt to include material for all of Chapter 8 that we will cover.

• 4/17: The Distinguished Lecture by Prof. Nancy Lynch, originally scheduled for April 20, has been cancelled. Therefore, culture assignment 5 is changed to be either attending any CS Department seminar and writing a report or reading any CS journal article and writing a report. Follow the same guidelines as for DLS seminars and their substitutions.

• 4/11: Please study the notes for yesterday's lecture (notes10.txt) for correction to material on antisymmetric property.

• 4/10: Homework 8 is now available, due Tuesday, Apr 17.

• 4/3: I just updated Notes 9 to include the rest of Ch 5.

• 3/30: Review for Exam 2 is now available.

• 3/27: Homework 7 is now available, due Tuesday, Apr 3.

• 3/22: Fenghui's office hours are changed. They are Tuesdays 3:00 - 5:00 PM and Fridays 2:00 - 4:00 PM.

• 3/20: Homework 6 is now available, due Tuesday, Mar 27.

• 3/20: Slight change in the schedule: next topic will be solving divide-and-conquer recurrences (Ch 7, Sec 3), followed by counting (Ch 5).

• 3/7: Homework 5 is now available, due Tuesday, Mar 20.

• 2/27: Homework 4 is now available, due Tuesday, Mar 6.

• 2/20: Clarification about logs and exercise 24(d) in Section 3.2 is here.

• 2/16: Review for Exam 1 is now available.

• 2/12: Homework 3 is now available, due Tuesday, Feb 20.

• 2/12: Exam 1 has been definitively scheduled for Thursday, Feb 22.

• 2/12: Distinguished Lecturers Kai Li and Bill Wulf have had to postpone their visits. Therefore, culture assignments 2 and 3 are changed to be either attending any CS Department seminar and writing a report or reading any CS journal article and writing a report. Follow the same guidelines as for DLS seminars and their substitutions. I have also adjusted the due date for culture assignment 2 because of Exam 1.

• 2/8: Following our conversation in class on Tuesday, I've shortened HW 2 somewhat by making a few of the problems optional. You should still know what the optional questions are asking about, though.

• 2/7: More on accessing IEEE Computer and Communications of the ACM for culture report 1: You can go to Evans Library to get copies. Or you can access them from the Evans Library web page: http://library.tamu.edu/portal/site/Library/. Click on Indexes/Databases, put in "IEEE" as your search term, and then click on "IEEE Xplore". This is the IEEE digital library - search for "IEEE Computer". Do the similar thing for "ACM".

• 2/5: Homework 2 is now available, due Tuesday, Feb 13.

• 1/30: Fenghui will probably be unable to be in his office hours on Tuesday. He will make them up on Wednesday afternoon and/or Thursday morning. Please email him about meeting with him (fhzhang (at) cs.tamu.edu).

• 1/30: Fenghui's office hours on Thursdays are changing to 1 - 3:50 PM.

• 1/25: If you cannot attend any CS department seminars before culture 1 report is due (on Feb 8), you may read an article from one of the following two journals: Communications of the ACM or IEEE Computer and write your report on that. Both journals are available on the web, if you are on a computer that is behind the TAMU firewall (TAMU has subscriptions).

• 1/23: Homework 1 is now available, due Thursday, Feb 1. I am postponing culture 1 report to Feb 8.

• 1/22: Due to other scheduling constraints, I had to change my office hours that were listed on the paper syllabus I handed out in class last week. My office hours this semester will be Mondays 2:30 - 4:00 and Wednesdays, 1:30 - 3:00. Contact me to arrange other times if you have conflicts.

• 1/18: My own typed lecture notes are available at the top of the calendar section of this web page.

• 1/18: Typo on paper syllabus handed out in class regarding culture reports. Please refer to information posted below in this web page.

• 1/18: SEC Engineering Career Fair Jan 22-23

• Classes cancelled Jan 16-17 due to bad weather.

Back to beginning

Syllabus

Teaching Assistant: Fenghui Zhang
Office: 315D H.R. Bright Bldg
Office Hours: Tuesdays 3:00 - 5:00 PM and Fridays 2:00 - 4:00 PM; other times by appointment. (*updated 3/22/07*)
Email: fhzhang (at) cs.tamu.edu
Office Phone: 845-0652

Prerequisite: MATH 151

Lecture: Tuesdays and Thursdays, 11:10 AM - 12:25 PM, HRBB 124.

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

Course URL: http://faculty.cs.tamu.edu/welch/teaching/289.s07

• Provide mathematical foundations to allow the students to analyze computer algorithms, both for correctness and performance
• Provide introduction to two models of computation: finite automata and Turing machines

Your grade will be based on four components:

• exams 60% - There will be two mid-term exams and one final exam, each worth 20%. The exams will be held in class.

• quizzes 10% - There will be 11 short weekly quizzes, consisting of a few simple questions (short answer, true-false, or multiple choice) concerning the reading and/or the material covered in the last class. The purpose of the quiz is to encourage you to do the reading in advance and to stay caught up in the class. Your lowest quiz grade will be dropped.

• homework 25% - Pencil and paper exercises and programming assignments.

• culture 5% This component is to round out your classwork. Attend and write short reports on five computer science seminars. More details are here.

There will be no make-up exams and no late assignments accepted except for university-excused absences. Please discuss unusual circumstances in advance with the instructor when possible.

Course grades will be assigned according to this scale:

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. Every assignment must be turned in with this cover sheet, which lists all sources you used.

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 (ADA) 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.

Back to beginning

Calendar

• readings
• quizzes
• homework
• exams
• culture activities

• details on the assignments
• exam reviews

Lecture notes:

• Notes 1: Introduction; Propositional Logic. 1/18
• Notes 2: Predicate Logic. 1/23
• Notes 3: Proofs. 1/25
• Notes 4: Sets, Functions, Sequences and Sums. 1/30 and 2/1
• Notes 5: Algorithms and Complexity. 2/8, 2/13, 2/15
• Notes 6: Induction and Recursion. 2/27, 3/1, 3/6
• Notes 7: Recursive Algorithms; Program Correctness. 3/8, 3/20
• Notes 8: Divide-and-Conquer Algorithms and Recurrences. 3/22
• Notes 9: Counting. 3/27, 3/29
• Notes 10: Relations. 4/10, 4/12, 4/17, 4/19
• Notes 11: Models of Computation. 4/24

Back to beginning

Culture Activities

You are to attend five computer science seminars and write a report on each one. Four of the seminars are those making up the Department of Computer Science Distinguished Lecturer Series; the fifth seminar is of your choosing from the Department's other seminar series (see here for a list). Each report is to be one to two pages long, typed, and must include

• date and title of talk, name and affiliation of speaker;
• summary of the talk;
• at least one comment about the paper or question that it raised in your mind, indicating that you have thought critically about the material presented.

If you have a schedule conflict with a particular lecture, you may substitute a report on a journal article written by the speaker. Such a report must include

• correct bibliographic information for the paper (title of article; names of all authors; name of journal with volume, number, date and page numbers)
• summary of paper contents
• at least one comment about the paper or question that it raised in your mind, indicating that you have thought critically about the material presented.

DO NOT PLAGIARIZE! You must write up your summary in your own words. See academic integrity policy in the syllabus.

Here are some tips for getting full credit on your reports.

Distinguished Lecture dates and report due dates are indicated in the calendar and reproduced here for convenience: (*updated 2/12/07*)

• Culture report 1 due Thu, Feb 8, on CS seminar of your choice
• Culture report 2 due Thu, Mar 1, on CS seminar of your choice
• Culture report 3 due Thu, Mar 22, on CS seminar of your choice
• Distinguished Lecture by Rosalind Picard, MIT, Mon, Mar 19, 4:10 PM in 124 Bright
• Culture report 4 due Thu, Apr 12, on Picard lecture/paper
• Distinguished Lecture by Nancy Lynch, MIT, Fri, Apr 20, 4:10 PM in 124 Bright -- CANCELLED
• Culture report 5 due Thu, Apr 26, on CS seminar of your choice or a paper by Nancy Lynch

Back to beginning

Useful Links

• Textbook web site

• Turn-in program information

Computing-Related at TAMU

• Texas A&M Computing Society (TACS) -- student organization for those interested in computing. Affiliated with the two main professional organizations, ACM and IEEE Computer Society.

• Computer Science Department, TAMU

• Student Computing and Information Page: central source of information about student computing at TAMU.

• Schedule of short courses offered by the CIS Computer Help and Training Group.

Careers and Mentoring

• Office of Honors Programs and Academic Scholarships

• CS Department Student Research Information

• TAMU Co-operative Education

• Computing Research Association Distributed Mentor Project for Undergraduate Females in Computer Science and Engineering: If you think you might be interested in graduate school in CS or CE, this could be a great opportunity for you if/when you are a sophomore or junior. Be thinking ahead!

Back to beginning