1 SYLLABUS COT 3100-Applications of Discrete Structures Basic Information: Semester: Spring 2010 Classroom Location: CSE E119 Time: Monday, Wednesday and Friday 5th Period (11:45am – 12:35pm). Webpage: http://www.cise.ufl.edu/class/cot3100sp10/index.html Pre-requisites: MAC 2311, MAC 2233 or MAC 3472 Instructor: Prof. My T. Thai Email: mythai AT cise DOT ufl DOT edu Office: CSE E566. Office Hours: Tuesday 1-3pm or by appointment. Teaching Assistants: + Nam Nguyen (nanguyen AT cise DOT ufl DOT edu) + Thang Dinh (tdinh AT cise DOT ufl DOT edu) + Yuchen Xie (yxie AT cise DOT ufl DOT edu) BASIC COURSE DESCRIPTION The essential course theme is mathematics of discrete events or entities. The following is an overview of the course contents: (1) Elements of mathematical reasoning with a view to developing the ability to comprehend as well as write clear, correct proofs. Different proof techniques will be taught. (2) Discrete structures: These include entities such as sets, relations, graphs, and trees. These entities act as very fundamental representations useful in a broad spectrum of applications across the length and breadth of computer science. (3) Basic Combinatorial Analysis: This includes the basic concepts of permutations, combinations, counting, probability, and the pigeonhole principle. (4) Introduction to algorithms and time complexity. The contents of this course serve as a pillar for several applications in computer science, and provide highly useful background for subsequent courses on data structures and algorithms, theoretical computer science, as also other fields within computer science such as databases, networks, operating systems, programming languages, compilers, artificial intelligence, graphics, etc. It is important to note that this is by no means a programming course. Rather, it emphasizes mathematical reasoning. You will be expected to solve problems and write proofs just as in any typical mathematics class. GRADING The grading will be based on two midterms (each worth 20%) and one final exam (worth 30%), homework (worth 20%) and in-class quizzes (worth 10%). Homework2 There will be 11 homework assigned typically on Friday. Each HW is equally weighted and you can drop (one) your lowest score. The homework will be strictly due at the beginning of class on the due date. No late homework will be accepted and there are no electronic submissions. Also, the solutions will be posted immediately after the due time. All homework must be turned in on paper with the student’s name and section number written clearly on it. Quizzes There will be a quiz almost every week (or bi-weekly). Each quiz is equally weighted and you can drop (one) your lowest score. (This allows you to miss one quiz if you have other commitment) The dates will be determined later. Exams The two mid-terms will be in-class (closed books, closed notes, but you are allowed a two-sided A4 sized cheat-sheet on which you can write down your favourite formulae). Midterm exams are scheduled to be in class during normal class time. The final exam will be held during the official final exams week. For policies on make-up exams, please see the section on COURSE POLICIES. Grading Scale Letter Percent A 90-100 A- 87-89 B+ 84-86 B 80-83 B- 77-79 C+ 74-76 C 70-73 C- 67-69 D+ 64-66 D 60-63 D- 57-59 F <56 COURSE TEXTBOOK The official textbook for the course will be the SIXTH edition of “Discrete Mathematics and its Applications” by Kenneth Rosen, McGraw Hill 2006. A fifth edition of this book is also available; however the homework assignments will be based primarily on the sixth edition of the book. Hence, it is ENTIRELY your responsibility to locate the appropriate topics or exercises should you choose to use the fifth edition of the book. No excuse regarding any confusion on this matter will be entertained. Please note that STUDENTS’ SOLUTIONS to selected exercises are also available for this book. Feel free to use them, though it is obviously recommended that you attempt to solve all problems yourself first for your own practice instead of rushing to look at available solutions. Links to the book: http://www.amazon.com/Discrete-Mathematics-Applications-Kenneth-Rosen/dp/0073312711/ (Make sure you purchase the correct edition of the book, i.e. the SIXTH edition) http://highered.mcgraw-hill.com/sites/0072880082/information_center_view0/table_of_contents.html Published Errata: http://highered.mcgraw-hill.com/sites/dl/free/0072880082/299357/Rosen_errata.pdf3 Over and above this there exist several other books on discrete mathematics, such as “How to Solve It” by Polya. However the assigned textbook provides all required material in great depth and detail. TENTATIVE LIST OF TOPICS (1) Propositional and predicate calculus with proof techniques (1.1-1.7) (2) Set theory, Functions, and Sequences (2.1-2.4) (3) Algorithms and Integers (3.1-3.5) (4) Induction and Recursion (4.1-4.4) (5) Counting (5.1-5.3) (6) Graphs and graph algorithms (9.1-9.6) (7) Trees (if time permits, 10.1-10.4) COURSE POLICIES Re-grading: You are free to discuss any concerns regarding grading with me or the TAs but verbal discussion will not lead to any alteration in your grades. You need to submit a written request on a separate sheet of paper attached to your answer sheet clearly stating the reason for your request, either to me or to one of the TAs. This is true for exams, quizzes and homework. On no account, should you write or make absolutely any changes whatsoever on the answer sheets. All re-grade requests must be made WITHIN ONE WEEK from the time the graded answer sheets are distributed to the class. Make-up Exams: There will be no make-up quizzes at all under any circumstances. Make-up midterms and final exams will be given only if you provide official documentation for a VALID EXCUSE which must be submitted to me PRIOR TO the exam. In the absence of such documentation, please do not ask for any make-up exams. Homework policy: No late homework will be accepted except in the case of medical problems that span the entire period starting from the day the homework was assigned till the day that it was due. Official documentation such as a doctor’s certificate is absolutely required in all such cases. Attendance: I will not be taking any attendance during class or any of the