Vietnam National University, Hanoi College of Technology CS281 - Discrete Structures Spring, 2008 Student Manual

Letter to Student To the Student: This course and this Student Manual reflect a collective effort led by your instructor. This course is an important component of our academic program. Although it has been offered for many years, this latest version represents an attempt to expand the range of sources of information and instruction, so that the course continues to be up-to-date and the methods well suited to what is to be learned. You will be asked from time to time to offer feedback on how the Student Manual is working and how the course is progressing. Your comments will inform the development team about what is working, and what requires attention. Our goal is to help you learn what is important about this particular field, and to eventually succeed as a professional applying what you learn in this course. This Student Manual is designed to assist you through the course by providing specific information about student responsibilities including requirements, timelines and evaluations. I hope you enjoy the course.

Faculty Information Name: Bui The Duy Office Location: 306, E3 Building Email: duybt@vnu.edu.vn Office Hours: 8am-5pm, weekdays Before or after class: 10am-11am, Tuesday Support personnel: • Le Thi Hoi – Assistant, 306, E3 Building • Ngo Thi Duyen – Assistant, 306, E3 Building • Ma Thi Chau – Assistant, 306, E3 Building

Resources Course Reading material MIT’s OpenCourseWare Connexions On-line Discrete Math tutorials

Purpose of the Course The main goal of this course is to provide students with an opportunity to gain an understanding of the theoretical foundations of Computer Science. The main areas of the course are Mathematical Logic, Set Theory, and Relations. Topics include proof methods with emphasis on mathematical induction, solving recurrence relations, propositional logic, first order logic, proof techniques, mathematical induction, sets, operations on sets, relations, operations on relations, and functions. The emphasis is on the applications of discrete structures in computer science rather than the mathematical theory itself.

Course Description Discrete structures is foundational material for computer science. By foundational we mean that relatively few computer scientists will be working primarily on discrete structures, but that many other areas of computer science require the ability to work with concepts from discrete structures. Discrete structures includes important material from such areas as set theory, logic, graph theory, and combinatorics. This course covers the mathematics that underlies most of computer science, which are the fundamental mathematical concepts and reasoning along with problem solving techniques. Topics covered include propositional logic, predicate logic, inferencing, proof methods including induction, set operations, binary relations including order relations, and equivalence relations, graphs, and functions.

Course Requirements CS101 - Introduction to Programming course MATH102 - Pre-Calculus II, or equivalents. Calculus is preferred, but not required. Students are presumed to be familiar with basic programming techniques, including the use of functions and procedures, loops and recursion. Also assumed is facility with basic algebra. Students are also expected to be familiar with the use of standard Internet-based tools including e-mail.

Course Objectives Cultivate clear thinking and creative problem solving. Thoroughly train in the construction and understanding of mathematical proofs. Exercise common mathematical arguments and proof strategies. Cultivate a sense of familiarity and ease in working with mathematical notation and common concepts in discrete mathematics. Teach the basic results in Mathematical Logic, Set Theory, and Relations.

Student Objectives At the end of the course, students should: Understand fundamental mathematical concepts as they apply to computer science by seeing how mathematics supports CS, and how CS concepts can be formalized in mathematics Illustrate by examples the basic terminology of functions, relations, and sets and demonstrate knowledge of their associated operations. Establish and solve recurrence relations that arise in counting problems including the problem of determining the time complexity of recursively defined algorithms. Model logic statements arising in algorithm correctness and real-life situations and manipulate them using the formal methods of propositional and predicate logic. Outline basic proofs for theorems using the techniques of: direct proofs, proof by counterexample, proof by contraposition, proof by contradiction, and mathematical induction. Relate the ideas of mathematical induction to recursion and recursively defined structures. Enhance one’s ability to program by seeing how mathematical concepts form the basis for many common programming problems (e.g. grammars for parsing, predicate calculus for logic programming, sets and algebras for relational databases, graphs and topological sorting for automating optimization). Further their ability to write large programs by integrating code from a diverse spectrum of program components.

Grading Procedures The overall grade for this course is based on your performance in (i) exercises, (ii) assignments, (iii) mid-term exam and (iv) final exam, with weights as given below. Exams consist of a midterm and a final exam. Course component grading weight (it can be changed): Midterm: 20% Weekly homework: 40% Final: 40%

Content Information First we learn a general methodology for solving problems. This methodology is going to be followed in solving problems, and in proving theorems throughout this course. The next subject is logic. Logic subject matter is covered in Chapter 1 of the textbook. “Logic” is a language that captures the essence of our reasoning, and correct reasoning must follow the rules of this language. We start with logic of sentences called propositional logic, and study elements of logic, (logical) relationships between propositions, and reasoning. Then we learn a little more powerful logic called predicate logic. Predicate logic allows us to reason with statements involving variables among other statements. In Chapter 1, we also study sets, relations between sets, and operations on sets. Sets are the basis of every theory in computer science and mathematics. In Chapter 3, we learn recursive definitions and mathematical reasoning, in particular induction. There are sets, operations and functions that can be defined precisely by recursive definitions. Properties of those recursively defined objects can be established rigorously using proof by induction. Then in Chapters 6 we study relations. Relations are one of the key concepts in the discussion of many subjects on computer and computation. For example, a database is viewed as a set of relations and database query languages are constructed based on operations on relations and sets. Graphs are also covered briefly here. Graphs are an example of discrete structures and they are one of the most useful models for computer scientists and engineers in solving problems. More in-depth coverage of graphs can be found in Chapter 7. Finally, back in Chapter 1 again, we briefly study functions. Functions are a special type of relation and basically the same kind of concept as the ones we see in calculus. However, functions are one of the most important concepts in the discussion of many subjects on computer and computation, such as data structures, database, formal languages and automata, and analysis of algorithms, which is briefly covered in Chapter 2.

Instructional Sequence Unit 1 Task 1: Read the following: Introduction to Discrete Structures Problem Solving Framework Problem Solving Example 1 Unit 2 Task 1: Read the following: Problem Solving Examples Unit 3 Task 1: Read the following: Introduction to Logic What is Proposition Elements of Propositional Logic Truth Table Connectives Construction of Proposition Converse and Contrapositive These materials can also be found in Textbook 1.1 - 1.2. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 11 : 1 all Textbook p. 11 : 3 all Textbook p. 11 : 7 a c e g Textbook p. 12 : 9 b d f h Textbook p. 13 : 19 all Textbook p. 13 : 21 a c e Textbook p. 13 : 23 d f Reading Material: Chapter Logic - Exercise 16-21 Unit 4 Task 1: Read the following: Variations of if_then From English to Proposition These materials can also be found in Textbook 1.1 - 1.2. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 12 : 15 all Textbook p. 12 : 17 all Reading Material: Chapter Logic - Exercise 22-23 Unit 5 Task 1: Read the following: Introduction to Reasoning Identities of Propositions and Dual Example of Use of Identities These materials can also be found in Textbook 1.1 - 1.2. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 19 : 1 a d f Textbook p. 19 : 5 Textbook p. 20: 9 b d f Textbook p. 20: 11 a Textbook p. 20: 20 all Textbook p. 20: 25 Reading Material: Chapter Logic - Exercise 24-29 Unit 6 Task 1: Read the following: Implications Reasoning with Propositions Proof of Identities Proof of Implications These materials can also be found in Textbook 1.1 - 1.2 and pp. 167 - 173. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Converting Inferencing to Logic Check the Correctness of Reasoning of 1. above using Inference Check Textbook p. 183: 1 all Textbook p. 183: 3 Textbook p. 20 : 9 c d e Textbook p. 20 : 19 Reading Material: Chapter Logic - Exercise 30-31 Unit 7 Task 1: Read the following: Why Predicate Logic ? Predicate Quantification Constructing Formulas (Wffs) These materials can also be found in Textbook 1.3. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 33 : 3 all Textbook p. 33 : 5 all Textbook p. 35 : 19 all Textbook p. 36 : 23 a c e Reading Material: Chapter Logic - Exercise 32-35 Unit 8 Task 1: Read the following: From Wff to Proposition English to Logic Translation These materials can also be found in Textbook 1.3. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 34 : 13 b d f h Textbook p. 35 : 17 a c e g Textbook p. 36 : 31 all Textbook p. 36 : 33 all Converting English to Logic Reading Material: Chapter Logic - Exercise 36-39 Unit 9 Task 1: Read the following: Reasoning with Predicate Logic These materials can also be found in Textbook 1.3 and 3.1 . Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 37 : 35 Textbook p. 183: 9 all Textbook p. 183: 11 b d Reading Material: Chapter Logic - Exercise 40-42 Unit 10 Task 1: Read the following: Quantifiers and Connectives These materials can also be found in Textbook 1.3. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 37 : 41 Textbook p. 37 : 43 a Reading Material: Chapter Logic - Exercise 43-44 Unit 11 Task 1: Read the following: Introduction to Sets Representation of Set Equality, Subset, etc. These materials can also be found in Textbook 1.4. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 45 : 1 a d Textbook p. 45 : 3 all Textbook p. 45 : 5 all Textbook p. 45 : 9 Textbook p. 45 : 13 all Reading Material: Chapter Set Theory - Exercise 4-8 Unit 12 Task 1: Read the following: Mathematical Reasoning Set Operations These materials can also be found in Textbook 1.3 and 1.5. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 45 : 21 Textbook p. 45 : 23 Textbook p. 54 : 3 all Textbook p. 54 : 19 a c Textbook p. 54 : 21 Reading Material: Chapter Set Theory - Exercise 9-13 Unit 13 Task 1: Read the following: Properties of Set Operation These materials can also be found in Textbook 1.5. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 54 : 7 all Textbook p. 54 : 9 a Textbook p. 54 : 15 a Reading Material: Chapter Set Theory - Exercise 14-16 TEST: Covers Unit 3 - Unit 12 inclusive. Unit 14 Task 1: Read the following: Recursive Definition Generalized Set Operations These materials can also be found in Textbook 1.5 and 3.3. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 55 : 35 a Textbook p. 55 : 36 b Textbook p. 210: 21 Textbook p. 210: 23 all Textbook p. 210: 31 (An empty string is a string with no symbols in it.) Reading Material: Chapter Recursion - Exercise 5-9 Unit 15 Task 1: Read the following: Recursive Definition of Function Recursive Algorithm These materials can also be found in Textbook 3.3 and 3.4. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 209: 1 a b c Textbook p. 209: 3 a b Textbook p. 209: 7 Textbook p. 218: 1 Textbook p. 218: 3 Reading Material: Chapter Recursion - Exercise 10-14 Unit 16 Task 1: Read the following: First Principle of Mathematical Induction These materials can also be found in Textbook 3.2. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 199: 3 Textbook p. 200: 9 Textbook p. 200: 13 Textbook p. 200: 19 Textbook p. 200: 21 Textbook p. 201: 43 Reading Material: Chapter Recursion - Exercise 15-20 Unit 17 Task 1: Read the following: Example of Use of Induction Second Principle of Mathematical Induction Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 199: 5 Textbook p. 202: 59Reading Material: Chapter Recursion - Exercise 21-22 These materials can also be found in Textbook 3.2. Unit 18 Task 1: Read the following: Introduction to Relation Binary Relation Definition of Relation (general relation) Equality of Relations Recursive Definition of Relation These materials can also be found in Textbook 6.1 and 6.2. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 382: 1 all Textbook p. 382: 2 a Textbook p. 389: 3 Recursively define the relation {< a, b > | a = 2b }. List unary relation on { 1, 2, 3 }. Prove that there are 2n2 binary relations on a set of cardinality n. Reading Material: Chapter Relation - Exercise 10-13 Unit 19 Task 1: Read the following: Digraph Digraph Representation of Binary Relation Properties of Binary Relation These materials can also be found in Textbook 6.3, 7.1 and 7.2. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 382: 3 b d f Textbook p. 382: 5 a c g e Textbook p. 383: 19 a b Textbook p. 396: 12 Textbook p. 396: 13 Textbook p. 396: 15 Reading Material: Chapter Relation - Exercise 14-17 Unit 20 Task 1: Read the following: Operations on Binary Relations Closures of Binary Relation These materials can also be found in Textbook 6.1 and 6.4. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 383: 19 a b Textbook p. 383: 21 Textbook p. 383: 35 Textbook p. 406: 1 Textbook p. 406: 3 Textbook p. 406: 11 for 5 Textbook p. 407: 22 Reading Material: Chapter Relation - Exercise 18-22 Unit 21 Task 1: Read the following: Equivalence Relation Order Relation (Partial, Total, and Quasi Orders) These materials can also be found in Textbook 6.5 and 6.6. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 413: 1 a c e Textbook p. 413: 5 a b Textbook p. 413: 9 Textbook p. 413: 11 Textbook p. 414: 23 Textbook p. 414: 25 Textbook p. 414: 31 a b Reading Material: Chapter Relation - Exercise 23-28 Unit 22 Task 1: Read the following: Order Relation (Minimal Element and the rest) These materials can also be found in Textbook 6.6. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 428: 1 Textbook p. 428: 3 Textbook p. 428: 5 Textbook p. 428: 15 a d Textbook p. 428: 17 Textbook p. 429: 27 Reading Material: Chapter Relation - Exercise 29-31 Unit 23 Task 1: Read the following: Definitions on Function Growth of Functions These materials can also be found in Textbook 1.6 and 1.8. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 67: 1 Textbook p. 67: 5 a c Textbook p. 67: 10 a b c Textbook p. 67: 11 a b c Textbook p. 67: 15 a b Textbook p. 68: 17 a c Textbook p. 68: 49 Textbook p. 90: 1 Textbook p. 90: 3 Reading Material: Chapter Function - Exercise 3-9 Unit 24 Task 1: Read the following: Growth of Functions (Calculation of Big-Oh Relation) These materials can also be found in Textbook 1.8. Task 2: Do the following exercises: These exercises are NOT homework questions. They are for helping you understand the materials of this unit. Textbook p. 90: 5 Textbook p. 90: 11 Textbook p. 90: 13 Textbook p. 90: 15 Textbook p. 91: 19 a b Textbook p. 91: 31 Reading Material: Chapter Function - Exercise 10-14

Calendar – Timetable Week Units to Study 1 Unit 1, Unit 2 2 Unit 3, Unit 4 Submit Homeworks 1, 2 3 Unit 5, Unit 6 4 Unit 7, Unit 8 Submit Homeworks 3, 4 5 Unit 9, Unit 10 6 Unit 11, Unit 12 Submit Homeworks 5, 6 7 Unit 13, Unit 14 TEST : Unit 3 - Unit 12 inclusive 8 Unit 15, Unit 16 Submit Homeworks 7, 8 9 Unit 17, Unit 18 10 Unit 19, Unit 20 Submit Homeworks 9, 10 11 Unit 21, Unit 22 12 Unit 23, Unit 24 Submit Homeworks 11, 12 EXAM : Unit 3 - Unit 24 inclusive

Readings Course Reading Material Textbook: Kenneth H. Rosen, Discrete Mathematics and Its Applications, 6th edition, McGraw-Hill Science/Engineering/Math, 2006, ISBN 978-0073312712.

Reference Task Force on Computing Curricula. Computing Curricula 2001: Computer Science, Final Report, December 2001. Available at http://www.sigcse.org/cc2001/ Discrete Mathematical Structures, 5th edition, by B. Kolman, R.C. Busby, and S.C. Ross, published by Prentice Hall, 2004. Mathematical Structures for Computer Science, 5th edition, by J.L. Gersting, published by Freeman, 2003. Essential Discrete Mathematics for Computer Science, by T. Feil and J. Krone, published by Prentice Hall, 2003. Discrete Mathematics for Computing, by R. Haggerty, published by Addison Wesley, 2002. Discrete Structures, Logic, and Computability, 2nd edition, by J.L. Hein, published by Jones and Bartlett, 2002. Discrete Mathematics for Computer Scientists, by J. Truss, published by Addison Wesley, 1999. Discrete Mathematics with Applications, 3rd edition, by S. Epp, published by Brooks/Cole, 2004. Discrete Mathematics with Proof, by E. Gossett, published by Prentice Hall, 2003. Discrete Mathematics, 5th edition, by K.A. Ross and C.R.B. Wright, published by Prentice Hall, 2003. Discrete Mathematics, 4th edition, by J.A. Dossey, A.D. Otto, L.E. Spence, and C.V. Eynden, published by Addison Wesley, 2002. Mathematics: A Discrete Introduction, by E.R. Scheinerman, published by Brooks/Cole, 2000. Discrete Mathematics, by S. Washburn, T. Marlowe, and C.T. Ryan, published by Addison Wesley, 1999. Discrete Mathematics with Graph Theory, 2nd edition, by E.G. Goodaire and M.M. Parmenter, published by Prentice Hall, 2002. Discrete and Combinatorial Mathematics, 5th edition, by R.P. Grimaldi, published by Addison Wesley, 2004. Discrete Mathematics with Combinatorics, 2nd edition, by J.A. Anderson, published by Prentice Hall, 2004. Discrete Mathematics: Numbers and Beyond, by S. Barnett, published by Addison Wesley, 1998.

Policy on cheating The instructor will put a great deal of effort into helping students to understand and to learn the material in the course. However, the instructor will not tolerate any form of cheating. The following behaviour will be regarded as cheating (together with other acts that would normally be regarded as cheating in the broad sense of the term): Copying assignments Allowing another student to copy an assignment from you and present it as their own work Copying from another student during a test or exam Referring to notes, textbooks, etc. during a test or exam Talking during a test or an exam Not sitting at the pre-assigned seat during a test or exam Communicating with another student in any way during a test or exam Having access to the exam/test paper prior to the exam/test Asking a teaching assistant for the answer to a question during an exam/test Presenting another’s work as your own Modifying answers after they have been marked Any other behaviour which attempts unfairly to give you an advantage over other students in the grade-assessment process Refusing to obey the instructions of the officer in charge of an examination.