BSc:DiscreteMathematics new

From IU
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Discrete Mathematics

  • Course name: Discrete Mathematics
  • Course number: XYZ
  • Subject area: Mathematics

Course characteristics

Key concepts of the class

  • Basic proof techniques (by construction, by induction, by contradiction)
  • sets and naíve set theory, relations and functions
  • finite combinatorics and discrete probability, discrete optimization
  • directed and undirected graphs, graph traverses and trees

What is the purpose of this course?

The course is designed for Software Engineering and Computer Science students to teach them basic reasoning and proving skills and provide them by a correct knowledge of basic (core) concepts, definitions, theoretical results and elementary applied methods and techniques of the set theory, algebra of relations and functions, finite combinatorics and discrete probability, graph theory, discrete optimization and dynamic programming, lattice theory and Boolean algebras, Boolean logic and propositional calculus, propositional modelling and satisfiability. All definitions and theorem statements (that will be given in lectures and that are needed to explain the keywords listed above) will be formally stated, but just few of them will be formally proven. Instead (in practice classes) we will try these definitions and theorems on work with routine exercises and a little bit more complicated (complex) problems.

Course Objectives Based on Bloom’s Taxonomy

- What should a student remember at the end of the course?

  • elements and basics of the naïve set theory,
  • basic concepts of relations and functions,
  • basic formulas of enumerating Combinatorics,
  • basic definitions and properties of graph theory,
  • propositional logic and reasoning,
  • match the concrete numerical approach with the necessary level of accuracy.

- What should a student be able to understand at the end of the course?

  • role of proof techniques for sound reasoning in mathematics
  • role of set theory in foundations of mathematics
  • role of discrete mathematics for foundations of programming
  • role of discrete mathematics for modeling of discrete systems

- What should a student be able to apply at the end of the course?

  • basic graph algorithms (path-finding, drawing, traversing)
  • basic algorithm design techniques (backtracking, branch-and-bound, dynamic programming)
  • basic propositional reasoning algorithms (satisfiability, tautology, derivation)

Course evaluation

Course grade breakdown
Proposed points
Labs/seminar classes 20 20
Interim performance assessment 30 40
Exams 50 40

If necessary, please indicate freely your course’s features in terms of students’ performance assessment:

Labs/seminar classes:

  • In-class participation 1 point for each individual contribution in a class but not more than 1 point a week (i.e. 14 points in total for 14 study weeks),
  • overall course contribution (to accumulate extra-class activities valuable to the course progress, e.g. a short presentation, book review, very active in-class participation, etc.) up to 6 points.

Interim performance assessment:

  • Each of 4 (2 theory and 2 practice) in-class tests costs 10 points.

Exams:

  • mid-term exam and final examination costs up to 20 points each (i.e. 40 points for both).

Overall score:

100 points (100%).

Grades range

Course grading range
Proposed range
A. Excellent 90-100 80-100
B. Good 75-89 70-79
C. Satisfactory 60-74 60-69
D. Poor 0-59 0-59

If necessary, please indicate freely your course’s grading features:

  • A: at least 80% of the overall score;
  • B: at least 70% of the overall score;
  • C: at least 60% of the overall score;
  • D: less than 60% of the overall score.

Resources and reference material

Textbook:

Reference material:

Course Sections

The main sections of the course and approximate hour distribution between them is as follows:

Course Sections
Section Section Title Lectures Seminars Self-study Knowledge
Number (hours) (labs) evaluation
1 Basic proof techniques and the naïve set theory 6 6 6 1
2 Basics of relations, functions and enumerating combinatorics 8 8 8 2
3 Basics of graphs theory, trees and discrete optimization 8 8 8 1
Final examination 2

Section 1

Section title:

Basic proof techniques and the naïve set theory

Topics covered in this section:

  • Basic proof techniques (by construction, by contradiction, by induction)
  • Postulates of the naïve set theory.
  • Introduction of (natural and rational) numbers in the naïve set theory.
  • Principle of mathematical induction.

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 0
Homework and group projects & 0
Midterm evaluation & 0
Testing (written or computer based) & 1
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 1


Typical questions for ongoing performance evaluation within this section

  1. Define set intersection using the postulates of the naïve set theory.
  2. Compute the number of parenthesis in the numeral for natural number .
  3. Prove existence of the natural numbers using the naïve set theory.
  4. Define addition for natural numbers using the naïve set theory.

Typical questions for seminar classes (labs) within this section

  1. Define the standard binary set union using the naïve set theory.
  2. Compute the number of subsets in the numeral for natural number .
  3. Define “less than” binary relation on the natural numbers using the naïve set theory.
  4. Proof (using the naïve set theory) uniqueness of the natural numbers.

Test questions for final assessment in this section

  1. Define the standard binary Cartesian product using the naïve set theory.
  2. Compute the length of the representation of the numeral for natural number .
  3. Define multiplication on the natural numbers using the naïve set theory.
  4. Proof existence of rational numbers using the naïve set theory.

Section 2

Section title:

Basics of relations, functions and enumerating combinatorics

Topics covered in this section:

  • Relations and functions, operations and relations over a set
  • Algebra of binary relations
  • Denotational semantics of a simple imperative programming language
  • Three main principles of finite combinatorics
  • Arrangements, permutations, combinations and some other selected combinatoric formulas

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 0
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 1


Typical questions for ongoing performance evaluation within this section

  1. Compute the number of partial functions from a finite set with elements to a finite set with elements.
  2. What is the decimal size of ?
  3. Show that the number of compositions of with exactly addends is .
  4. Course has enrolled students, a project group must consist of students, groups will be formatted in random. Explain what does this statement mean? (I.e. explain what are , , and in the definition of the probability space.)

Typical questions for seminar classes (labs) within this section

  1. Let be integer; explain (don’t prove!) using intuitive set theory why
    • ;
    • .
  2. Evaluate (without use of a computer) the decimal size of (i.e. provide reliable/provable lower and upper bound for the length of the decimal representation of this number).
  3. Prove that in the denotational semantics programs and .
  4. Prove that the reflexive-transitive closure of a binary relation is the least reflexive and transitive binary relation that contains .

Test questions for final assessment in this section

  1. Characterize in the terms of arity, reflexivity, symmetry, etc.,
    • relations “a number is prime”, “numbers are co-prime”, “a number is a common multiple of two numbers” on natural numbers;
    • relations “less than”, “not-greater than”, etc., on natural numbers;
    • relations “less than”, “not-greater than”, etc., on rational and real numbers.
  2. Prove the following equalities in any algebra of binary relations:
    • ;
    • ;
    • .
  3. Define (separately) antisymmetric, symmetric-, reflexive-, transitive- closures of a binary relation.
  4. Explain (using the standard set-theoretic notation and operations) how to build the above closures from the equality, and the inverse .

Section 3

Section title:

Basics of graphs theory, trees and discrete optimization

Topics covered in this section:

  • Definition and main properties of graphs and digraphs.
  • Selected classes of (di)graphs (empty, complete, chains, etc).
  • Euler graphs.
  • Graph complements and “almost all graphs”.
  • Plane and planar graphs, Euler formula.
  • Graph traversing, (directed) trees, König Lemma.

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 0
Homework and group projects & 0
Midterm evaluation & 0
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 1


Typical questions for ongoing performance evaluation within this section

  1. Draw complete graphs of orders , , and .
  2. How many Petri nets (without edge multiplicities) with places and transitions do exist?
  3. Check Euler’s formula for the regular dodecahedron.
  4. A terminal node of a graph is a node with degree . Prove that a tree has at least 2 terminal nodes.

Typical questions for seminar classes (labs) within this section

  1. How many edges has the complete graph of order ? How many edges has the complete digraph of order ?
  2. Expend Euler theorem (about Euler paths) on multi-graphs.
  3. Prove that and aren’t planar graphs.
  4. A spanning tree of a graph is a tree that contains all nodes of the graph.
    • Prove that any spanning tree of a connected -graph results after removal of edges.
    • Does removal of any set consisting of edges results in a tree?

Test questions for final assessment in this section

  1. How many edges has complete biograph ?
  2. Check that the graphs , , and are self-complementary.
  3. Prove that every finite planar graph has the average node degree is less than .
  4. Draw all (a) forests and (b) trees of orders from to .