[ CS 275 Homepage ]

CS 275 - Discrete Mathematics : Syllabus

Time and Place

Classes : 12:30pm -- 1:45pm, Tuesday and Thursday CB 102.
Recitations : Section 1 : 10am -- 10:50am, Monday, CB 243.
Recitations : Section 2 : 11am -- 11:50am, Monday, RMB 323.
Recitations : Section 3 : 12pm -- 12:50pm, Monday, RMB 323.

Professor & Teaching Assistants

Professor: Dr. Etienne Grossmann.
Email: etienne@cs.uky.edu
Tel: 859 257 1257 Extension 81280.
Office: 514 C Robotics building.
Office Hours: Tuesday and Thursday, 2pm - 3:15pm.

Teaching Assistant: Saikat Chakrabarti.
Email: schak2@cs.uky.edu
Office: Multilab, in the EE Annex Building.
Office Hours: Tuesday and Thursday, 10:30am - 12pm.

Teaching Assistant: Albert Kalim.
Email: akali2@uky.edu
Office: Multilab, in the EE Annex Building.
Office Hours: Thursday, 9am - 10:30am.

Course 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.

Learning Outcomes, as specified here:

Students will develop a 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

Measures: These five specific outcomes will be evaluated on the basis of student work (homeworks and exams) that will contain problems specifically addressing these outcomes. They will also be evaluated on the basis of student self-assessment of their mastery of the five outcomes performed at the end of the semester.

Prerequisites

MA-113 and CS-115

Textbook

Kenneth H. Rosen, Discrete Mathematics and its Applications, Fifth Edition, McGraw Hill, 2003.

Grading

There will be 8-10 homeworks due Tuesdays at the beginning of class; assignments will be posted the previous Tuesday on the web. Illegible work will not be graded. There will be two midterm and one final exam. Each student is allowed to bring a single letter-sized "helper" sheet of paper to the exams. All grades will range between 0 and 20.

The average of the six best homeworks will represent 50% of your grade; the midterms will be 15% and the final 20%.

Read this

Attendance in class and section is very strongly encouraged.

Copying of homework from other students or from other sources is strictly prohibited. Obtaining a solution from another source without citing the source is plagiarism. You are encouraged to visit Dr. Grossmann or your T.A. in their office hours or to send them email if you are stuck on homework problems. You do not need an appointment for regularly scheduled hours.

Week-by-week course outline

Date	Topic	Chapter
W1: Aug. 26	Set theory	1.6
W2: Aug. 31, Sept. 2	Mathematical proofs	1.1-1.5
Sept. 6	Labor day: no recitation.
W3: Sept. 7, 9	Mathematical induction and recursive definitions; Counting.	3.3, 4.1
W4: Sept. 14, 16	Counting: unions and products, permutations, combinations, enumeration algorithms.	4.3, 4.6
W5: Sept. 21, 23	Binomial theorem; the inclusion/exclusion principle.	4.4-4.6
W6: Sept. 28, 30	Functions; inclusion/exclusion continued; review.	1.8, 1.7, 6.5, ...
Oct. 5	MIDTERM
W7: Oct. 7	The notion of a relation. Partial orders and equivalence relations.	7.1,7.5-6 (+bits of 7.2, 7.4)
W8: Oct. 12, 14	More on relations, closures, composition, inverses and functions.	1.8, 7.1, 7.4-6.
W9: Oct. 19, 21	The Pigeonhole principle; Boolean algebra: definitions and Boolean functions.	4.2, 10.1, 10.2
W10: Oct. 26, 28	Boolean algebra: logic gates and set theory. Recurrences: first-order linear; second-order	10.1-10.3, 6.1, 6.2
Nov. 2	Elections : no class.
W11: Nov. 4	Recurrences: divide-and-conquer; relation to analysis of algorithms.	2.2, 6.1-6.3
W12: Nov. 9, 11	Graphs: definitions	8.1-8.4
Nov. 16	MIDTERM
W13: Nov. 18	Graphs: planarity; cycles, colorings, matchings.	8.7, 8.8, 8.5
W14: Nov. 23	Trees: definitions, counting, spanning trees.	9.1, 9.4, 9.5
Nov 25	Thanksgiving : no class.
W15: Nov. 30, Dec. 2	Review.
Dec. 7, 9	"Dead week": no class.
Dec. 14	FINAL: 1pm - 3pm Tuesday, Dec. 14th

Acknowledgments

This page is largely inspired from the CS 275 pages of Drs. Goldsmith, Calvert and Truszczynski.