BSc:DiscreteMathematics new

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.

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

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 ${\textstyle n}$.
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 ${\textstyle n}$.
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 ${\textstyle n}$.
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 ${\textstyle n}$ elements to a finite set with ${\textstyle m}$ elements.
2. What is the decimal size of ${\textstyle 2_{10}^{100}}$?
3. Show that the number of compositions of ${\textstyle n\geq 0}$ with exactly ${\textstyle k\geq 0}$ addends is ${\textstyle C_{n-1}^{k-1}}$.
4. Course has ${\textstyle 90}$ enrolled students, a project group must consist of ${\textstyle 3}$ students, groups will be formatted in random. Explain what does this statement mean? (I.e. explain what are ${\textstyle \Omega }$, ${\textstyle {\mathcal {F}}}$, and ${\textstyle P}$ in the definition of the probability space.)

Typical questions for seminar classes (labs) within this section

1. Let ${\textstyle n,k>0}$ be integer; explain (don’t prove!) using intuitive set theory why
   • ${\textstyle C_{n}^{k}=C_{n-1}^{k-1}+C_{n-1}^{k}}$;
   • ${\textstyle \sum _{m=0}^{m=n}C_{n}^{m}\ =2^{n}}$.
2. Evaluate (without use of a computer) the decimal size of ${\textstyle 100!}$ (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 ${\textstyle \left(\alpha ;(\beta ;\gamma )\right)}$ and ${\textstyle \left((\alpha ;\beta );\gamma \right)}$.
4. Prove that the reflexive-transitive closure ${\textstyle R^{*}}$ of a binary relation ${\textstyle R}$ is the least reflexive and transitive binary relation that contains ${\textstyle R}$.

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:
   • ${\textstyle (P\circ Q)\circ R\ =\ P\circ (Q\circ R)}$;
   • ${\textstyle (P\circ Q)^{-}\ =\ Q^{-}\circ P^{-}}$;
   • ${\textstyle (P\cup Q)^{-}\ =\ P^{-}\cup Q^{-}}$.
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, ${\textstyle R}$ and the inverse ${\textstyle R^{-}}$.

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 ${\textstyle 2}$, ${\textstyle 3}$, ${\textstyle 4}$ and ${\textstyle 6}$.
2. How many Petri nets (without edge multiplicities) with ${\textstyle m}$ places and ${\textstyle n}$ transitions do exist?
3. Check Euler’s formula for the regular dodecahedron.
4. A terminal node of a graph is a node with degree ${\textstyle 1}$. 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 ${\textstyle n}$? How many edges has the complete digraph of order ${\textstyle n}$?
2. Expend Euler theorem (about Euler paths) on multi-graphs.
3. Prove that ${\textstyle K_{5}}$ and ${\textstyle K_{3,3}}$ 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 ${\textstyle (mn}$-graph results after removal of ${\textstyle (m-n+1)}$ edges.
   • Does removal of any set consisting of ${\textstyle (m-n+1)}$ edges results in a tree?

Test questions for final assessment in this section

1. How many edges has complete biograph ${\textstyle K_{m,n}}$?
2. Check that the graphs ${\textstyle K_{1}}$, ${\textstyle P_{4}}$, and ${\textstyle C_{5}}$ are self-complementary.
3. Prove that every finite planar graph has the average node degree is less than ${\textstyle 6}$.
4. Draw all (a) forests and (b) trees of orders from ${\textstyle 1}$ to ${\textstyle 6}$.