Introduction to algoritmiths and data structures
Using your “Dankort”, looking at a time table, travelling with DSB, surfing on the Internet, withdrawing money from the bank, calling a friend –all these and many more everyday activities depend on algorithms.
Algorithm is about methods for solving problems with different resources and limits. The problems and resources can be of many kinds. Often, we want a computer to perform a calculation as fast as possible using a minimum of the available memory. In this case the resources are calculation time and used memory space. The given problem could be finding the shortest route between two cities. But algorithms can be of relevance to many other kinds of problems and resources, e.g. minimizing the number of transistors on a chip or minimizing the number of mouse-clicks needed to navigate through a homepage.
Developing software it is important that both the designer and the programmer know what kind of problems the computer can solve and how it can do it efficiently. A good software developer/programmer should know about the methods needed to obtain the desired efficiency. Knowing about algorithms is therefore essential to the software developing process.
Many technological advances depend on efficient algorithms while others are still looking for efficient solutions. Building, e.g. a search engine for the Internet, big geographical databases, and route planning systems, effective algorithms are both fundamental and essential parts of the technology. At present, sequence analyses in DNA strings for genetic and biotechnological uses is one of the big research areas for algorithms.
The aim of the courseThe course aims at giving you a fundamental understand of algorithms enabling you to understand the time and space aspects of software. You will learn how to deal with basic algorithmic problems when developing software.
Course content and goalsSpecific problems will be solved using a selection of fundamental algorithmic methods. The course will deal with the following methods:
In detail we will work with:
- Methods for sorting and searching
- Methods for finding the shortest way in a network
- Methods for compact presentation of a large amount of data
- Methods for analysing efficiency and correctness.
We will also touch on different tools for analysing e.g. proofs of correctness using invariants, asymptotic analysis and notation, amortised analysis and probabilistic analysis.
- Stacks, queues, lists, and sequences
- Priority queues, balanced search trees, and dictionaries
- Sorting and selection
- Amounts and partitioning
PrerequisitesThe course Introductory Programming at the IT-C or the like.
The courseThe course consists of weekly lectures followed by tutorials. There will be a set of mandatory excersises.
Course examWritten examination. All mandatory exercises must be handed in and accepted before the examination.