Semester: 1

Credit: 3

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)

12

24

12

16

Prerequisite

Ÿ Theoretical computer science: Computational time complexity and space complexity

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

Ÿ Basic knowledge of algorithm design for greedy, recursive, and enumeration methods

Ÿ Ability to program using algorithms

Course Objectives

This course mainly introduces the relevant content of advanced algorithms and related operations that can be performed using advanced algorithms. After learning the theoretical knowledge, you can use algorithms for programming modeling and use familiar programming languages to implement algorithm models. After completing this course, students should be able to:

Ÿ Mastering the method of analyzing the time complexity and space complexity of the algorithm can prove the correctness and completeness of the proposed algorithm.

Ÿ Can flexibly design algorithms for problems, and use the knowledge learned to design and solve more complex algorithm modeling processes

Ÿ Program the algorithm model to ensure the robustness and execution efficiency of the program.

Course Syllabus

Ÿ Basic algorithms: knowledge about enumeration, greedy and recursive

Ÿ Sorting algorithms: basic sorting algorithm, merge sort, quick sort

Ÿ String search algorithm KMP, BM algorithm, Tire tree algorithm

Ÿ Hash algorithm and common methods of processing hash algorithm, analysis of execution efficiency of hash 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 algorithm design -Level N

Coding Algorithms Using Familiar Programming Languages -Level M

Analyze the time complexity and space complexity of existing algorithms -Level N

Use more efficient algorithms to model problems and optimize existing programs -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 %