This course provides a study of theories and techniques of algorithm design and analysis. For algorithm design, students will study a wide range of algorithmic solutions to problems from various application areas, including searching, sorting, optimization, and important problems in graph theory. In addition, important design paradigms will be covered including greedy methods, divide-and-conquer methods, dynamic programming, backtracking, and branch-and-bound methods. For algorithm analysis, students will practice analyzing the execution time and the resource consumption of algorithms, and related mathematical techniques.

Practical study related to 13016212 Data Structures and Algorithms

This course provides a study of the nature of logic and logical reasoning, covering the following topics: arguments, syntax and semantics of propositional logic, validity and equivalence in propositional logic, truth tables, basic proof theory for propositional logic, syntax and semantics of first-order logic, validity and equivalence in first-order logic, basic proof theory for first-order logic, limitations of first-order logic, and applications of logic for problem solving.

This course studies three important methods for software verification and validation: testing, peer reviews, and formal verification, with emphasis on testing. Topics on testing include the necessity and limitations of testing, an overview of test processes, testing throughout the software development life cycle, unit testing, test design techniques, test automation, tool support for testing, and test management. The course will study how software peer reviews, which can help detect and prevent software defects, are carried out in practice and study the inspection processes throughout the software development life cycle, including the inspection of requirement documents, design documents, code, and test plans. The course will also provide a basic understanding of formal verification, including how to prove the correctness of a simple program using Hoare logic.

This course provides an introduction to the theory of computation, covering the following topics: strings and languages, finite automata, equivalence of deterministic finite automata and nondeterministic finite automata, regular languages, regular expressions, regular grammars, relations between regular languages and regular grammars, properties of regular languages, pumping lemma for regular languages, context-free grammar, pushdown automata, relations between pushdown automata and context-free languages, properties of context-free languages, pumping lemma for context-free languages, Turing machines, equivalence of nondeterministic Turing machines and deterministic Turing machines, undecidable problems, computational complexity, important complexity classes (such as P, NP, and EXPTIME), reduction, and complete complexity classes.