CS 275 Spring 2007

University Handbook Description

 Topics in discrete math aimed at applications in Computer Science. Fundamental principles: set theory, induction, relations, functions, Boolean algebra. Techniques of counting: permutations, combinations, recurrences, algorithms to generate them. Introduction to graphs and trees.

Prerequisites: MA 113 and CS 115.

Requirements, Goals, Homework, Exams, and a Few Serious Warnings

Students need to be familiar with basic algebra and calculus, basic programming techniques in a general purpose programming language such as C++, data structures including lists, elementary algorithms such as searching and basic sorting, and basic concepts of recursion.

Students will develop knowledge of a variety of mathematical tools applicable in computer science. Specifically, students will be able to

• construct inductive proofs
• apply set algebra
• apply elementary logic
• enumerate combinatorial objects
• solve recurrence relations

Homework will be due on Wednesdays in your discussion section. Do not bring it to me in my office. There will be proofs, problem solving, and at least one short computer program on weeks that homework is due. I would prefer that you use a program like Word, WordPad, LaTeX, or a text editor to do the written parts of the homework. You should use C++ for the programming.

Your grade will be made up of a combination of the homework and exam scores. In general I give points for mistakes. So the best possible score is a zero. I normally curve course and will not have a good idea what the curve will look like until after the first exam and the first few homeworks. Stay tuned, but rest assured that if you do miserably on either all of the homeworks or exams, you will fail the course.

Warnings:

• Read the textbook on a regular basis. It is long winded, but can be read fairly quickly since you will learn what to skip. I assume that you are reading the textbook in advance of what I am lecturing on.
• Watch the homework web page every Tuesday and Thursday. I will add problems to it twice a week and just expect you to find the new problems. If you miss homework or exams, be prepared with written documentation from a university approved source (e.g., a doctor of medicine) and it will help if you contact me well in advance. Otherwise you could easily fail this course.
• Exam dates will be posted by the week before and will be given in class on Tuesday or Thursday. They will listed at the top of course web pages. I assume you will monitor the class web pages yourself. Look now.
• If you library or web search the solution to a homework or exam problem, cite the source. I do not penalize good scholarship, which searching available, nonliving resources is part of.
• It is quite easy to either cheat or plagiarize in this course, even by accident. Do not exchange code unless you have been explicitly told to do so. Do not swap printed or electronic versions either. Do not look over a shoulder and take notes. Do not try to be a lawyer and find a clever way of doing something similar to these examples. Getting caught cheating or plagiarizing will result in a grade of E and possibly much worse, including expulsion from the university and legal proceedings against you. I have zero tolerance for cheaters. There are enough interesting things to do in life without experiencing being tossed out of school.

Date	Exam	Solution	Median	Average	Bar chart
2/1/2007	exam1	exam1-soln	28	25	bar-exam1
3/1/2007	exam2	exam2-soln	22	25	bar-exam2
3/29/2007	exam3	exam3-soln	12	15	bar-exam3
4/19/2007	exam4	exam4-soln	26	29	bar-exam4
5/3/2007	final

The overall grading is min{final exam, (65*(your exams total / exams possible total) + 35*(your homeworks total / homeworks possible total))}, which is shown in bar-overall with a median of 25 and an average of 25 as of 5/3/2007. The grade ranges are 0-15 (A), 16-30 (B), 31-35 (C), 36-40 (D), and 41-100 (E).

The final has 100 possible points that you can accumulate. If you get 0-15 on it, then you can raise your course grade to an A. Similarly for 16-30 (B), 31-35 (C), and 36-40 (D). The worst that you will get for a grade is the letter grade you have earned through exams 1-4 and the homeworks prior to the final. If you already have an A in the course, you will not take the final.

Textbook

You are expected to read and master the contents of

• K. H. Rosen, Discrete Mathematics and Its Applications, 5th edition, McGraw Hill, Boston, 2003.
  ISBN-10: 0072424346. Book web site is http://www.mhhe.com/math/advmath/rosenindex.mhtml.

Other books that might be useful are

• R. P. Grimaldi, Discrete and Combinatorial Mathematics, 5th edition, Addison Wesley, Boston, 2004.
  ISBN-10: 0201726343, ISBN-13: 978-0201726343.
• A. Cupillari, The Nuts and Bolts of Proofs, 3rd edition, Academic Press, Boston, 2005.
  ISBN-10: 0120885093, ISBN-13: 978-0072880083.
• A. V. Aho, J. E. Hopcroft, and J. E. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, 1974.
  ISBN-10: 0201000296, ISBN-13: 978-0201000290.
• K. H. Rosen, Discrete Mathematics and Its Applications, 6th edition, McGraw Hill, Boston, 2007.
  ISBN-10: 0072880082, ISBN-13: 978-0072880083. This is the third version of the 6th edition.

You will need a copy of Rosen's 5th edition book at all of the exams. If you do not have it, you will fail the exams. If you find the cost of the book too high (I did not choose the textbook), please take another course instead.

Lecture Notes

The class lecture notes are always online. There is a hyperlink in all of the web page headers to the notes. In addition, there are some extra notes.

• Recurrence relations (Jay Hatcher)
• Graphs (Divya Bansal)

Office Hours and Contacting Me

My office hours will be on Tuesdays 11:00-12:00 and Wednesdays 10:00-11:00 (and subject to cancellation occasionally) and posted here after the first class lecture.

My office is 514H RMB (the building formerly known as the Robotics building). My office telephone number is 257-2438 and my eFAX is +1-203-547-6273. I am virtually never at my UK office on Mondays or Fridays. Do not call me at home (or show up there). Do not show up at my office unannounced outside of my office hours. If you are skipping lots of classes, do not show up at my office with a bunch of questions that you would know the answers to if you had bothered to actually show up for class. Do not bother any member of my research group who might be in or near my office.

Send me email with CS275 in the subject line. I have a filter in my mailer to catch messages with that in the Subject line. Otherwise you will be competing with the 500-600 pieces of spam I get a day. If I do not know your name or decide that the subject is blank or irrelevant, I will just delete your message if it lands in my Inbox. C'est la vie. In your email, include a phone number so I can call you in case I need to. I usually respond to email fairly quickly unless I am on an airplane or train.

Course Evaluation Questions Specific to this Class

The course has taught me:

37. how to construct proofs by mathematical induction
38. how to apply laws of set algebra
39. how to apply elementary logic
40. how to enumerate combinatorial objects
41. how to solve recurrence relations
42. to understand the relevance of discrete mathematics to CS curriculum

Cheers,
Craig C. Douglas

Last modified: