Information in the Degree Programme Tables may still be subject to change in response to Covid-19

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

Undergraduate Course: Informatics 2 - Introduction to Algorithms and Data Structures (INFR08026)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Credit level (Normal year taken)SCQF Level 8 (Year 2 Undergraduate) AvailabilityAvailable to all students
SCQF Credits20 ECTS Credits10
SummaryThis 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 divide-and-conquer, greedy, recursive backtracking, dynamic programming) will be introduced using real-world examples.
Entry Requirements (not applicable to Visiting Students)
Pre-requisites Students MUST have passed: Informatics 1 - Introduction to Computation (INFR08025)
Students MUST have passed: Informatics 1 - Object-Oriented Programming (INFR08014) OR Informatics 1 - Object Oriented Programming (INFR08029)
Prohibited Combinations Other requirements Non-Informatics degree students must have completed a minimum of 20 credits of maths in year 1 and are strongly recommended to have taken (or be taking) Proofs and Problem Solving (MATH08059) or Discrete Mathematics and Probability (INFR08031). For Informatics students (including those on joint degrees), mathematical prerequisites are covered by your required maths courses.
Information for Visiting Students
Pre-requisitesStudents should have completed a minimum of two semesters of programming courses and at least one semester of University-level mathematics. A previous course in discrete mathematics is strongly recommended.
High Demand Course? Yes
Course Delivery Information
Academic year 2020/21, 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 50 %, Coursework 50 %, Practical Exam 0 %
Additional Information (Assessment) Weighting is 30% coursework, 10% short quizzes, 10% course engagement contributions, and 50% exam.
There will be at least one 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:
  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.
Reading List
Recommended supplementary reading: Introduction to Algorithms, by Cormen, Leiserson, Rivest, Shamir.
Additional Information
Graduate Attributes and Skills Problem-solving, critical thinking and analytical thinking, scientific writing skills.
KeywordsAlgorithms,Data Structures
Course organiserDr Mary Cryan
Tel: (0131 6)50 5153
Course secretaryMs Kendal Reid
Tel: (0131 6)51 3249
Help & Information
Search DPTs and Courses
Degree Programmes
Browse DPTs
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Important Information