Skip to main content

Algoritmur og datastrukturar

Lecture Plan

TOPICS
Thursday 8th March Monday 12th March Basics (what is an algorithm and its representation by pseudo code) and Mathematical Induction
Thursday 15th March Monday 19th March Efficiency of algorithms (searching, Big-O notation)
Thursday 22nd March Monday 26th March Polynomial and Exponential algorithms (pattern matching, sorting algorithms, exhaustive search algorithms - Traveling Salesman Problem, Knapsack Problem)
Monday 29th March Thursday 12th April Divide and Conquer technique (mergesort, tower of hanoi, fibonacci number, time complexity analysis via recurrence relations)
Monday 16th April Thursday 19th April Review of graph structures and some basic graph algorithms (undirected and directed graphs and their representations, trees; depth first search, breadth first search)
Monday 23rd April Thursday 26th April Greedy methods (Single-source shortest path problem, Minimum Spanning Tree)
Monday 30th April Thursday 3rd May Dynamic programming technique (Fibonacci number, assembly line scheduling)

Course Description

TitleAlgorithms and Data Structures
Course no.50??.10
ECTS7.5
Prerequisites 
Aims•    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•    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.
SyllabusIntroduction
•    Definition of an algorithm, counting elementary operations during execution, worst-case analysis of running time and storage requirements - on several examples of simple algorithms. Design of pseudo code algorithms.
Complexity Issues
•    Asymptotics and "order of" notation for complexity. Comparison of polynomial time and exponential time complexities and examples of algorithms with such complexities. Brief introduction of the notion of computable and non-computable functions.
Review of Graphs structures and their representation
•    Directed and Undirected graphs; Trees; representation by adjacency matrices and incidence lists, graph and tree traversals.
Algorithm Design Techniques
•    Review of the standard algorithm design paradigms commonly used in Computer Science together with typical example problems solved by these.
    - Overview: why a range of design methods is needed.
    - Divide-and-Conquer algorithms: general overview of approach; run-time analysis of simple Divide-and-Conquer methods via solution of recurrence relations.
    - Dynamic Programming: differences from Divide-and-Conquer; general overview; necessity for iterative implementation.
    - Greedy Method: concept of optimisation problem and the distinction between 'exact' and 'approximate' solution algorithms.
Tutorials 
•    It will be arranged when it is necessary.
DømingKravda verkætlanarfrágreiðingin og munnlig framløga av frágreiðingini. Galdandi próvtalsstigi verður nýttur.

Textbook

INTRODUCTION TO THE DESIGN AND ANALYSES OF ALGORITHMS, Anany V. Levitin, Villanova University, 2011 (Third Edition), Addison-Wesley.

Further Reading:
INTRODUCTION TO ALGORITHMS, TH Cormen, CE Leiserson and RL Rivest, MIT Press/McGraw-Hill, 3rd Edition, 2009.

ContactProf. Dr. Qin Xin, QinX@setur.fo
Course Web Page

Link to the course web page:
www.setur.fo/index.php
 

Course Start8th March, 2012
Course End3rd May, 2012
TeachingEvery Monday and Thursday from 9:15am to 3pm
Assignments

•    Two assessments will be given on 12th April and 19th April respectively and submissions for both of them have to be done before 27th April, 2012.
•    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.

Examination•    4-hour written examination on Monday 14th May, 2012.
•    100% contribution to the final marks.