Undergraduate Course: Informatics 2  Introduction to Algorithms and Data Structures (INFR08026)
Course Outline
School  School of Informatics 
College  College of Science and Engineering 
Credit level (Normal year taken)  SCQF Level 8 (Year 2 Undergraduate) 
Availability  Available to all students 
SCQF Credits  20 
ECTS Credits  10 
Summary  This course provides a formal and practical introduction to the algorithms and data structures that underlie all areas of computation. It aims to provide students with a toolbox of standard algorithms and data structures, as well as the skills to analyse both the theoretical complexity of algorithms and their practical behaviour. Both written and programming exercises will be used, with examples from all areas of Informatics. 
Course description 
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 divideandconquer, greedy, recursive backtracking, dynamic programming) will be introduced using realworld examples.

Information for Visiting Students
Prerequisites  Students should have completed a minimum of two semesters of programming courses and at least one semester of Universitylevel mathematics. A previous course in discrete mathematics is strongly recommended. 
High Demand Course? 
Yes 
Course Delivery Information

Academic year 2019/20, Available to all students (SV1)

Quota: None 
Course Start 
Full Year 
Timetable 
Timetable 
Learning and Teaching activities (Further Info) 
Total Hours:
200
(
Lecture Hours 30,
Seminar/Tutorial Hours 10,
Supervised Practical/Workshop/Studio Hours 8,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 4,
Directed Learning and Independent Learning Hours
146 )

Assessment (Further Info) 
Written Exam
80 %,
Coursework
20 %,
Practical Exam
0 %

Additional Information (Assessment) 
20% coursework/80% exam weighting
There will be a practical assignment.

Feedback 
Students will receive oral feedback from tutors and demonstrators during tutorial and lab sessions. Written feedback will be provided on a formative assignment prior to summative practical assessment. 
Exam Information 
Exam Diet 
Paper Name 
Hours & Minutes 

Main Exam Diet S2 (April/May)   2:00   Resit Exam Diet (August)   2:00  
Learning Outcomes
On completion of this course, the student will be able to:
 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.
 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.
 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).
 Describe various algorithmic strategies (e.g., bruteforce, greedy, divideandconquer, recursive backtracking, dynamic programming) and give examples of each from a range of application areas including language processing and information retrieval. Handsimulate 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.
 Define informally the classes P and NP and give examples of problems in NP. Explain the halting problem and its significance.

Reading List
Recommended supplementary reading: Introduction to Algorithms, by Cormen, Leiserson, Rivest, Shamir. 
Additional Information
Graduate Attributes and Skills 
Problemsolving, critical thinking and analytical thinking, scientific writing skills. 
Keywords  Algorithms,Data Structures 
Contacts
Course organiser  Dr Mary Cryan
Tel: (0131 6)50 5153
Email: mcryan@inf.ed.ac.uk 
Course secretary  Ms Kendal Reid
Tel: (0131 6)51 3249
Email: kr@inf.ed.ac.uk 

