Math 2150 DISCRETE STRUCTURES (4) 2005

Catalog Description

Topics in discrete mathematics. Elementary logic, set theory and relations; induction, enumeration techniques, recurrence relations, trees and graphs. Boolean algebra, algorithm analysis. Prerequisite: Math 1304.

Note to the instructor: This course covers a variety of topics, intro- ducing students to some interesting and useful areas of mathematics. This class, together with linear algebra, serve to show lower- division students what more there is to math than calculus. Also, a key goal of the course is better problem-solving and proof techniques by all of the students. The course should also show students how discrete mathematics is used.

Topics covered:

Sets, operations on sets

Relations and functions: binary relations, orders, equivalence relations and partitions Logic and propositional calculus Boolean algebra

Methods of proof: what is a proof? how does one do a proof? Induction proof techniques

Recursive definitions and algorithms: mathematical view

Combinatorics: permutations, combinations

Graphs: connectivity, trees, spanning trees, paths, etc.

Algorithms: integers and alogithms, number theory, complexity

Requirements and suggestions for the course:

  • Emphasize problem-solving techniques. Try to help students understand how to approach challenging problems.
  • Emphasize proofs. Students should be able to identify a good proof, and should be able to construct proofs of their own. They should understand proof by contradiction, induction, etc.
  • Cover applications of fields where possible, especially to areas of Computer Science.
  • Good communication skills are required on all written work.
  • Group discussions and problem-solving sessions are encouraged.
  • Various mathematical systems are covered in the course. Students should be exposed to the basic ideas and encouraged to take further courses.

Texts:

Rosen : Discrete Mathematics and its Applications

Ross and Wright: Discrete Mathematics

Mott, Kandel, Baker: Discrete Mathematics for Computer Scientists and Mathematicians