CS330 – Discrete Structures Last Updated - 02/19/02Course Manager - Dr. Sanjiv Kapoor, Professor3 credit hours; required for CS & CPE (or MATH230); 150 min. lecture each weekCurrent Catalog Description - Introduction to the use of formal mathematical structures to represent problemsand computational processes. Topics covered include Boolean algebra, first-order logic, recursive structures,graphs, and abstract language models. Prerequisite: CS 106 or CS 200. (3-0-3)Textbook• Kenneth H. Rosen, Discrete Mathematics and Its Applications, McGraw-Hill, 4th Edition, ©1999,ISBN-0072899050References - other textbooks or materials• noneCourse Goals - Students should be able to:• Illustrate by examples the basic terminology of functions, relations, and sets and demonstrate knowledgeof their associated operations.• Demonstrate in practical applications the use of basic counting principles of permutations, combinations,inclusion/exclusion principle and the pigeonhole methodology.• Calculate probabilities of events and expectations of random variables for problems arising from gamesof chance.• Establish and solve recurrence relations that arise in counting problems including the problem ofdetermining the time complexity of recursively defined algorithms.• Model logic statements arising in algorithm correctness and real-life situations and manipulate themusing 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, mathematical induction.• Relate the ideas of mathematical induction to recursion and recursively defined structures.• Illustrate by example basic terminology of graph theory and model problems in computer science usinggraphs and trees.• Deduce properties that establish particular graphs as Trees, Planar, Eulerian, and Hamiltonion.• Illustrate the application of trees and graphs to data structures.• Explain the basic concepts modeling computation including formal machines, languages, finiteautomata, Turing machinesPrerequisites by Topic• Experience writing programs in any computer language.• Pre-calculusMajor Topics Covered in Course1. Sets, Functions and relations - sets, set operations, functions, summations, growth of functions,equivalence relations, countable and uncountable sets, examples of algorithm analysis4.5 hours2. Counting Methods – permutations, combinations, discrete probability, pigeonhole principle 6 hours3. Advanced counting – inclusion-exclusion, recurrence relations, methods of solving recurrences,examples from computer sciences6 hours4. Introductory Logic – propositional logic, predicate logic, proof methodologies, examples ofalgorithm correctness6 hours5. Partially Ordered sets - trees, boolean algebra, example of minimizing circuits 4.5 hours6. Introduction to Graphs - trees , connectivity, eulerian traversals, minimum spanning tree,planarity, Euler’s formula, matching7.5 hours7. Formal machines and languages-an introduction - automaton, grammars and turing machines 6 hours8. Introduction to Algebraic Topics (OPTIONAL) – rings, groups, semi-groups. 1.5 hoursExam #1, Exam #2 3 hoursFinal Exam -45 hoursLaboratory projects (specify number of weeks on each)• noneEstimate CSAB Category Content in Credit Hours CORE ADVANCED CORE ADVANCEDData Structures .5 Computer Organization and Architecture .5 Algorithms 2 Concepts of Programming Languages 0 Software Design 0 Oral and Written Communications - Every student is required to submit at least __0___ written reports (notincluding exams, tests, quizzes, or commented programs) of typically __0___ pages and to make __0___ oralpresentations of typically __0___ minutes duration. Include only material that is graded for grammar, spelling,style, and so forth, as well as for technical content, completeness, and accuracy.Social and Ethical Issues - Please list the topics that address the social and ethical implications of computingcovered in all course sections. Estimate the class time spent on each topic. In what ways are the students in thiscourse graded on their understanding of these topics (e.g., test questions, essays, oral presentations, and soforth)?• noneTheoretical Foundations - Please list the types of theoretical material covered, and estimate the time devotedto such coverage in contact (lecture and lab) hours.• The entire course is basically theoretical material, please see “Major Topics Covered in Course” aboveProblem Analysis - Please describe the problem analysis experiences common to all course sections.• Deriving recurrence relations from recursive algorithms• Modeling logic statementsSolution Design - Please describe the design experiences common to all course sections.• noneOther Course Information• Additional Suggested Course Assignmentso 4-6 homework assignmentso 2 exams (75 minutes each)o 1 final exam (120 minutes)• Planned Course Enhancementso New course description - Introduction to the use of formal mathematical structures to representproblems and computational processes. Topics covered include sets, functions and relations,counting methods, recursive structures, logic, partially ordered sets, graphs, formal machines andlanguages. Prerequisite: CS 106 or CS 200. (3-0-3) (Fall 2002)o Replacement of programming assignments with additional quizzes or homework assignments(Fall