IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
Kursusnavn (dansk):Algoritmer og datastrukturer - B.Sc.-kursus 
Kursusnavn (engelsk):Algorithms and Data Structures - B.Sc. course 
Semester:Forår 2009 
Udbydes under:Bachelor i softwareudvikling (bswu) 
Omfang i ECTS:7,50 
Kursussprog:Engelsk 
Kursushjemmeside:https://learnit.itu.dk 
Min. antal deltagere:
Forventet antal deltagere:42 
Maks. antal deltagere:42 
Formelle forudsætninger:Basic ability to program in some imperative programming language (Java, Python, C/C++/C#, etc.), using conditions, loops, arrays, methods/procedures/functions, simple recursion and abstract data types (interfaces). This is normally obtained by following the first semester undergraduate course Grundlæggende Programmering (GPP).

Knowledge of basic mathematical concepts like: sets, functions, graphs, and trees, arithmetic and geometric series. You are expected to know this from your high school education. We will make up for any lacks in that respect on the way. 
Læringsmål:This course builds on your prior knowledge of programming. It will train you in designing efficient and correct programs, while giving you basic algorithmic tools indispensible for every software developer.

After the course you should:

  • Be able to understand and clearly explain the mechanics of computations and data structures involving manipulation of references, nested loops and recursion, specified in natural language, in abstract pseudocode or in concrete programming language (Java).

  • Be able to implement abstractly specified computations and data structures in an imperative programming language (Java).

  • Be able to analyze time and space usage of algorithms/programs.

  • Be able to argue for correctness of programs using invariants.

  • Be able to assess scalability of a given single-threaded software application, using asymptotic analysis.

  • Be able to choose among and make use of the most important algorithms and data structures in libraries, based on knowledge of their complexity.

  • Be able to design algorithms for ad hoc problems by using and combining known algorithms and data structures.

  • Know about the most important hardware and programming language factors influencing the speed at which a program runs.

 
Fagligt indhold:The course will be taught in a series lectures with associated exercise classes. Topics covered are among others complexity analysis, big-O, correctness (loop invariants, assertions), algorithmic problem solving techniques including divide-and-conquer, concrete algorithms and data structures for search trees, sorting, hashing, graphs, shortest paths. The lectures will cover theory and the exercise will train practical issues of applying the theory.  
Læringsaktiviteter:

12 lecture series + 12 exercise sessions

We will spend 6 hours a week on lectures and exercises for the first 12 weeks of the semester.

You are expected to work systematically. The course gives plenty of opportunities to gain hands-on experience with solving problems, with implementing algorithms and with using them. This is arranged around guided exercise sessions, and graded weekly hand-ins (both homeworks and in class progress tests).

The textbook and lectures are in English, but written work and the exam can be delivered in Danish.
--------------------

Se hvordan undervisningen er tilrettelagt her:
link til skemaoplysninger
Skemaoplysningerne for forårssemesteret vil være tilgængelige fra kort før semesterstart.

See the schedule here:
link to the time table
The schedule for the spring term will be available shortly before the beginning of the term.
 

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

The course contains many small assignments, a larger mid-term test, and one programming assignment.
All these are graded.
In order to be admitted to the exam you have to obtain at least 60% of total points throughout the semester, observing the deadlines announced at the course website.

The grade given at the exam is independent of the grades obtained for the assignments on the course.  

Litteratur udover forskningsartikler:Goodrich, Michael T. and Tamassia, Roberto: Algorithm Design. Wiley 2002.  
 
Afholdelse (tid og sted)
Kurset afholdes på følgende tid og sted:
UgedagTidspunktForelæsning/ØvelserStedLokale
Torsdag 09.00-12.00 Forelæsning ITU 3A14, 4A44, 4A46, 4A62
Torsdag 13.00-15.00 Øvelser ITU Aud. 4, 4A44, 4A46, 4A62

Eksamen afholdes på følgende tid og sted:
EksamensdatoTidspunktEksamenstypeStedLokale
2009-06-02 09.00-13.00 Skriftlig eksamen ITU 2A18, 2A20, 3A18