Algorithms and Data Structures (U01895)

? Credit Points : 10 ? SCQF Level : 9 ? Acronym : INF-3-ADS

The course aims to provide general techniques for the design of efficient algorithms and, in parallel, develop appropriate mathematical tools for analysing their performance. In this, it broadens and deepens the study of algorithms and data structures initiated in CS2. Along the way, problem solving skills are exercised and developed.

Entry Requirements

? Pre-requisites : Pass in Informatics 2B. Passes in Maths-for-Inf-3 and Maths-for-Inf-4 (unless the student is a joint Maths-CS student, in which case they should have passed their 2nd year Maths program). Successful completion of Year 2 of an Informatics Single or Combined Degree, or equivalent by permission of the School. Students are also expected to have a strong mathematical background.

Variants

? This course has variants for part year visiting students, as follows

Algorithms and Data Structures (VS1) (Semester 1 (Blocks 1-2))

Subject Areas

Home subject area

Theoretical Computer Science, (School of Informatics, Schedule O)

Delivery Information

? Normal year taken : 3rd year

? Delivery Period : Semester 1 (Blocks 1-2)

? Contact Teaching Time : 3 hour(s) per week for 10 weeks

First Class Information

Date	Start	End	Room	Area	Additional Information
22/09/2006	10:00	10:50	Lecture Theatre 6301, JCMB	KB

All of the following classes

Type	Day	Start	End	Area
Lecture	Tuesday	10:00	10:50	KB
Lecture	Friday	10:00	10:50	KB

Summary of Intended Learning Outcomes

A student who has attended this course:
- Should know the major algorithms for well-known combinatorial problems such as Sorting, Martix Multiplication, Minimum Spanning Trees, and other problems listed in the syllabus.
- Should be familiar with algorithmic strategies such as Divide-and-Conquer, the Greedy strategy and Dynamic Programming, and should be able to test these strategies on new problems and identify whether or not they are likely to be useful for those problems.
- Should be able to construct clear and rigorous arguments to prove correctness/running-time bounds of algorithms, and should be able to present these arguments in writing.
- Should understand the importance of the data structures used in a particular implementation of an algorithm, and how the data structure that is used can affect the running time.
- Should be able to construct simple lower bound arguments for algorithmic problems, and to understand the relationship between upper and lower bounds. Also should be able to perform simple average-case analyses of the running-time of an algorithm, as well as worst-case analyses.