UMUC-Europe Syllabus

CMIS 160 Discrete Mathematics for Computing (3) (Not open to students who have completed CMSC 150.) Recommended: MATH 107. An introduction to discrete mathematical techniques for solving problems in the field of computing. Basic principles from areas such as sets, relations and functions, logic, proof methods, and recursion are examined. Topics are selected on the basis of their applicability to typical problems in computer languages and systems, databases, networking, and software engineering.

Course Goals/Objectives:

This course is intended to: *Train students to think algorithmically and to develop analytical skills essential for computer and information science. *Introduce students to the mathematical foundations of computer science. *Prepare students for further studies in programming, databases, system hardware and software applications, and the analysis of networks and Internets. *Enable the students to: 1. Apply the basic properties and operations related to sets 2. Apply to sets the basic properties and operations related to functions and relations 3. Illustrate the basic definitions of graph theory and properties of graphs and trees with applications to data structures *Apply principles of partial order relations to solve a problem *Express statements with the precision of formal logic *Construct a digital logic circuit, a logical statement, or an input/output table when given any one of the three representation: prove a formula using mathematical induction, construct a finite-state automaton that accepts a specified language, determine the language accepted by a given finite-state automation *Develop a conceptual understanding of number theory, digital representation of numeric data, and applications to algorithms *Use recursion to define a set of strings with a specified characteristic *To determine the computational complexity and the efficiency of algorithms *Relate each major topic in discrete mathematics to an application area in computing *Understand how Math has evolved from ancient Greek philosophy to its use in modern day computers

Course Introduction:

Discrete Mathematics for Computing is a collection of topics, primarily mathematical in nature, that underlie a variety of concepts and techniques in computing. Topics include the analysis and application of sets, relations, and functions; propositional and predicate logic (essential for understanding relational database operations and SQL), number systems and Boolean algebra (fundamental to the design of computer logic circuits and for understanding data representation in programming languages), analysis of algorithms, and recursion - key topics in computer programming. In this course, you study and practice formalisms, logical processes, notations, concepts, and techniques that will help deepen your understanding of a variety of computer areas. Course topics include: 1. Sets, Functions, and Relations 2. Graphs and Trees 3. Partial Ordering, Paths, and Circuits 4. Logic and Methods of Proof 5. Finite-State Machines Each of these topics relates to one or more applications in areas of computing. Note that students should have a solid understanding of college-level algebra. If you have not taken this kind of a course recently, you should acquire and review a college algebra text and ensure that you understand the concepts. There are also some informal prerequisites, or human qualities, that facilitate learning discrete mathematics. A short list of these qualities includes confidence, imagination, willingness to experiment, perseverance, common sense, decision-making skills, handling detours and roadblocks, self-discipline, and courage to go from the known to the unknown. Each of you has all of these qualities, at least to some degree. Just as healthy bodies result from proper physical exercise, knowledge of discrete mathematics comes from a willingness to exercise your mental capabilities. This course is required for all students majoring in Computer and Information Science (CMIS); it is strongly recommended for students majoring in IFSM or CMST, and would be valuable for anyone interested in the mathematical foundations of computer science. Students who complete CMIS 160 will be well prepared for advanced courses in programming, databases, computer hardware and software, and network and Internet routing.

Grading Information and Criteria:

There will be three 75-minute exams each worth 15% of the final grade, and a comprehensive final exam that is worth 30% of the final grade. The remaining 25% of the final grade will be comprised of the homework assignments and projects. Projects are due the class meeting prior to the final exam. Late projects will not be accepted. Homework problems from the sections covered on each of the three exams is due the day that exam is administered. If the homework problems are submitted late, they will only be worth half credit. The homework for the sections covered after Exam III is due the day of the final exam. Any homework submitted after the final exam is taken is worth zero points. ***MAKE-UP EXAMS WILL ONLY BE GIVEN FOR DIRE CIRCUMSTANCES*** Grading Scale: A = 90% - 100% B = 80% - 89% C = 70% - 79% D = 60% - 69% F = 0% - 59%

Other Information:

Attendance: The student is responsible for attending all classes and any related activities regularly and punctually. Absences from class do not excuse a student from missed coursework. Much of the benefits of this course is derived from practice with other during class sessions. It is expected, therefore, that the assigned chapters be read before each class meeting so students may participate during class time to the fullest. Class Discussions: Students are encouraged (indeed, expected) to participate. Ask questions. Homework assignments will be given for each class session. You are responsible for solving all problems assigned. Homework will be collected as described in the grading information and criteria section above. Completing all the homework problems should help you prepare for the exams. If there are any problems that you found difficult or were unable to solve, be prepared to ask questions concerning those problems. Mastery of math depends on practice, practice, practice! Withdrawal: In the event you must withdraw from this course, follow the formal procedure found in the UMUC undergraduate catalog. Your request to withdraw, resulting in a grade of "W", must be submitted to the appropriate parties at least two weeks before the last scheduled class session. Failure to adhere to the appropriate process will result in a Grade of "F". Academic Integrity: Students of University College are expected to conduct themselves in a manner that will contribute to the maintenance of academic integrity. All students are responsible for adhering to the University's policies regarding integrity and dishonesty stated in the college catalog. All incidents of inappropriate academic integrity will be turned over to the Administration for investigation and will result in all students involved receiving a 0 or "F" on the assignment or exam.

Project Descriptions:

Each of the five projects listed here must be submitted by the class meeting prior to the final exam. Late projects will not be accepted. All work should be shown for each project and you should use proper English and complete sentences with your written responses. 1. problem 44 on page 74. 2. problem 23 on page 243. 3. problem 30 on page 369. 4. problem 45 on page 453. 5. Read section 9.3 and then write an algorithm for insertion sort, which is described on pages 500-502.

Academic Policies:

Cases of plagiarism are handled consistent with current UMUC guidelines. See the UMUC policies at the following URL: http://www.umuc.edu/policy/

Course Schedule:

Tentative Schedule; may be modified as required by instructor. All readings and assignments from Epp, Discrete Mathematics with Applications. All reading assignments should be completed before class meetings. Meeting 1. Logical Form and Logical Equivalence; Conditional statements Read sections 1.1 and 1.2 Problems as assigned from 1.1 and 1.2 Meeting 2. Valid and Invalid Arguments; Digital Logic Circuits Read sections 1.3 and 1.4 Problems as assigned from 1.3 and 1.4 Meeting 3. Number Systems and Circuits for Addition Read section 1.5 Problems as assigned from 1.5 Meeting 4. Predicates and Quantified Statements Read sections 2.1 and 2.2 Problems as assigned from 2.1 and 2.2 Meeting 5. Exam I (75 minutes) Homework assigned during class meetings 1 - 4 due Direct Proof and Counterexample Read section 3.1 Meeting 6. Sequences, Mathematical Induction Read sections 4.1 and 4.2 Problems as assigned from 4.1 and 4.2 Meeting 7. Correctness of Algorithms, Basic Definitions of Set Theory Read sections 4.5 and 5.1 Problems as assigned from 4.5 and 5.1 Meeting 8. Properties of Sets, the Empty Set, Partitions, Power Sets, Boolean Algebras Read sections 5.2 and 5.3 Problems as assigned from 5.2 and 5.3 Meeting 9. Exam II (75 minutes) Homework assigned during class meetings 5 - 8 due Counting and Probability; Possibility Trees and the Multiplication Rule Read sections 6.1 and 6.2 Problems as assigned from 6.1 and 6.2 Meeting 10. Functions Defined on General Sets, Finite-State Automata Read sections 7.1 and 7.2 Problems as assigned from 7.1 and 7.2 Meeting 11. Recursively Defined Sequences, Solving Recurrence Relations by iteration Read sections 8.1 and 8.2 Problems as assigned from 8.1 and 8.2 Meeting 12. Real-Valued Functions of a Real Variable and their Graphs; O-notation Read sections 9.1 and 9.2 Problems as assigned from 9.1 and 9.2 Meeting 13. Exam III (75 minutes) Homework assigned during class meetings 9 - 12 are due Efficiency of Algorithms; Relations on Sets Read section 9.3 Problems as assigned from 9.3 Meeting 14. Exponential and Logarithmic Functions; Efficiency of Search and Sort Algorithms Read sections 9.4 and 9.5 Problems as assigned from 9.4 and 9.5 Meeting 15. Graphs, Path and Circuits, Trees and Spanning Trees Read sections 11.1, 11.2, 11.5 and 11.6 Problems as assigned from 11.1, 11.2, 11.5, 11.6 Projects Due Meeting 16. Final Examination (150 minutes)