SYLLABUSCOT 3100: Applications of Discrete StructuresBasic Information:Semester: Spring 2009.Instructor: Jeffrey HoInstructor Contact Information:Email: jho AT cise DOT ufl DOT edu Phone: 352-392-TBDOffice Number: CSE E360.Classroom Location: CSE E121 Class Timings: Monday, Wednesday and Friday 5th Period (11:45am – 12:35pm).Instructor Office Hours: Monday and Wednesday (1:00 pm to 2:00 pm), or by appointment .Teaching Assistants:Bo Li (boli AT cise DOT ufl DOT edu)Muhammad Rushdi (mrushdi AT cise DOT ufl DOT edu)Young Yeo (yiyeo AT cise DOT ufl DOT edu)Webpage: http://www.cise.ufl.edu/class/cot3100sp09/Pre-requisites: MAC 2311, MAC 2233 or MAC 3472BASIC 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 andalgorithms, theoretical computer science, as also other fields within computer sciencesuch as databases, networks, operating systems, programming languages, compilers,artificial intelligence, graphics, etc. It is important to note that this is by no means aprogramming course. Rather, it emphasizes mathematical reasoning. You will beexpected 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 (worth35%), homeworks (worth 20%) and in-class quizzes (worth 10%). (Note that the totalhere is 105%).Homeworks:There will be weekly or bi-weekly homeworks assigned typically on Monday. Thehomework will be strictly due the very next Monday BEFORE or during the first 10minutes of class. No late homeworks will be accepted and there are no electronicsubmissions. Also, the solutions will be posted immediately after the due time. Allhomeworks must be turned in on paper with the student’s name and section numberwritten clearly on it. Depending on the exact number of homeworks, your lowest orlowest two scores will be dropped. All homeworks are weighted equally.Quizzes:There will be five in-class quizzes. The dates will be determined later.Exams:The two mid-terms will be in-class (closed books, closed notes, but you are allowed atwo-sided A4 sized cheat-sheet on which you can write down your favourite formulae).The mid-terms will be two hours long each. Midterm exams are scheduled to be inclass during normal class time. The final exam will be held during the official finalexams week. For policies on make-up exams, please see the section on COURSEPOLICIES. Grading Scale:The final grading scale will be an ‘A’ (90 and above), a ‘B+’ (85 and above, less than 90),a ‘B’ (80 and above, less than 85), a ‘C+’ (75 and above, less than 80), a ‘C’ (70 andabove, less than 75) and a ‘D’ (60 and above, but less than 70). COURSE TEXTBOOK:The official textbook for the course will be the SIXTH edition of “Discrete Mathematicsand its Applications” by Kenneth Rosen, McGraw Hill 2006. A fifth edition of this bookis also available; however the homework assignments will be based primarily on the sixthedition of the book. Hence, it is ENTIRELY your responsibility to locate the appropriatetopics or exercises should you choose to use the fifth edition of the book. No excuseregarding 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 firstfor 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.htmlPublished Errata:http://highered.mcgraw-hill.com/sites/dl/free/0072880082/299357/Rosen_errata.pdfOver 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 requiredmaterial in great depth and detail.TENTATIVE LIST OF TOPICS: (Exact section numbers from the book will be announced later)(1) Propositional and predicate calculus with proof techniques(2) Basic Set theory(3) Sequences(4) Functions(5) Basic Algorithms(6) Algorithms involving operations on integers (time permitting)(7) Mathematical Induction(8) Recursion and basic recurrences(9) Permutations and Combinations(10) Basic probability(11) Relations(12) Graphs and graph algorithms(13) Trees (time permitting)COURSE POLICIES:Regrading:You are free to discuss any concerns regarding grading with me or the TAs but verbaldiscussion will not lead to any alteration in your grades. You need to submit a writtenrequest on a separate sheet of paper attached to your answer sheet clearly stating thereason for your request, either to me or to one of the TAs. This is true for exams, quizzesand homeworks. On no account, should you write or make absolutely any changeswhatsoever on the answer sheets. All regrade requests must be made WITHIN ONEWEEK 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 andfinal exams will be given only if you provide official documentation for a VALIDEXCUSE which must be submitted to me PRIOR TO the exam. In the absence of suchdocumentation, please do not ask for any make-up exams.Homework policy:No late homeworks will be accepted except in the case of