INF2-IADS: Course Learning Outcomes and Outline

Learning Outcomes

On successful completion of this course, you should be able to: 

1. Explain both formally and informally the difference between "best", "expected", and "worst" case behaviour of an algorithm, and use asymptotic notation to analyse the time and space complexity of algorithms. Use recurrence relations to determine the time complexity of recursively defined algorithms.

2. Describe the properties, typical implementations, and example application use cases of abstract data types (e.g., stacks, queues, sets, dictionaries, priority queues) and discuss the costs and benefits of dynamic and static data structure implementations; use the above knowledge to justify the selection of appropriate data types in a range of settings.

3. Work with a range of data structures to implement basic algorithms given pseudocode or a task specification; perform empirical studies to compare the performance of different implementations of the same algorithm or data type on various input (or different algorithms for the same problem) and explain what can be learned from empirical analysis that cannot be learned from asymptotic analysis (and vice versa).

4. Describe various algorithmic strategies (e.g., brute-force, greedy, divide-and-conquer, recursive backtracking, dynamic programming) and give examples of each from a range of application areas including language processing and information retrieval. Hand-simulate a range of algorithms, including algorithms for searching, sorting, hashing, solving graph problems, and examples of dynamic programming. Give example applications that would use each algorithm and choose appropriate algorithms to use for example problems.

5. Define informally the classes P and NP and give examples of problems in NP. Explain the halting problem and its significance.

Course Outline

This course is an important foundation for all areas of Informatics. 

It runs for the full year (10 credits in each semester), with approximately 15 lectures per semester. A mixture of tutorials and labs will be used to reinforce both mathematical and practical knowledge of algorithms and data structures, including differences between theoretical and empirical analysis. 

Students' ability to implement and empirically analyse algorithms will be assessed via practical coursework, with an exam to assess other aspects of the course (knowledge and choice of existing algorithms and data structures, theoretical analysis, algorithmic strategies, and applications). 

The following is an indicative list of topics covered: 

• Asymptotic notation and algorithmic analysis 
• Sequential data structures (lists, stacks, queues) 
• Basic and more advanced sorting algorithms 
• Tree data structures, heaps and priority queues 
• Hashing and dictionaries 
• Graphs and graph algorithms 
• Dynamic programming 
• The classes P and NP 

Throughout, different specific algorithms and algorithmic strategies (such as divide-and-conquer, greedy, recursive backtracking, dynamic programming) will be introduced using real-world examples.