IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
Kursusnavn (dansk):Introduktion til algoritmik og datastrukturer 
Kursusnavn (engelsk):Introduction to Algorithms and Data Structures 
Semester:Efterår 2005 
Udbydes under:cand. it, softwareudvikling (swu) 
Omfang i ECTS:7,50 
Kursussprog:Engelsk 
Kursushjemmeside:https://learnit.itu.dk 
Min. antal deltagere:0 
Forventet antal deltagere:30 
Maks. antal deltagere:140 
Formelle forudsætninger:Basic knowledge of programming in any imperative programming language, such as Java, C, C++, or C#. You should be able to write programs involving conditions, loops, arrays, methods/procedures/functions, and recursion. This can be obtained by following the course Introductory programming (GP) or Introduction to Programming - Concepts and Tools (IPBR).

Knowledge of the following basic mathematical concepts: sets, relations, functions, graphs, and trees. This can be aquired by following a lecture, given one week before the course starts. (More information below, see 'Format of Course'/'Kursusform (yderligere oplysninger)'.)
 
Læringsmål:The goal of the course is to give the student a basic understanding of fundamental algorithms and data structures so that the student:
  • Is able to describe the basic data structures, algorithms and programming techniques, including lists, stack, queues, search trees, hash tables, different sorting algorithms, search algorithms for graphs, and dynamic programming.
  • Can apply the techniques from the course when solving programming/algorithm problems. These techniques include methods for sorting and searching, basic graph algorithms, recursion, dynamic programming, and time and space analysis of programs, both basic techniques and amortized analysis.
  • Is able to select the best algorithm and/or data structure when solving a given programming problem.
  • Is able to analyse time and space required for the execution of a program, as well as the correctness of a program.
  • Is able to formulate a given programming task as an algorithmic problem, in order to select the best method for solving it.
  • Is able to combine and modify algorithms and data structures, in order to design an efficient program.


All in all this course teaches you how to write fast programs, how to design them, and how to analys them.

After the course the student has the algorithmic competences required to meet the prerequisites for advanced courses such as "Advanced Algorithms", "Programming Languages, Interpreters, and Compilers", and "Advanced Database Technology".
 
Fagligt indhold:This course is a "must have"-course, for anyone who wants to become a good programmer. The course will provide the students with a toolbox of highly relevant techniques for solving common, as well as many specialized, programming problems.

The course takes its cue from different problems, which will be solved by using selected basic algorithm/advanced programming techniques. Subjects which we will cover:
  • Methods to sort and search, including Merge sort, Quick sort, balanced search trees, and hashing.
  • Methods to find a shortest path in a graph, such as Bellman-Ford and Dijkstras algorithms.
  • Methods to store large data sets for efficient access and manipulation, e.g. Union-Find data structures.
  • Methods to analyse how time/space efficient a program is, including Big-Oh analysis.
  • Methods to use recursion in programming.
  • Programming methods like dynamic programming.
This will include e.g.:
  • Stacks, queues, sequence, trees.
  • Priority queues, search trees, dictionaries.
  • Graph algorithms.
We will also look at different tools to analyse programs, such as invariants to prove correctness, and asymptotic analysis to calculate time and space needed for a program.
 
Læringsaktiviteter:12 forelæsninger og 12 øvelsesgange

Lectures, exercises, and weekly mandatory hand-ins.

There will be a programming contest. Fastest program wins a price!

There is an opportunity to refresh your basics of mathematics during a non-obligatory primer lecture offered in the week preceeding the introduction week. The primer is not part of the course curriculum, but gives you a chance to start the course more gently. We recommend all students to attend the primer, unless you already are familiar with the concepts: sets, relations, functions, graphs, and trees.

Time and place for the lecture will be annonced on the course homepage.

NB! In the introductory week, meaning from 29 August to 2 September 2005, exercises from 13:00 to 16:00 are cancelled. This means, that there will be only lectures from 9:00 to 12:00.
 

Eksamensform og -beskrivelse:X. experimental examination form (7-scale; external exam), 13-skala, Ekstern censur

Hand-ins are graded, and students must achieve 70% of the maximum possible point sum to qualify for the exam.  

Litteratur udover forskningsartikler:Cormen, Leiserson, Rivest & Stein: Introduction to Algorithms, Second Edition, The MIT Press, ISBN 0-262-03293-7.
 
 
Afholdelse (tid og sted)
Kurset afholdes på følgende tid og sted:
UgedagTidspunktForelæsning/ØvelserStedLokale
Onsdag 09.00-12.00 Forelæsning ITU 4A14
Onsdag 13.00-16.00 Øvelser ITU 2A14

Eksamen afholdes på følgende tid og sted:
EksamensdatoTidspunktEksamenstypeStedLokale
2006-01-11 9.00-13.00 Skriftlig eksamen ITU se eksamensplan i studiehåndbogen på ITUs intranet