Course Objectives
[1] Can read a technical book written in English.
[2] Can explain the fundamentals of graphs.
[3] Can explain the fundamentals of algorithms.
[4] Can explain the fundamentals of trees.
[5] Can explain graph traversal algorithms.
Rubric
| Ideal Level | Standard Level | Unacceptable Level |
| Achievement 1 | Can read a technical book written in English with little use of a dictionary. | Can read a technical book written in English using a dictionary. | Cannot read a technical book written in English. |
| Achievement 2 | Can explain the fundamentals of graphs sufficiently. | Can explain the fundamentals of graphs. | Cannot explain the fundamentals of graphs. |
| Achievement 3 | Can explain the fundamentals of algorithms sufficiently. | Can explain the fundamentals of algorithms. | Cannot explain the fundamentals of algorithms. |
| Achievement 4 | Can explain the fundamentals of trees sufficiently. | Can explain the fundamentals of trees. | Cannot explain the fundamentals of trees. |
| Achievement 5 | Can explain graph traversal algorithms sufficiently. | Can explain graph traversal algorithms. | Cannot explain graph traversal algorithms. |
Assigned Department Objectives
Teaching Method
Outline:
Learn the fundamentals of graphs and graph algorithms using a technical book written in English.
Style:
Read a technical book written in English in turns. Each page is translated in Japanese alternatively by teacher, student 1, teacher, student 2, ... . During a student translates, the teacher asks the student if necessary.
Notice:
This course's content will amount to 90 hours of study in total. These hours include the learning time guaranteed in classes and the standard self-study time required for pre-study / review, and completing assignment reports.
To achieve these goals, students are required to self-study outside of classes:
(1) Read several pages of the technical book before each class.
(2) Write two assignment reports.
Students who miss 1/3 or more of classes will not be eligible for evaluation.
Characteristics of Class / Division in Learning
Course Plan
|
|
|
Theme |
Goals |
| 1st Semester |
| 1st Quarter |
| 1st |
What is a graph |
Can explain the definition of a graph. Also, can explain what a graph models.
|
| 2nd |
The degree of a vertex, isomorphic graphs |
Can explain things related to the degree of a vertex and isomorphic graphs.
|
| 3rd |
Subgraphs and degree sequences |
Can explain things related to subgraphs and degree sequences.
|
| 4th |
Connected graphs, cut vertices and bridges |
Can explain things related to connected graphs, cut vertices and bridges.
|
| 5th |
Special graphs
|
Can explain complete graphs, bipartite graphs and hypercubes.
|
| 6th |
Digraphs |
Can explain things related to digraphs.
|
| 7th |
Algorithmic complexity
|
Can explain algorithmic complexity and order notation.
|
| 8th |
Search algorithms and sorting algorithms
|
Can explain the binary search algorithm and bubblesort algorithm.
|
| 2nd Quarter |
| 9th |
Introducing NP-completeness
|
Can explain NP-completeness.
|
| 10th |
Greedy algorithms and representing graphs in a computer
|
Can explain greedy algorithms. Also, can explain the adjacency matrix of a graph, the adjacency list of a graph, stack and queue.
|
| 11th |
Properties of trees
|
Can explain the fundamental properties of trees.
|
| 12th |
Rooted trees
|
Can explain things related to rooted trees.
|
| 13th |
Depth-first search
|
Can explain the depth-first search algorithm.
|
| 14th |
Finding Blocks
|
Can explain an algorithm that finds the blocks of a graph.
|
| 15th |
Breadth-first search
|
Can explain the Breadth-first search algorithm.
|
| 16th |
No final exam
|
|
Evaluation Method and Weight (%)
| Explanation when reading in turns | Report | Mutual Evaluations between students | Behavior | Portfolio | Other | Total |
| Subtotal | 60 | 40 | 0 | 0 | 0 | 0 | 100 |
| Basic Proficiency | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Specialized Proficiency | 60 | 40 | 0 | 0 | 0 | 0 | 100 |
| Cross Area Proficiency | 0 | 0 | 0 | 0 | 0 | 0 | 0 |