Algorithms and Complexity

This subject is not offered in 2014.

200 hours

An undergraduate degree in a cognate discipline.

None

Basic proficiency in mathematics and computing.

AIMS

The aim of this subject is for students to develop familiarity and competence in assessing and designing computer programs for computational efficiency. Although computers manipulate data very quickly, to solve large-scale problems, we must design strategies so that the calculations combine effectively. Over the latter half of the 20 th century, an elegant theory of computational efficiency developed. This subject introduces students to the fundamentals of this theory and to many of the classical algorithms and data structures that solve key computational questions. These questions include distance computations in networks, searching items in large collections, and sorting them in order.

INDICATIVE CONTENT

Topics covered include complexity classes and asymptotic notation; empirical analysis of algorithms; abstract data types including queues, trees, priority queues and graphs; algorithmic techniques including brute force, divide-and-conquer, dynamic programming and greedy approaches; space and time trade-offs; and the theoretical limits of algorithm power.

INTENDED LEARNING OUTCOMES (ILO)

On completion of this subject the student is expected to:

1. Design, manipulate and reason about a variety of techniques for solving sorting, searching and graph problems
2. Write efficient algorithms and data structures for a variety of fundamental problems
3. Conduct formal reasoning about problem complexity and algorithmic efficiency
4. Recognize the design techniques of standard algorithms, and apply these techniques to develop new computational solutions to problems

• Project work during semester, due around weeks 6 and 11, expected to take approximately up to 48 hours (20%)
• A 45 minute mid-semester test, around week 7 (10%)
• A 3-hour end-of-semester written examination (70%)

Hurdle requirement: To pass the subject, students must obtain at least:

• 50% overall
• 30/70 in the written examination

All Intended Learning Outcomes (ILOs) are addressed in all assessment components

This subject is not available as a breadth subject.

On completion of this subject students should have the following skills:

• Application of knowledge of basic science and engineering fundamentals
• Effective communication about computational efficiency
• Capacity to reason and solve problems
• Ability to undertake problem identification, formulation and solution
• Capacity for creativity and innovation
• Profound respect for truth and intellectual integrity, and for the ethics of scholarship

LEARNING AND TEACHING METHODS

The subject involves weekly three-hour lectures. The lectures are a mix of direct delivery and interactive student problem solving. Although written assignments are submitted by students individually, in-plenum discussion of the problems is allowed, and encouraged.

INDICATIVE KEY LEARNING RESOURCES

Students are provided with lecture slides, and links on the LMS to the in-house animated software Algorithms in Action. The slides are integrated with the well-established textbook.

CAREERS / INDUSTRY LINKS

With Big Data at the forefront of modern computing solutions, industry is ever-more focused on efficient computational analysis methods. Software engineers, developers and data analysts will find not only the analysis techniques, but also the fundamental algorithmic design concepts, highly applicable to the handling of significant datasets. Building on an initial connection in a similar undergraduate offering, there is scope for industry liaison with this subject.