Faculty of Science

Objectives

To provide theoretical analysis of the most important areas of algorithm design and analysis. It provides an integrated treatment of both sequential and parallel algorithms and review fundamental notions in computability (types of problems computers can solve).

Contents

Complex treatment of computability and complexity; RAM and PRAM, sequential and parallel machines; Comparison-based algorithms, searching, selection, sorting, hashing, dynamic algorithms; information-extraction algorithms; graph, randomised algorithms, parallel algorithms, geometric algorithms; Connectivity, spanning trees; Computable functions; recursive functions; Post, Thue and semi-Thue systems; Turing machines; Church’s Thesis.