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 divide-and-conquer, greedy, recursive backtracking, dynamic programming) will be introduced using real-world examples.
|
Information for Visiting Students
| 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 |
Course Delivery Information
|
| Academic year 2022/23, 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 | |
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., 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.
- 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. |
| Keywords | Algorithms,Data Structures |
Contacts
| Course organiser | Dr Mary Cryan
Tel: (0131 6)50 5153
Email: mcryan@inf.ed.ac.uk |
Course secretary | Miss Kerry Fernie
Tel: (0131 6)50 5194
Email: kerry.fernie@ed.ac.uk |
|
|
University Homepage