CSE/Math 261  Discrete Structures Total Credits  (3)

Instructors:  Donald Hillman and Henry Baird

Current Catalog Description
Topics in discrete structures chosen for their applicability to computer science and engineering. Sets, propositions, induction, recursion; combinatorics; binary relations and functions; ordering, lattices and Boolean algebra; graphs and trees. Various applications.

Textbook
Kenneth H. Rosen , Discrete Mathematics and its Applications, 5th Ed.,  2003, ISBN 0-07-242434-6, McGraw-Hill.

References
None

Course Goals
Teach the fundamental concepts and methods common to mathematics and computer science & engineering; provide extensive practice in rigorous proof, in the context of propositional logic, set theory, number theory, and algorithm design and analysis.

Prerequisites by Topic
Calculus (Math 21): Functions and graphs; limits and continuity; derivative, differential, and applications; indefinite and definite integrals; trigonometric, logarithmic, exponential, and hyperbolic functions.

Major Topics Covered in the Course
Logic & Proof: Logic, Propositional Equivalences, Predicates and Quantifiers, Nested Quantifiers, Methods of Proof.
Sets, Functions, & Algorithms: Set Operations and Functions; Functions; Algorithms; The Growth of Functions; Complexity of Algorithms.
Number Theory:  The Integers, Division, and Algorithms; Applications of Number Theory; Matrices.
Mathematical Reasoning, Induction, and Recursion:  Proof Strategy, Sequences and Summations, Mathematical Induction, Recursive Definitions, Recursive Algorithms, Program Correctness.
Counting: Counting, Permutations, Combinations; Recurrence Relations; Divide and Conquer Algorithms.
Relations: Relations, Properties, Representations; Closures, Equivalence, Partial Orderings.
Graphs: Graphs, Terminology; Isomorphism, Connectivity; Hamiltonian Paths;  Shortest-Path Problems.

Laboratory projects (specify number of weeks on each)
None.
 
Estimate CSAB Category Content
                                                                     CORE      ADVANCED
Data Structures                                                 0.5    
Computer Organization and Architecture
Algorithms Software Design                              0.5    
Concepts of Programming Languages 

Oral and Written Communications
None.

Social and Ethical Issues
One hour of discussion of the implications of writing incorrect and insecure software,

Theoretical Content
80% of the topics (see above) are devoted to fundamental concepts and methods that form the basis of mathematics and computer science.

Problem Analysis
20% of the course presents concrete problems for analysis, with special emphasis on    general strategies for solving problems.

Solution Design
About 20% of homework problems require the design of algorithms and programs.