Discrete Mathematics Ｂ

Course Information

College	Akashi College	Year	2022
Course Title	Discrete Mathematics Ｂ
Course Code	4417	Course Category	Specialized / Compulsory
Class Format	Lecture	Credits	School Credit: 1
Department	Electrical and Computer Engineering Computer Engineering Course	Student Grade	4th
Term	Second Semester	Classes per Week	2
Textbook and/or Teaching Materials
Instructor	HAMADA Yukihiro

Course Objectives

[1] Can explain the generalized concept of being equal and being larger (smaller).
[2] Can explain the basics of graph theory.
[3] Can explain the basics of formal language theory.

Rubric

	Ideal Level	Standard Level	Unacceptable Level
Achievement 1	Can explain the equivalence relation, partial orders, and total orders accurately.	Can explain the equivalence relation, partial orders, and total orders.	Cannot explain the equivalence relation, partial orders, and total orders.
Achievement 2	Can explain the path, connectivity, and tree of graph theory accurately.	Can explain the path, connectivity, and tree of graph theory.	Cannot explain the path, connectivity, and tree of graph theory.
Achievement 3	Can use Backus form, context-free grammar, finite automaton, and regular grammar correctly.	Can use Backus form, context-free grammar, finite automaton, and regular grammar.	Cannot use Backus form, context-free grammar, finite automaton, and regular grammar.

Teaching Method

Outline:

Discrete mathematics is a field of mathematics that deals with finite or discrete subjects, and one of the foundations of computer science. In this course, you will learn about relations on a set, graphs and trees, finite automaton and regular grammar.

Style:

Classes will be held in a lecture style.

Notice:

Make sure you understand the exact definition of the term and get an intuitive image from the formal description. Try to solve the examples or exercise problems yourself and score it against the answer.
Students who miss 1/3 or more of classes will not be eligible for a passing grade.

Characteristics of Class / Division in Learning

Aided by ICT

Applicable to Remote Class

Course Plan

			Theme	Goals
2nd Semester
	3rd Quarter
		1st	Binary relation 1 of 2	Can explain the basics of binary relation.
		2nd	Binary relation 2 of 2	Can calculate composition and exponentiation of binary relation.
		3rd	Equivalence relation 1/2	Can explain the equivalence relation, which is a generalization of the concept of equal.
		4th	Equivalence relation 2/2	Can handle equivalence class, quotient set, and subdivisions of equivalence relation.
		5th	Order 1 of 2	Can explain the partially ordered set and total order of the inequality (=) generalization.
		6th	Order 2 of 2	Can handle the upper extremum, lower extremum, maximum, and minimum values of a partially ordered set, and can explain the above (below) boundary.
		7th	Midterm exam It is given during class.
		8th	Illustration of binary relation	Can illustrate the binary relation as a directed graph.
	4th Quarter
		9th	Hasse diagram, topological sort, and transitive closure	Can draw a Hasse diagram of partially ordered set, and can explain the closure of topological sort and transitive.
		10th	Graph basics 1 of 2	Can explain the basics of graphs.
		11th	Graph basics 2 of 2	Can explain n-partite graph and several kinds of paths in a graph. Also, can represent a graph by adjacency matrix, adjacency list and incidence matrix.
		12th	The connectivity of a graph	Can explain the diameter, radius, connected component, cut vertex, bridge, connectivity and edge connectivity. Also, can explain n-connected and n-edge connected.
		13th	Tree	Can explain the fundamental concepts and theorems about trees. Also, can explain ordered tree, positional tree, binary tree and n-ary tree.
		14th	Finite automaton and nondeterministic finite automaton	Can define FA and NFA formally and draw their state transition diagrams. Also, can determine the language that they accept.
		15th	Regular grammar and regular expression	Can define right linear grammar and left linear grammar formally, and determine the language that they generate. Can represent a given language by regular expression.
		16th	Final exam

Evaluation Method and Weight (%)

	Examination	Presentation	Mutual Evaluations between students	Behavior	Portfolio	Other	Total
Subtotal	100	0	0	0	0	0	100
Basic Proficiency	0	0	0	0	0	0	0
Specialized Proficiency	100	0	0	0	0	0	100
Cross Area Proficiency	0	0	0	0	0	0	0