# DEGREE REGULATIONS & PROGRAMMES OF STUDY 2023/2024

### Timetable information in the Course Catalogue may be subject to change.

 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)

 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 divide-and-conquer, greedy, recursive backtracking, dynamic programming) will be introduced using real-world examples.
 Pre-requisites Students MUST have passed: Informatics 1 - Introduction to Computation (INFR08025) AND Informatics 1 - Object Oriented Programming (INFR08029) It is RECOMMENDED that students have passed Proofs and Problem Solving (MATH08059) OR Discrete Mathematics and Probability (INFR08031) Co-requisites Prohibited Combinations Other requirements Non-Informatics degree students must have completed a minimum of 20 credits of maths in year 1. For Informatics students (including those on joint degrees), mathematical prerequisites are covered by your required maths courses.
 Pre-requisites Students 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
 Academic year 2023/24, 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 60 %, Coursework 40 %, Practical Exam 0 % Additional Information (Assessment) Weighting is 30% coursework, 10% short quizzes, and 60% 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
 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 algorithmsdescribe 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 settingswork 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., 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 problemsdefine informally the classes P and NP and give examples of problems in NP. Explain the halting problem and its significance
 Recommended supplementary reading: Introduction to Algorithms, by Cormen, Leiserson, Rivest, Shamir.
 Graduate Attributes and Skills Problem-solving, critical thinking and analytical thinking, scientific writing skills. Keywords Algorithms,Data Structures
 Course organiser Dr Aris Filos-Ratsikas Tel: Email: Aris.Filos-Ratsikas@ed.ac.uk Course secretary Miss Kerry Fernie Tel: (0131 6)50 5194 Email: kerry.fernie@ed.ac.uk
 Navigation Help & Information Home Introduction Glossary Search DPTs and Courses Regulations Regulations Degree Programmes Introduction Browse DPTs Courses Introduction Humanities and Social Science Science and Engineering Medicine and Veterinary Medicine Other Information Combined Course Timetable Prospectuses Important Information