Algorithms and Data Structures

Course Information

College	Tsuyama College	Year	2021
Course Title	Algorithms and Data Structures
Course Code	0052	Course Category	Specialized / Compulsory
Class Format	Lecture	Credits	School Credit: 2
Department	Department of Integrated Science and Technology Communication and Informations System Program	Student Grade	3rd
Term	Year-round	Classes per Week	2
Textbook and/or Teaching Materials	Textbooks :　Ibaraki Toshihide, "Algorithms and Data Structures by C(Japanese)"(Ohmusha), Reference books :　John E. Hopcroft et al., "Introduction to Automata Theory, Languages and Computation"
Instructor	KIKUCHI Yosuke

Course Objectives

Learning purposes :
Students who have taken this course can explain well-known algorithms and data structures and answer the name of algorithm and data structures when they read the explanation. They also can explain basic notion and terminology of time complexity and its related notion for considering efficiency of algorithms.

Course Objectives :
１．To be able to explain what is algorithms
２．To be able to explain well-known sorting algorithms and search algorithms
３．To be able to explain well-known data structures, e.g. stack, queue, binary tree and so on
４．To be able to use graph representation of information
５．To be able to explain string search algorithms
６．To be able to explain formal language and automata

Rubric

	Excellent	Good	Acceptable	Not acceptable
Achievement 1	The student can write down notion of complexity and its definition, also explain its meaning without any reference.	The student can write down notion of complexity and its definition, also explain its meaning with some reference.	The student can write down notion of complexity and its definition with some reference.	The student does not know notion of complexity and its definition.
Achievement 2	The student can implement sorting or search algorithms. The student can amend program of the algorithms, if it has bags.	The student can implement sorting or search algorithms.	The student can explain well-known algorithms for sorting or search.	The student can not explain well-known algorithms for sorting or search.
Achievement 3	The student can implement program using stack, queue, binary tree data structures as needed.	The student can implement program using stack, queue, binary tree data structures.	The student can explain data structures, e.g. stack queue or binary tree.	The student can not explain data structures, e.g. stack queue or binary tree.
Achievement 4	The student can explain graph algorithms, and estimate their complexity.	The student can explain graph algorithms.	The student can use graph representation.	The student does not know graph structure.
Achievement 5	The student know at least three string search algorithms and explain them.	The student know at least two string search algorithms and explain them.	The student know a string search algorithms and explain it.	The student doens not know string search algorithms.
Achievement 6	If give a language, the student can prove that the language is not regular by using pumping lemma.	The student can fugure out the automaton for a regular language.	The student can judge whether a sequence can be accepted by a given automaton.	The student can not judge whether a sequence can be accepted by a given automaton.

Teaching Method

Outline:

General or Specialized : Specialized
Foundational academic disciplines : Integrated Disciplines/Informatics/Principles of Informatics/Software
Field of learning : Infromation system・Programming・Network
Relationship with Educational Objectives :This class is equivalent to "(3) Acquire deep foundation knowledge of the major subject area".

MCC Goals(Based on the guidelie 4/28/2017 version, number in brackets is MCC level)：V-D-2 Software/Algorithms(4), Data structures(4), Program analysis, V-D-5 System programming/Compiler(4) V-D-7 Information mathematics・Information theory/applied discrete mathematics(4)

Relationship with JABEE programs :
The main goal of learning / education in this class is "A".

Course outline :
Efficiency of solving a problem by computer is depend on algorithm and data structures. This course provide basic skill of choosing and designing algorithms and data structures using well-known algorithms and data structures.

Style:

Course method :
This course is a lecture with writing on a blackboard mainly, sometimes a recitation. Students presentation may be held.
Sometimes students need to solve and submit assigments.

Grade evaluation method :
Exams (100%).
Regular examinations will be conducted 4 times, and the evaluation ratios will be weighted. As a general, retaking exams can not performed. Examinations are based on the rubric but there is no guarantee that the examinations cover achievements in rubric.

Notice:

Course advice :
This course is closely connected with mathematics and programming. Implementation of algorithms that are dealt with in this course makes deeply understanding. The student should check the theme of the lesson before attendance.

Foundational subjects : Fundamentals of Integrated Science and Technology(1st year), Basic Programming(2nd)
Related subjects : Database Systems(5th year), Advanced Programming(4th), Mathematical Information(4th)

Attendance advice :
If you are late for the start time, you will be treated as 1 period absence.
If you are 50 minutes late, you will be treated as 2 periods absence.You can consult with BlackBoard(LMS).

Characteristics of Class / Division in Learning

Aided by ICT

Applicable to Remote Class

Instructor Professionally Experienced

Ｍｕｓｔ　ｃｏｍｐｌｅｔｅ　ｓｕｂｊｅｃｔｓ

Course Plan

			Theme	Goals
1st Semester
	1st Quarter
		1st	Guidance
		2nd	Algorithms and time complexity	Students can give some examples of mathematical modelings of actual problems
		3rd	Basic data structures 1	Student can give at least 2 suitable data structures for given mathematical modeling.
		4th	Basic data structures 2	Student can design data structure for given mathematical modeling.
		5th	Sorting algorithms 1	Students can explain bubble sort algorithm and insertion sort algorithm.
		6th	Sorting algorithms 2	Students can explain quick sort algorithm and merge sort algorithm and so on.
		7th	Sorting algorithms 3	Students can explain bucket sort algorithm.
		8th	Time complexity of sorting algorithms	Students can explain complexity of sorting.
	2nd Quarter
		9th	1st semester mid-term exam
		10th	Return and commentary of exam answers
		11th	Tree data structures 1	Students can explain binary search trees and blalanced trees.
		12th	Tree data structures 2	Students can explain B trees.
		13th	Graph algorithms 1	Students can use graphs as mathmematical modeling. Students can explain data structures of graphs.
		14th	Graph algorithms 2	Students can explain depth first search and breadth first search
		15th	(1st semester final exam)
		16th	Return and commentary of exam answers
2nd Semester
	3rd Quarter
		1st	Graph algorithms 3	Students can use algorithm for shortest path problem.
		2nd	Graph algorithms 4	Students can use algorithm for network flow problem.
		3rd	String search algorithms 1	Students can explain Rabin-Karp string search algorithm.
		4th	String search algorithms 2	Students can explain Knuth-Morris-Pratt algorithm.
		5th	String search algorithms 3	Students can explain Moyer-Moore string search algorithm.
		6th	Greedy algorithms and dynamic programming 1	Students can explain greedy algorithm
		7th	Greedy algorithms and dynamic programming 2	Students can explain dynamic programming.
		8th	Computability	Students know undecidable problem.
	4th Quarter
		9th	2nd semester mid-term exam
		10th	Return and commentary of exam answers
		11th	Formal language	Student can explain notion of formal language.
		12th	Automata	Student can explain notion of automata.
		13th	Regular expression and automata	Student can explain relation between regular expressions and finite automata.
		14th	Compiller	Student can explain the role and mechanism.
		15th	(2nd semester final exam)
		16th	Return and commentary of exam answers

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