Course ID: A3
Unit: DATA SCIENCE AND ENGINEERING – Unit A: Algorithms and Information Technologies
Weekly Hours: 4
ECTS Credits: 7
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.