IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
Kursusnavn (dansk):Introduktion til algoritmik og datastrukturer 
Kursusnavn (engelsk):Introduction to Algorithms and Data Structures 
Semester:Forår 2006 
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:35 
Maks. antal deltagere:140 
Formelle forudsætninger:Basic ability to program in some imperative programming language (Java, JavaScript, php, perl, python, C/C++/C#, etc), using conditions, loops, arrays, methods/procedures/functions, and simple recursion. This may be obtained by following GP or IPBR.

Knowledge of basic mathematical concepts like: sets, functions, graphs, and trees. These can be refreshed by following a non-obligatory lecture, given in the beginning of the semester for all course participants expressing interest. More information below. 
Læringsmål:The goal of this course is to familiarize you with the essence of the art of computer programming: design and analysis of algorithms, so that you
  • Understand and can describe basic data structures, algorithms and programming design techniques.
  • Clearly distinguish problems and their properties from algorithms (solutions) and their properties.
  • Can apply the techniques from the course when solving programming/algorithm problems occurring in the industry.
  • Are able to extract an algorithmic problem from a practical programming task.
  • Can choose a suitable algorithm and/or data structure for a given programming problem.
  • Are able to analyse time and space required for the execution of a program, as well as the correctness of a program.
  • Are able to combine and modify algorithms and data structures, in order to design an efficient program.
This course provides the algorithmic competences required by advanced courses such as "Advanced Algorithms" and "Advanced Database Technology".  
Fagligt indhold:This course is a must have for anyone who wants to become a good programmer. It provides you with a toolbox of highly relevant techniques for solving common, as well as many specialized, programming problems. The techniques we discuss are known to stand well the trial of time: they are vastly independent of programming languages, paradigms being currently in fashion, or hardware available.

The course takes its cue from different realistic applications such like: organizing and querying massive data sets (like in databases and search engines), alignment of DNA sequences in genetics, route planning (map servers like krak.dk, GPS devices, logistics systems), and implementation of programming languages and language processors.

Instead of investigating all the application domains in depth (which would be impossible in a course of 12 lectures) we extract the essential core of each task: the abstract computational problem. We observe that many even apparently distant applications, involve the same abstract problem. We propose a solution for it in a form of an algorithm or a data structure. For some classes of problems we discuss general techniques that can be used to design a tailored algorithm.

In particular we discuss the following data structures: heaps, priority queues, balanced search trees, hash tables, and graphs. Algorithms include: algorithms for sorting and searching data (including Merge-Sort, Quick-Sort, Heap-Sort and Bucket-Sort), tree traversal algorithms, graph algorithms (exploration, spanning-tree construction, shortest-path finding such as Dijkstra or Bellman-Ford), optimization algorithms for some scheduling problems. The generic techniques we use are: recursion, tail-recursion elimination, divide&conquer, dynamic programming and memoization.

Last but not least, we introduce rigorous frameworks for analysis of correctness and efficiency (time and space usage) of algorithms. These include both basic techniques (like big-Oh notation and invariants) as well as advanced methods: amortized analysis, lower bound complexity proofs and (fragments of) randomized analysis. 
Læringsaktiviteter:12 forelæsninger og 12 øvelsesgange

The main emphasis is put on practical skills. More than 70% of the time is devoted to hands-on experience with solving actual algorithmic problems, during lectures, exercises, programing assignments, and homework.

Bi-weekly mandatory hand-ins, containing exam like questions, are graded and supplemented with personalized feedback. There will be a programming contest, to let you see how you compare to the other participants. The author of the fastest program wins fame and a valuable prize!

There is an opportunity to refresh knowledge of basic mathematical concepts during a non-obligatory primer lecture in the beginning of the semester. Although the primer is not part of our curriculum, it gives you a chance to start the course more gently. Time and place for the lecture will be negotiated during the first lecture.

Exam admission requirements: there are 5 mandatory hand-ins, each graded with 0 to 100 points. One has to achieve at least 70% of all the points in order to qualify for the exam.

NB! In the introductory week from 30 January to 3 February 2006 there will be only lectures from 9:00 to 12:00 (no exercises). 

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

 

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 2A14
Onsdag 13.00-16.00 Øvelser ITU 2A14

Eksamen afholdes på følgende tid og sted:
EksamensdatoTidspunktEksamenstypeStedLokale
2006-06-07 9-13 Skriftlig eksamen ITU See examination plan in Study Guide on the Intranet