5024 - Algorithms and Data Structures
Course information
- Title
- Algorithms and Data Structures
- Course number
- 5024.24
- Academic year
- 2024-2025
- ECTS
- 7.50
- Level
- Bachelor
- Faculties
- Science and Tecnology
- Educations
- BSc in Software Engineering
- Prerequisites
- Upper secondary school with mathematics at level B
- Language of instruction
- The course is taught in English. The textbook is in English and other instructional materials are in English, and possibly Faroese. Exams will be in English.
- Registration
- Students on the first and third semester of Bachelor of Science in Software Engineering are automatically enrolled. Applicants for an individual course must apply via the Student Service Center at lss@setur.fo
- Beginning date
- Thursday, August 22, 2024
- End date
- Thursday, October 10, 2024
Academic content
- Purpose
- To introduce the notation, terminology, and techniques underpinning the study of algorithms - To introduce the standard algorithmic design paradigms employed in the development of efficient algorithmic solutions - To introduce the mathematical tools needed for the analysis of algorithms in terms of the use of formal models of Time and Space
- Learning outcomes
- By the end of the course the student is expected to be able to: - describe standard algorithms such as sorting algorithms, search algorithms, string matching algorithms, graph traversal algorithms; - apply these algorithms or a given pseudo code algorithm in order to solve a given problem; - carry out simple asymptotic analyses of algorithms involving sequence, selection, and iteration, and identify and compare simple properties of these algorithms; - describe the algorithm design principles of Divide-and-Conquer, greedy method, and dynamic programming and distinguish the differences between these principles; - apply the studied algorithms that illustrate these design principles; - apply the studied design principles to produce algorithmic solutions to a given problem; - explain and illustrate the distinction between different classes of problems, in particular, polynomial time and exponential time solvable problems.
- Content
- Introduction o Definition of an algorithm, counting elementary operations during execution, worst-case analysis of running time and storage requirements - on several examples of simple algorithms o Design of pseudo code algorithms • Complexity Issues o Asymptotics and "order of" notation for complexity o Comparison of polynomial time and exponential time complexities and examples of algorithms with such complexities o Brief introduction of the notion of computable and non-computable functions • Review of Graphs structures and their representation o Directed and Undirected graphs; Trees; representation by adjacency matrices and incidence lists, graph and tree traversals • Algorithm Design Techniques o Review of the standard algorithm design paradigms commonly used in Computer Science together with typical example problems solved by these o Overview: why a range of design methods is needed o Divide-and-Conquer algorithms: general overview of approach; run-time analysis of simple Divide-and-Conquer methods via solution of recurrence relations o Dynamic Programming: differences from Divide-and-Conquer; general overview; necessity for iterative implementation o Greedy Method: concept of optimisation problem and the distinction between 'exact' and 'approximate' solution algorithms
- Learning and teaching approaches
- Lectures, theoretical- and computer-based exercises
Assessment
- Assessment method
- ▪ one or two assessments will be given during the lectures o 0% contribution to the final marks but we strongly recommend you to pass these assignments although it is not a necessary condition to get the permission for the examination ▪ 4-hour written examination (paper and pen based) o course related materials are NOT allowed o 100% contribution to the final marks
- Examination (internal/external)
- External
- Grading scale
- 7-scale
- Exam date/dates
- The written exam is set for week 43
- Deadline for withdrawal from exam
- Thursday, August 22, 2024
Academic responsibility and teachers
- Academic responsibility
- Qin Xin
- Teachers
- Qin Xin