Discrete Structures

Course descriptive guide:

Material: Chapters 1 - 8, 11’
This four credit course is designed for Computer Science Engineering majors.
Math 376 is based on COMPSCI 250, the University of Massachusetts course offered to
their Computer Science students. The course covers those fundamental Mathematical
concepts having to do with discrete structures such as mathematical reasoning and proof,
combinatorial analysis, algorithmic thinking, and applications to the computer sciences.
Mathematica labs are an integral part of the course.

Teaching Procedures:
This is essentially a lecture recitation course in which students are encouraged to be active
participants. Computer lab exercises are an integral part of the course.

Course competencies:

The student will understand and employ the basics of LOGIC .

 1. Define and construct propositions using unary and binary connectives.
 2. Set up truth tables to establish tautologies, contingencies and contradictions.
 3. Employ bit operators to manipulate string and numeric data .
 4. Translate and symbolize universal and existential quantifiers.

The student will construct, define and apply FUNCTIONS

 1. Define basic set notation terminology and perform set operations.
 2. Employ functions to examine relations between domains and ranges.
 3. Determine the convergence and divergence of sequences and series.
 4. Use exponential and factorial functions to determine function growth.

The student will employ the concepts and theorems of NUMBER THEORY

 5. Determine the computational complexity of an algorithm.
 6. Use prime and composite numbers in basic number theoretic algorithms.
 7. Use the division algorithm .
 8. Find the GCD and LCM.
 9. Use the notation and operations of modular arithmetic .
 10. Determine random number seeds and pseudorandomness.
 11. Develop and analyze encryption models.
 12. Perform binary operations.
 13. Write computer code for Euclidean algorithm.
 14. Solve problems using the Chinese Remainder Theorem.
 15. Define basic matrix operations.

The student will apply MATHEMATICAL REASONING.

 16. Define axioms and prove basic number theoretic theorems.
 17. Use the rules of inference to determine the validity of arguments.
 18. Recognize fallacies.
 19. Use the direct proof and indirect to prove theorems.
 20. Use mathematical induction to prove theorems for all n.
 21. Demonstrate existence proofs.
 22. Recognize the Halting problem and its consequences.
 23. Use the well- ordering principle .
 24. Set up recursion definitions.
 25. Employ loops and iterations to solve recursion problems.
 26. Determine program correctness.

The student will enumeric lists by applying COMBINATORICS

 27. State and use the sum rule and product rule for counting.
 28. Use the inclusion/exclusion principles in counting.
 29. Draw tree diagrams for all possible outcomes.
 30. Use Pascal's identity for counting problems.
 31. State Vandermonde's Identity.
 32. Expand binomials with the binomial theorem.
 33. Solve discrete probability problems with combinations and permutations.
 34. Do problems with conditional probability.
 35. Find the expected value of an experiment .
 36. Use Chebychev's inequality for appropriate discrete probability problems.
 37. Compute the complexity of computations.

The student will examine and compare RELATIONS.

 38. Set up mathematical models for compound interest , Fibonacci numbers and Tower of Hanoi problems.
 39. Solve homogeneous linear recurrence relations.
 40. Define binary relations.
 41. Define and recognize reflexive, symmetric and transitive properties.
 42. Define n-ary relations.
 43. Set up and solve problems using directed graphs.
 44. Define closures and paths in a given path problem.
 45. Define equivalence relations and partial orderings on a set.

The student will examine and solve problems with GRAPHS.

 46. Define a simple graph.
 47. Define a multigraph.
 48. Set up graph models to represent real world problems.
 49. Define a bipartite graph.
 50. Define and utilize a local area network.
 51. Set up an interconnected network with parallel processing.
 52. Define a subgraph.
 53. Use matrices to represent graphs.
 54. Set up an adjoining matrix and an incidence matrix.
 55. Define isomorphic.
 56. Determine connectivity of a graph.
 57. Find Euler paths of a given graph.
 58. Find Hamilton paths of a given graph.
 59. Define graph coloring

The student will define and examine FINITE STATE MACHINES

 60. Define and use language and grammar parametrics.
 61. Set up context-free and context-sensitive grammars.
 62. Define a finite state machine with and without output.
 63. Define a regular set.
 64. Define the grammar of a regular set.
 65. Define and examine the Turing Machine with its implications for computer output.

Grading:

There are five examinations for the course and a cumulative final examination counting as
two tests . There will be NO makeup tests given. The five labs will also count as one test.
Your grade will be based on the average of these scores. Class participation will be an
important part of this course, and your participation will be factored into your grade if it is
especially positive .

Description of the Course:

This course is a study of the discrete structures of Mathematics. They include
propositional calculus, quantification, sets, functions, sequences and series, number
theoretic functions, proofs - direct and indirect, induction, combinatorics, discrete
probability, recurrence relations, equivalence relations, partial orderings, graphs, paths and
finite state machines.

Attendance

Attendance is required. A student absent from class bears the full responsibility for all
subject matter taught and for all procedural information discussed including changes in
examination dates.