BSc:DiscreteMathandLogic

Discrete Math and Logic

• Course name: Discrete Math and Logic
• Course number: XYZ
• Knowledge area: Math, Computational Science

Administrative details

• Faculty: Computer Science and Engineering
• Year of instruction: 1st year of BS
• Semester of instruction: 1st semester
• No. of Credits: 4 ECTS
• Total workload on average: 144 hours overall
• Frontal lecture hours: 2 per week
• Frontal tutorial hours: 0 per week
• Lab hours: 2 per week
• Individual lab hours: 0
• Frequency: weekly throughout the semester
• Grading mode: letters: A, B, C, D

Prerequisites

Elementary Algebra and Planimetry (at high-school level)

Course outline

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 & 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. The course is based on a textbook “Discrete Mathematics and Its Applications” by K.H. Rosen and a non-conventional textbook “Concrete Mathematics” by R.L. Graham, D.E. Knuth and O. Patashnik (specially designed as a mathematical complement for “The Art of Computer Programming”).

Expected learning outcomes

The course will provide an opportunity for participants to:

• know elements and basics of set theory, theory of relations and functions, enumerating Combinatorics, graph theory, discrete optimization and propositional logic and reasoning ;
• understand role of set theory in foundations of mathematics and role of discrete mathematics for foundations of programming and modeling of discrete system ;
• get practical experience with basic algorithms in discrete mathematics and propositional logic.

Programming related learning outcomes

• None.

Expected acquired core competences

• Basic proof techniques (by construction, by induction, by contradiction);
• sets and naïve set theory, relations and functions;
• finite combinatorics and discrete probability;
• graphs and trees;
• discrete optimization, dynamic programming;
• lattices and Boolean algebras;
• propositional logic and calculus;
• propositional modelling and propositional satisfiability problem.

Required computer resources

No computer resources are required for this course.

Evaluation

• Grading items:
  • In-class participation 1 point per week for each individual contribution in class (i.e. 14 points overall).
  • Final overall in-course participation/contribution (“instructors’ gratitude”) 6 points.
  • Each in-class theory or practice tests – up to 10 points (i.e. 40 points overall).
  • Mid-term exam up to 20 points, final examination up to 20 points (i.e. 40 points overall).
• Final grade scale:
  • A: 80..100 points (i.e. 80% at least);
  • B: 70..79 points (i.e. 70% at least);
  • C: 60..69 points (i.e. 60% at least);
  • D: less than 60 points.