Semester: 1

Credit: 2

Program: Computer Science

Course Module: Specialized Compulsory

Responsible: Mei Yu

E-mail: yumei@tju.edu.cn

Department: College of Intelligence and Computing, Tianjin University

Time Allocation (1 credit hour = 45 minutes)

4

12

16

16

Prerequisite

Ÿ Theoretical computer science: Computational time complexity and space complexity

Ÿ Structure-oriented programming language or object-oriented programming language

Ÿ Basic knowledge of sequence tables, linked lists, binary tree, and methods on the data structure

Ÿ Graph theory, tree-related knowledge, and methods on the data structure.

Course Objectives

This course mainly introduces the concept and construction method of data structure and related operations that can be performed using the data structure. After learning the theoretical knowledge, you can understand the modeling method and modeling process of the data structure. After completing this course, students should be able to:

Ÿ Master the relevant methods and methods of using arrays, trees, and graphs to construct advanced data structures

Ÿ Model and solve problems using data structures and implement coding

Ÿ Master how to analyze the complexity of time and space

Course Syllabus

Ÿ Basic data structures: linear list, stack, queue, tree, and graph

Ÿ Tree data structure union search and its application

Ÿ Tree Data Structure Binary Search Tree and Its Application

Ÿ Basic path search algorithm and topological sorting

Ÿ Connectivity: strong connectivity, correlation connectivity, etc.

Ÿ Minimum tree coverage: Dijkstra algorithm, Kruskal algorithm

Ÿ Shortest path algorithm: Dijkstra algorithm, Bellman-Ford algorithm

Textbooks & References

Ÿ John E. Hopcroft, Rajeev Motwani.Introduction to automata theory, languages, and computation(3rd ed). Pearson, 2006.

Ÿ Michael Sipser.Introduction to the Theory of Computation (3rd ed). Cengage Learning, 2012.

Ÿ Jürgen Dassow, Gheorghe Paun.Regulated rewriting in formal language theory (1st ed). Springer Publishing Company, 2012.

Peter Linz.An Introduction to Formal Languages and Automata (5th ed). Jones & Bartlett Learning, 2011.

Capability Tasks

Descriptions of each level are illustrated below:

CT1: To understand basic science, and to have analytical ability and the ability to integrate related knowledge.

CT2: To apply relevant professional knowledge to the field of science and technology: understanding of the basic concepts and its connotation, application of different methods and concepts which have been learned, capability of judging the scope and limitations of such applications.

CT3: To grasp methodologies and engineering tools: identifying, utilizing and solving problems. Even if the students are not familiar with the content, they can turn to computer tools for systematic analysis.

CT4: To carry out experiments in research environment with the abilities to utilize tools, especially for data collection and processing.

CT11: To have the capacity to understand and evaluate one’s work and understand one’s own abilities (especially in a certain respect of the discipline) and to be able to make correct career choice.

CS1: Master the basic theoretical knowledge of own major and understand the development status and trend of own major.

CS2: Firmly master the core knowledge and relevant engineering knowledge for computer major, and possess the primary capability of applying the core knowledge and engineering knowledge to system development.

CS3：Able to possess relatively good system analysis and software design capabilities, master advanced technologies for solving the actual project problems, able to participate in formulating actual engineering solutions, participate in formulating implementation plans, implement project solutions and complete project tasks, and able to undertake engineering or management work, and effectively solve actual engineering problems in the field of computer science.

Achievements

Understand concepts related to advanced data structures-LevelN

Encode data structures using familiar programming languages-LevelM

Analyze time complexity and space complexity of existing data structure systems-LevelN

Use data structures to model problems and optimize legacy systems-Level M

Students:Computer Science，Year 1

Assessment：

Exam

Assignment

Experiment

Attendence

Presentation

Others

√

√

√

√

√

Language of assessment：chinese

Attendance： 5% Homework: 20 % Presentation: 5%

Experiment： 20% Final report/test： 50 %