|
Instructor:
Ion Mandoiu Office Hours: TTh 2-3pm, or by appt. Office: CCB 245 Phone: 894-9443 E-mail: mandoiu@cc.gatech.edu |
Teaching Assistant:
Donghua Xu Office Hours: MW 2:30-4pm Office: CCB 154 Phone: 894-2573 E-mail: xu@cc.gatech.edu |
Newsgroup: git.cc.class.1155
Web page:
http://www.cc.gatech.edu/classes/cs1155_99_summer/
Textbook: Kenneth H. Rosen. Discrete Mathematics and its Applications, Fourth Edition, McGraw-Hill, 1999.
Catalog Description: Introduction to the basic techniques of rigorous argumentation emphasizing the reading and writing of formal and informal proofs in discrete mathematics and computer science.
Class schedule:
| Date | Topics covered | Book sections |
| 06/22 | Propositional logic | 1.1, 1.2 |
| 06/24 | Predicate calculus, growth of functions | 1.3, 1.8 |
| 06/29 | Proofs by contradiction, divisibility, prime numbers, fundamental thm of arithmetic, gcd, lcm | 3.1, 2.3 |
| 07/01 | Gcd characterization (Ex.58, p.201), Euclid's algo, modular arithmetic, chinese rem. & Fermat's thms | 2.3, 2.4, 2.5 |
| 07/06 | Mathematical induction, summations, arithmetic and geometric progressions | 1.7, 3.2 |
| 07/08 | Second principle of mathematical induction, ranking tournament players | 3.2 |
| 07/13 | Sets and functions | 1.4, 1.5, 1.6 |
| 07/15 | Mid-term exam | --- |
| 07/20 | Composition of functions, inverse functions; cardinality of sets | 1.6, 17 |
| 07/22 | More on infinite sets; basic counting | 1.7, 4.1 |
| 07/27 | Pigeonhole principle; combinations and permutations; combinatorial proofs | 4.2, 4.3 |
| 07/29 | Discrete probability; probabilistic events and random variables | 4.4, 4.5 |
| 07/03 | Undirected graphs; free trees | 7.1, 7.2, 8.1 |
| 07/05 | Special types of trees; Lower bound for sorting | 8.1, 8.4 |
| Date | Topics covered | Book sections |
Review session: 3:00pm Monday, August 9, CCB 201
Final Exam: Tuesday, August 10, 11:30-2:20 CCB 201
Grading: 5 weekly homeworks 30%, mid-term exam 30%, comprehensive final 40%.
Late policy: The weekly assignments are due in class, one week after they are handed out (unless otherwise specified). Late assignments will be assesed a penalty of 20% of their grade if turned in whithin 48 hours; assignments that are more than 48 hours late will not be accepted.
Getting help: Don't hesitate to get help if you get stuck on a homework problem. The most obvious sources of help are your instructor, your TA, and the newsgroup for the class. You are also allowed to verbally collaborate on homework problems with other students, provided that you acknowledge the collaboration by writing the names of those with whom you discussed solutions. You are not allowed to share written answers with anyone else, and you may not look up the answer to a homework problem if it happens to be published either in print or on the internet.