10.90.136.10: Created page with "= Discrete Mathematics = * '''Course name:''' Discrete Mathematics * '''Course number:''' XYZ * '''Subject area:''' Mathematics == Cou..."

2021-07-30T10:09:28Z

Created page with "= Discrete Mathematics = * '''Course name:''' Discrete Mathematics * '''Course number:''' XYZ * '''Subject area:''' Mathematics == Cou..."

New page

= 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
!
!
!align="center"| '''Proposed points'''
|-
| Labs/seminar classes
| 20
|align="center"| 20
|-
| Interim performance assessment
| 30
|align="center"| 40
|-
| Exams
| 50
|align="center"| 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
!
!
!align="center"| '''Proposed range'''
|-
| A. Excellent
| 90-100
|align="center"| 80-100
|-
| B. Good
| 75-89
|align="center"| 70-79
|-
| C. Satisfactory
| 60-74
|align="center"| 60-69
|-
| D. Poor
| 0-59
|align="center"| 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
|align="center"| '''Section'''
| '''Section Title'''
|align="center"| '''Lectures'''
|align="center"| '''Seminars'''
|align="center"| '''Self-study'''
|align="center"| '''Knowledge'''
|-
|align="center"| '''Number'''
|
|align="center"| '''(hours)'''
|align="center"| '''(labs)'''
|align="center"|
|align="center"| '''evaluation'''
|-
|align="center"| 1
| Basic proof techniques and the naïve set theory
|align="center"| 6
|align="center"| 6
|align="center"| 6
|align="center"| 1
|-
|align="center"| 2
| Basics of relations, functions and enumerating combinatorics
|align="center"| 8
|align="center"| 8
|align="center"| 8
|align="center"| 2
|-
|align="center"| 3
| Basics of graphs theory, trees and discrete optimization
|align="center"| 8
|align="center"| 8
|align="center"| 8
|align="center"| 1
|-
|align="center"| Final examination
|
|align="center"|
|align="center"|
|align="center"|
|align="center"| 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? ===

<div class="tabular">

|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 

</div>
=== Typical questions for ongoing performance evaluation within this section ===

# Define set intersection using the postulates of the naïve set theory.
# Compute the number of parenthesis in the numeral for natural number <math display="inline">n</math>.
# Prove existence of the natural numbers using the naïve set theory.
# Define addition for natural numbers using the naïve set theory.

=== Typical questions for seminar classes (labs) within this section ===

# Define the standard binary set union using the naïve set theory.
# Compute the number of subsets in the numeral for natural number <math display="inline">n</math>.
# Define “less than” binary relation on the natural numbers using the naïve set theory.
# Proof (using the naïve set theory) uniqueness of the natural numbers.

=== Test questions for final assessment in this section ===

# Define the standard binary Cartesian product using the naïve set theory.
# Compute the length of the representation of the numeral for natural number <math display="inline">n</math>.
# Define multiplication on the natural numbers using the naïve set theory.
# 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? ===

<div class="tabular">

|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 

</div>
=== Typical questions for ongoing performance evaluation within this section ===

# Compute the number of partial functions from a finite set with <math display="inline">n</math> elements to a finite set with <math display="inline">m</math> elements.
# What is the decimal size of <math display="inline">2_{10}^{100}</math>?
# Show that the number of compositions of <math display="inline">n\geq 0</math> with exactly <math display="inline">k\geq 0</math> addends is <math display="inline">C_{n-1}^{k-1}</math>.
# Course has <math display="inline">90</math> enrolled students, a project group must consist of <math display="inline">3</math> students, groups will be formatted in random. Explain what does this statement mean? (I.e. explain what are <math display="inline">\Omega</math>, <math display="inline">\mathcal{F}</math>, and <math display="inline">P</math> in the definition of the probability space.)

=== Typical questions for seminar classes (labs) within this section ===

# Let <math display="inline">n,k>0</math> be integer; explain (don’t prove!) using intuitive set theory why
#* <math display="inline">C^k_n=C^{k-1}_{n-1}+C^{k}_{n-1}</math>;
#* <math display="inline">\sum_{m=0}^{m=n}C_n^m\ =2^n</math>.
# Evaluate (without use of a computer) the decimal size of <math display="inline">100!</math> (i.e. provide reliable/provable lower and upper bound for the length of the decimal representation of this number).
# Prove that in the denotational semantics programs <math display="inline">\left(\alpha;(\beta;\gamma)\right)</math> and <math display="inline">\left((\alpha;\beta);\gamma\right)</math>.
# Prove that the reflexive-transitive closure <math display="inline">R^*</math> of a binary relation <math display="inline">R</math> is the least reflexive and transitive binary relation that contains <math display="inline">R</math>.

=== Test questions for final assessment in this section ===

# 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.
# Prove the following equalities in any algebra of binary relations:
#* <math display="inline">(P\circ Q)\circ R\ =\ P\circ(Q \circ R)</math>;
#* <math display="inline">(P\circ Q)^-\ =\ Q^-\circ P^-</math>;
#* <math display="inline">(P\cup Q)^-\ =\ P^-\cup Q^-</math>.
# Define (separately) antisymmetric, symmetric-, reflexive-, transitive- closures of a binary relation.
# Explain (using the standard set-theoretic notation and operations) how to build the above closures from the equality, <math display="inline">R</math> and the inverse <math display="inline">R^-</math>.

=== 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? ===

<div class="tabular">

|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 

</div>
=== Typical questions for ongoing performance evaluation within this section ===

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

=== Typical questions for seminar classes (labs) within this section ===

# How many edges has the complete graph of order <math display="inline">n</math>? How many edges has the complete digraph of order <math display="inline">n</math>?
# Expend Euler theorem (about Euler paths) on multi-graphs.
# Prove that <math display="inline">K_5</math> and <math display="inline">K_{3,3}</math> aren’t planar graphs.
# A spanning tree of a graph is a tree that contains all nodes of the graph.
#* Prove that any spanning tree of a connected <math display="inline">(m n</math>-graph results after removal of <math display="inline">(m-n+1)</math> edges.
#* Does removal of any set consisting of <math display="inline">(m-n+1)</math> edges results in a tree?

=== Test questions for final assessment in this section ===

# How many edges has complete biograph <math display="inline">K_{m,n}</math>?
# Check that the graphs <math display="inline">K_1</math>, <math display="inline">P_4</math>, and <math display="inline">C_5</math> are self-complementary.
# Prove that every finite planar graph has the average node degree is less than <math display="inline">6</math>.
# Draw all (a) forests and (b) trees of orders from <math display="inline">1</math> to <math display="inline">6</math>.

BSc:DiscreteMathematics new - Revision history

10.90.136.10: Created page with "= Discrete Mathematics = * '''Course name:''' Discrete Mathematics * '''Course number:''' XYZ * '''Subject area:''' Mathematics == Cou..."