# 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.

Prev | Next |