COURSE:                 Math 310, Discrete Mathematics

CLASSROOM:        Bridges 264

INSTRUCTOR:       James Hatzenbuhler

DEPARTMENT:     Mathematics

OFFICE:                   MacLean 375Q

OFF. PHONE:         477-4012

E-MAIL:                hatzenbu@mnstate.edu

 

 

OFFICE HOURS:

 

            Monday:                     10:30 a.m. – 11:20 a.m., 2:30 p.m. – 3:30 p.m.

            Tuesday:                    10:30 a.m. – 12:00 noon, 2:30 p.m. – 3:30 p.m.

            Wednesday:                9:30 a.m. – 11:20 a.m., -2:30 p.m. – 3:30 p.m.

            Thursday:                  10:30 a.m. – 12:00 noon, 2:30 p.m. – 3:30 p.m.

            Friday:                        10:30 a.m. – 11:20 a.m.

Also by appointment.

 

Course Description:  Methods of proof, sets, logic, functions and relations, Boolean algebra, graph theory and number systems.  Students must either have taken, or be concurrently enrolled in Math 262, Calculus II.

 

Required Text:  DISCRETE MATHEMATICS AND ITS APPLICATIONS, 6th edition by Kenneth H. Rosen

 

 

COURSE OBJECTIVES / STUDENT LEARNING OUTCOME

 

Upon completion of the course, students will be able to do the following:

·         Solve real world problems using mathematics/logical systems.

·         Express mathematical/logical ideas clearly in writing.

·         Explain what constitutes a valid mathematical/logical argument (proof).

·         Be able to construct a valid proof.

·         Apply a variety of higher-order problem-solving and modeling strategies.

·         Exhibit mastery of computational skills and the ability to make reasonable estimates.

·         Understand and be able to apply the concepts of graph theory and Boolean algebra.

 

 

GRADING:

There will be four one- hour exams, five scheduled quizzes and a final exam.  Each of the one-hour exams will be worth 100 points, while the final exam will be worth 100-200 points.  The quizzes will be worth a total of 100-125 points.  At the discretion of the professor, supplemental problems may be assigned for credit.  These problems will be distributed in class and the due date will be announced at that time.  Each student is responsible for obtaining, completing and submitting such assignments by the due date.  Grading will be based on total points and the following percentages, although pluses or minuses may also be used.

 

A         100 – 90

B           89 – 80

C           79 – 70

D           69 – 60

F            59 –   0

 

Course Outline:

 

I.  Logic

            Propositional Logic

Propositions, truth tables, negation, conjunction, disjunction, exclusive or, conditional, biconditional, converse, contrapositive, inverse, precedence, tautologies, contradictions, contingencies, logical equivalence, disjunctive normal form, functionally complete, NAND, NOR

 

            Predicate Logic

                        Universal quantifier, existential quantifier, scope, nested quantifiers

 

Arguments

                        Premises, conclusion, valid arguments, rules of inference, fallacies

 

            Proofs

Theorems, axioms, direct proofs, indirect proofs, vacuous proof, trivial proof, counterexample, exhaustive proofs, existence proofs, uniqueness proofs, Principle of Mathematical Induction

 

II.  Sets

Sets, elements, set builder notation, finite and infinite sets, set equality, subsets, power sets, Venn diagrams, universal set, relationships among sets, intersection, union, complement, difference, properties of set operations, Cartesian products

 

III.  Relations

Binary relation, properties of relations, combining relations, representing relations, equivalence relation, equivalence classes, partitions, partial orderings, Hasse diagrams, maximal element, minimal element, bounds

IV.  Graphs

Graphs, vertices, edges, simple graph, multigraph, loop, pseudograph, digraph, degree, adjacent, incident, in-degree, out-degree, complete graphs, cycles, wheels, bipartite graphs, subgraphs, representing graphs, graph isomorphism, path, connected graph, component, Euler circuit, Euler path, Hamilton circuit, Hamilton path, weighted graph, traveling salesperson problem, cheapest link algorithm, nearest neighbor algorithm, Dijkstra's algorithm

 

V.  Trees

Tree, forests, rooted tree, tree terminology, tree traversal, infix-prefix-postfix notation, spanning tree, depth-first search, breadth-first search, minimum spanning tree, Prim's algorithm, Kruskal's algortihm

 

VI.  Boolean Algebra

Boolean Algebra, Boolean expressions, Boolean identities, duality principle, literal, fundamental product, minterm, SOP form, disjunctive normal form, functionally complete, NAND, NOR, logic gates, circuit design, Karnaugh maps

 

Sections Covered

                                    1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7

                                    2.1, 2.2

                                    4.1

                                    8.1, 8.3, 8.5, 8.6

                                    9.1, 9.2, 9.3, 9.4, 9.5, 9.6

                                    10.1, 10.3, 10.4, 10.5

                                    11.1, 11.2, 11.3, 11.4

 

Other Possible Topics

 

Number systems:     Binary, Octal, Hexidecimal, One's Complement, Two's omplement, Floating Point, Binary Coded Decimal

 

                        Functions

 

                        Combinatorics

 

Attendance Policy:

 

            Students will take exams and quizzes as scheduled.  See schedules for exams and quizzes on my web page.

 

 

Academic Honesty:

 

            See policy in the Student Handbook

 

            http://web.mnstate.edu/bring/AcademicDishonesty.htm

 

 

Calculators:  No graphing calculators or calculators on cell phones can be used during exams or quizzes.  Calculators should not be needed.

 

Please turn CELL PHONES OFF during class.

 

 

Special Accommodation:

 

Students with disabilities who believe they may need an accommodation in this class are encouraged to contact Greg Toutges, Coordinator of Disability Services, at 477-5859 (phone) or 1-800-627-3529 (MRS/TTY), CMU 114 as soon as possible to ensure that accommodations are implemented in a timely fashion.