Difference between revisions of "BSc: Logic and Discrete Mathematics"

From IU
Jump to navigation Jump to search
 
(15 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
* '''Course name''': Logic and Discrete Mathematics (Philosophy 1)
  
* '''Course name''': Logic and Discrete Mathematics (Philosophy 1)
 
* '''Code discipline''': CSE113
  
* '''Code discipline''': CSE113
−
* '''Subject area''': Math. Computer Science
 +
* '''Subject area''': Math, Computer Science
 
== Short Description ==
  
== Short Description ==
 
This course consists of two distinct but overlapping parts: i. Logic; and ii. Discrete Mathematics.
  
This course consists of two distinct but overlapping parts: i. Logic; and ii. Discrete Mathematics.
Line 59: Line 59:
 
==== Level 1: What concepts should a student know/remember/explain? ====
  
==== Level 1: What concepts should a student know/remember/explain? ====
 
By the end of the course, the students should be able to ...
  
By the end of the course, the students should be able to ...
  +
*know the categorical logic
−
* remember the differentiation techniques
  
  +
*know the propositional logic
−
* remember the integration techniques
  
  +
*know the predicate logic
−
* remember how to work with sequences and series
  
  +
*explain the difference between deduction and induction
  +
*know the trees and spanning trees
  +
*remember the Euler and Hamilton graphs
  +
* know what is planar graphs
  +
* explain the Dijkstra’s algorithm
   
 
==== Level 2: What basic practical skills should a student be able to perform? ====
  
==== Level 2: What basic practical skills should a student be able to perform? ====
 
By the end of the course, the students should be able to ...
  
By the end of the course, the students should be able to ...
  +
* use Venn diagrams
−
* apply the derivatives to analyse the functions
  
  +
* calculate truth values
−
* integrate
  
  +
* analyse formal structures of some arguments
−
* understand the basics of approximation
  
  +
* differ the deduction and induction
  +
* build spanning trees
  +
* find Euler tour and Hamilton path
  +
* use Dijkstra’s algorithm
  +
* solve maximum flow problem
   
 
==== Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios? ====
  
==== Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios? ====
 
By the end of the course, the students should be able to ...
  
By the end of the course, the students should be able to ...
  +
...
−
* Take derivatives of various type functions and of various orders
  
−
* Integrate
  
−
* Apply definite integral
  
−
* Expand functions into Taylor series
  
−
* Apply convergence tests
  
   
 
== Grading ==
  
== Grading ==
Line 85: Line 91:
 
! Grade !! Range !! Description of performance
  
! Grade !! Range !! Description of performance
 
|-
  
|-
−
| A. Excellent || 90-100 || -
 +
| A. Excellent || 85-100 || -
 
|-
  
|-
−
| B. Good || 75-89 || -
 +
| B. Good || 75-84 || -
 
|-
  
|-
 
| C. Satisfactory || 60-74 || -
  
| C. Satisfactory || 60-74 || -
Line 100: Line 106:
 
! Activity Type !! Percentage of the overall course grade
  
! Activity Type !! Percentage of the overall course grade
 
|-
  
|-
−
| Midterm || 20
 +
| Midterm || 40
 
|-
  
|-
  +
| Final exam || 40
−
| Quizzes || 28 (2 for each)
  
 
|-
  
|-
−
| Final exam || 50
 +
| In-class participation || 20
−
|-
  
−
| In-class participation || 7 (including 5 extras)
  
 
|}
  
|}
   
Line 117: Line 121:
   
 
=== Open access resources ===
  
=== Open access resources ===
  +
* K.H. Rosen, Discrete Mathematics and Its Applications (7th Edition). McGraw Hill, 2012.
−
* Jerrold E. Marsden and Alan Weinstein, Calculus I, II, and II. Springer-Verlag, Second Edition 1985
  
  +
* Lehman, E., Leighton, F. T., Meyer, A. R. (2017). ''<span>Mathematics for Computer Science. Massachusetts Institute of Technology Press.''<span>
−
* Zorich, V. A. Mathematical Analysis I, Translator: Cooke R. (2004)
  
−  
−
=== Software and tools used within the course ===
  
−
* No.
  
   
 
== Activities and Teaching Methods ==
  
== Activities and Teaching Methods ==
Line 200: Line 201:
   
 
==== Section 1 ====
  
==== Section 1 ====
  +
#Solve Truth Tables
−
# A plane curve is given by <math>x(t)=-\frac{t^2+4t+8}{t+2}</math>, <math display="inline">y(t)=\frac{t^2+9t+22}{t+6}</math>. Find
  
  +
#Use Truth Tables to analyse arguments
−
#: the asymptotes of this curve;
  
  +
#Use Quantifiers to assess inferences
−
#: the derivative <math display="inline">y'_x</math>.
  
  +
#What is Propositional Logic used for?
−
# Apply Leibniz formula Find <math display="inline">y^{(n)}(x)</math> if <math display="inline">y(x)=\left(x^2-2\right)\cos2x\sin3x</math>.
  
  +
#What is Predicate Logic used for?
−
#: Draw graphs of functions
  
−
#: Find asymptotes
  
−
# Find the derivatives of the following functions:
  
−
#* <math display="inline">f(x)=\log_{|\sin x|}\sqrt[6]{x^2+6}</math>;
  
−
#* <math display="inline">y(x)</math> that is given implicitly by <math display="inline">x^3+5xy+y^3=0</math>.
  
   
 
==== Section 2 ====
  
==== Section 2 ====
−
# Find the following integrals:
  
−
#*<math display="inline">\int\frac{\sqrt{4+x^2}+2\sqrt{4-x^2}}{\sqrt{16-x^4}}\,dx</math>;
  
−
#*<math display="inline">\int2^{2x}e^x\,dx</math>;
  
−
#*<math display="inline">\int\frac{dx}{3x^2-x^4}</math>.
  
−
# Find the indefinite integral <math display="inline">\displaystyle\int x\ln\left(x+\sqrt{x^2-1}\right)\,dx</math>.
  
−
# Find the length of a curve given by <math display="inline">y=\ln\sin x</math>, <math display="inline">\frac{\pi}4\leqslant x\leqslant\frac{\pi}2</math>.
  
   
 
==== Section 3 ====
  
==== Section 3 ====
  +
−
# Find limits of the following sequences or prove that they do not exist:
  
  +
#What is the characteristic property of trees?
−
#* <math>a_n=n-\sqrt{n^2-70n+1400}</math>;
  
  +
#How to find an Euler tour?
−
#* <math display="inline">d_n=\left(\frac{2n-4}{2n+1}\right)^{n}</math>;
  
  +
#What is a Hamilton path?
−
#* <math display="inline">x_n=\frac{\left(2n^2+1\right)^6(n-1)^2}{\left(n^7+1000n^6-3\right)^2}</math>.
  
  +
#Why are K3 and K5,5 not planar?
  +
#What is the difference between undirected and directed graphs?
  +
#Why do we consider weighted graphs?
  +
#What practical problems are solved using Dijkstra's algorithm?
  +
#What is the maximum flow problem?
   
 
=== Final assessment ===
  
=== Final assessment ===
−
'''Section 1'''
 +
==== Section 1 ====
  +
#What is the difference between Categorical and Propositional Logic?
−
# Apply the appropriate differentiation technique to a given problem.
  
  +
#How does Predicate Logic differ from Categorical and Propositional Logic?
−
# Find a derivative of a function
  
  +
#Why is Predicate Logic so important?
−
# Apply Leibniz formula
  
  +
#What are Truth-Functions and why do we use them?
−
# Draw graphs of functions
  
  +
#Compute True Tables for Propositions
−
# Find asymptotes of a parametric function
  
  +
#Compute True Tables for Arguments
   
−
'''Section 2'''
 +
==== Section 2 ====
  +
#
−
# Apply the appropriate integration technique to the given problem
  
−
# Find the value of the devinite integral
  
−
# Calculate the area of the domain or the length of the curve
  
   
−
'''Section 3'''
 +
==== Section 3 ====
  +
#Explain handshaking lemma.
−
# Find a limit of a sequence
  
  +
#Give necessary and sufficient conditions for the existence of an Euler tour.
−
# Find a limit of a function
  
  +
#Give sufficient conditions for the existence of a Hamilton path (theorems of Dirac and Ore).
  +
#Explain Kuratowski’s theorem.
  +
#Explain the difference between undirected and directed graphs.
  +
#Give the definition of weighted graphs?
  +
#Explain Dijkstra's algorithm?
  +
#What is the solution of the maximum flow problem (the Ford-Fulkerson algorithm)?
   
 
=== The retake exam ===
  
=== The retake exam ===

Latest revision as of 17:02, 25 July 2023

Logic and Discrete Mathematics (Philosophy 1)

  • Course name: Logic and Discrete Mathematics (Philosophy 1)
  • Code discipline: CSE113
  • Subject area: Math, Computer Science

Short Description

This course consists of two distinct but overlapping parts: i. Logic; and ii. Discrete Mathematics. The first part of the course is an introduction to formal symbolic logic. Philosopher John Locke once wrote that ``logic is the anatomy of thought. This part of the course will teach students to analyse and evaluate arguments using the formal techniques of modern symbolic logic. The second part of the is designed for students to teach them basic notions of graph theory, discrete optimization and dynamic programming. This part will give practical experience with basic algorithms in discrete mathematics.

Course Topics

Course Sections and Topics
Section Topics within the section
Basic of Logic
  1. Logical Operators
  2. Truth Tables for Propositions
  3. Propositional calculus
  4. Quantifiers
  5. Predicate Logic
  6. Basic Proof Techniques in Math
  7. Fundamental proofs
  8. Use of propositional calculus to do proofs
Set Theory & Finite combinatorics
  1. Fundamentals of the set theory
  2. From sets to relations
  3. Functions and numbers
  4. Algebra of binary relations
  5. Principles of finite combinatorics
  6. Recursion and Discrete Optimization
  7. Linear recurrence relations
Basic of Graphs
  1. From set and relations to graphs
  2. Euler tours and graphs
  3. Hamilton paths and graphs
  4. Planar graphs and Euler formula
  5. Trees and Kőnig's infinity lemma

Intended Learning Outcomes (ILOs)

What is the main purpose of this course?

This calculus course will provide an opportunity for participants to:

  • understand key principles involved in differentiation and integration of functions
  • solve problems that connect small-scale (differential) quantities to large-scale (integrated) quantities
  • become familiar with the fundamental theorems of Calculus
  • get hands-on experience with the integral and derivative applications and of the inverse relationship between integration and differentiation.

ILOs defined at three levels

We specify the intended learning outcomes at three levels: conceptual knowledge, practical skills, and comprehensive skills.

Level 1: What concepts should a student know/remember/explain?

By the end of the course, the students should be able to ...

  • know the categorical logic
  • know the propositional logic
  • know the predicate logic
  • explain the difference between deduction and induction
  • know the trees and spanning trees
  • remember the Euler and Hamilton graphs
  • know what is planar graphs
  • explain the Dijkstra’s algorithm

Level 2: What basic practical skills should a student be able to perform?

By the end of the course, the students should be able to ...

  • use Venn diagrams
  • calculate truth values
  • analyse formal structures of some arguments
  • differ the deduction and induction
  • build spanning trees
  • find Euler tour and Hamilton path
  • use Dijkstra’s algorithm
  • solve maximum flow problem

Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios?

By the end of the course, the students should be able to ... ...

Grading

Course grading range

Grade Range Description of performance
A. Excellent 85-100 -
B. Good 75-84 -
C. Satisfactory 60-74 -
D. Fail 0-59 -

Course activities and grading breakdown

Activity Type Percentage of the overall course grade
Midterm 40
Final exam 40
In-class participation 20

Recommendations for students on how to succeed in the course

  • Participation is important. Attending lectures is the key to success in this course.
  • Review lecture materials before classes to do well.
  • Reading the recommended literature is obligatory, and will give you a deeper understanding of the material.

Resources, literature and reference materials

Open access resources

  • K.H. Rosen, Discrete Mathematics and Its Applications (7th Edition). McGraw Hill, 2012.
  • Lehman, E., Leighton, F. T., Meyer, A. R. (2017). Mathematics for Computer Science. Massachusetts Institute of Technology Press.

Activities and Teaching Methods

Teaching and Learning Methods within each section
Teaching Techniques Section 1 Section 2 Section 3
Problem-based learning (students learn by solving open-ended problems without a strictly-defined solution) 1 1 1
Project-based learning (students work on a project) 0 0 0
Modular learning (facilitated self-study) 0 0 0
Differentiated learning (provide tasks and activities at several levels of difficulty to fit students needs and level) 1 1 1
Contextual learning (activities and tasks are connected to the real world to make it easier for students to relate to them) 0 0 0
Business game (learn by playing a game that incorporates the principles of the material covered within the course) 0 0 0
Inquiry-based learning 0 0 0
Just-in-time teaching 0 0 0
Process oriented guided inquiry learning (POGIL) 0 0 0
Studio-based learning 0 0 0
Universal design for learning 0 0 0
Task-based learning 0 0 0
Activities within each section
Learning Activities Section 1 Section 2 Section 3
Lectures 1 1 1
Interactive Lectures 1 1 1
Lab exercises 1 1 1
Experiments 0 0 0
Modeling 0 0 0
Cases studies 0 0 0
Development of individual parts of software product code 0 0 0
Individual Projects 0 0 0
Group projects 0 0 0
Flipped classroom 0 0 0
Quizzes (written or computer based) 1 1 1
Peer Review 0 0 0
Discussions 1 1 1
Presentations by students 0 0 0
Written reports 0 0 0
Simulations and role-plays 0 0 0
Essays 0 0 0
Oral Reports 0 0 0

Formative Assessment and Course Activities

Ongoing performance assessment

Section 1

  1. Solve Truth Tables
  2. Use Truth Tables to analyse arguments
  3. Use Quantifiers to assess inferences
  4. What is Propositional Logic used for?
  5. What is Predicate Logic used for?

Section 2

Section 3

  1. What is the characteristic property of trees?
  2. How to find an Euler tour?
  3. What is a Hamilton path?
  4. Why are K3 and K5,5 not planar?
  5. What is the difference between undirected and directed graphs?
  6. Why do we consider weighted graphs?
  7. What practical problems are solved using Dijkstra's algorithm?
  8. What is the maximum flow problem?

Final assessment

Section 1

  1. What is the difference between Categorical and Propositional Logic?
  2. How does Predicate Logic differ from Categorical and Propositional Logic?
  3. Why is Predicate Logic so important?
  4. What are Truth-Functions and why do we use them?
  5. Compute True Tables for Propositions
  6. Compute True Tables for Arguments

Section 2

Section 3

  1. Explain handshaking lemma.
  2. Give necessary and sufficient conditions for the existence of an Euler tour.
  3. Give sufficient conditions for the existence of a Hamilton path (theorems of Dirac and Ore).
  4. Explain Kuratowski’s theorem.
  5. Explain the difference between undirected and directed graphs.
  6. Give the definition of weighted graphs?
  7. Explain Dijkstra's algorithm?
  8. What is the solution of the maximum flow problem (the Ford-Fulkerson algorithm)?

The retake exam

Retakes will be run as a comprehensive exam, where the student will be assessed the acquired knowledge coming from the textbooks, the lectures, the labs, and the additional required reading material, as supplied by the instructor. During such comprehensive oral/written the student could be asked to solve exercises and to explain theoretical and practical aspects of the course.

Retrieved from "https://eduwiki.innopolis.university/index.php?title=BSc:_Logic_and_Discrete_Mathematics&oldid=8313"