Faculty of Science

Objectives

To provide skills on how data may be structured and instructions sequenced in algorithms and programmes as well as the relationship between appropriate data and control structures and tasks from the “real world”.

Contents

Relevant constructs in a programming language; techniques in algorithm design; further recursion; naturally recursive problems; efficiency considerations (informal) in selecting algorithms; simple analysis of algorithms; (e.g., best-/worst-case performance, space-time efficiency and tradeoffs); Data structures (both static and dynamic): arrays; single and double linked lists; binary trees; various data structures for stacks and queues, matrix representation; Introductory notions on abstract data types; File structures: notion of a record; variant records; logical and physical files; reading/writing to sequential and random access files; managing free blocks; text files; B-trees; Inverted files; Further sorting algorithms (e.g. quick sort); sorting records in files; Search algorithms e.g. iterative, recursive; binary tree search; Fibonacci search; hashing techniques; Representation of graphs; topological sort, shortest distance problems; spanning trees; mention of NP-complete problems.

Prerequisite: