Class Description

Course ID: A3

Unit: DATA SCIENCE AND ENGINEERING – Unit A: Algorithms and Information Technologies

Weekly Hours: 4

Type:

ECTS Credits: 7

Course Homepage: 

Description: • Computational problems and formal languages. • Turing machines. • Complexity measures: running time and working space. • Non-deterministic Turing machines. • Complexity classes. • Relations between complexity classes. • Hierarchy Theorems. The Gap Theorem. • Polynomial time reductions and completeness. • The class NP. • Cookʼ s Theorem. • NP-complete problems in logic. • NP-complete problems in graphs. • NP-complete problems in sets. • NP-complete problems in numbers and pseudo-polynomial algorithms.