¹û¶³Ó°Ôº

Aims:

To introduce more formal aspects of algorithms and data structures, techniques for analysing the complexity of algorithms, and to discuss the limits of computation (intractable and undecidable problems).

Intended learning outcomes:

On successful completion of the module, a student will be able to:

1. Understand how to use a variety of data structures.
2. Understand a variety of common algorithms and why some are more efficient than others
3. Carry out time complexity analysis in a variety of scenarios.
4. Discuss intractable and undecidable problems.

Indicative content:

The following are indicative of the topics the module will typically cover:

Algorithms and Data Structures:

• Why study algorithms and data structures?
• Pseudocode.
• Efficiency of algorithms.
• Recursion.
• Arrays.
• Approaches to algorithm design including greedy and divide and conquer.
• Graph traversal.

Analysis of Algorithms:

• Empirical vs theoretical analysis.
• Algorithmic complexity.
• O-notation.
• Forms of time complexity analysis (worst case, average case, best worst case).
• Sums of series and simple summation formulae.
• Recursive algorithms and recurrence relations.

Limits of Computation:

• Tractable and intractable problems.
• The complexity classes P, NP, NPC.
• Undecidability.

Requisites:

To be eligible to select this module, a student must: (1) be registered on a programme and year of study for which it is a formally available; and (2) have also selected Introductory Programming (COMP0066), App Engineering (COMP0067), and Computer Architecture and Operating Systems (COMP0068).