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 : Computer Science 2A (INF-2-CS2A) and Computer Science 2B (INF-2-CS2B).

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

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
23/09/2005	10:00	11:00	Lecture Theatre B, 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.