IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
Kursusnavn (dansk):Grundlæggende strukturer for beregninger - Algoritmer og datastrukturer 
Kursusnavn (engelsk):Foundations of Computing - Algorithms and Data Structures 
Semester:Forår 2011 
Udbydes under:cand.it., softwareudvikling og -teknologi (sdt) 
Omfang i ECTS:7,50 
Kursussprog:Engelsk 
Kursushjemmeside:https://learnit.itu.dk 
Min. antal deltagere:12 
Forventet antal deltagere:35 
Maks. antal deltagere:50 
Formelle forudsætninger:-----
Information about the course of study
This course is mandatory for students who are enrolled on on the Master of Science in IT, study programme Software Development and Technology, Development Technology track. See a description of the track here: Kandidat Software Development Technology 
Læringsmål:After the course the student should be able to:

•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).
•Implement abstractly specified computations and data structures in an imperative programming language (Java).
•Analyze time and space usage of algorithms/programs.
•Argue for correctness of programs using invariants.
•Assess scalability of a given single-threaded software application, using asymptotic analysis.
•Choose among and make use of the most important algorithms and data structures in libraries, based on knowledge of their complexity.
•Design algorithms for ad hoc problems by using and combining known algorithms and data structures.
•Account for and describe the most important hardware and programming language factors influencing the speed at which a program runs. 
Fagligt indhold:This course serves as an introduction to data structures, algorithms and complexity for freshly educated programmers.

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. 
Læringsaktiviteter:

The lectures will cover theory and the exercise will train practical issues of applying the theory.

Emphasis is put theoretical reasoning as well as on concrete experience with applying theoretical ideas in programming. In particular, doing a number of programming exercises will be a mandatory part of the course.

-----
NB!! Course restriction I!!
Please note that there is a course restriction between this course and the SDT course Performance and Test 

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

This course has mandatory assignments (e.g. attendance, papers, exercises, presentations, productions), that need to be completed/approved before being eligible to register for the examination:
- A number of programming exercises  

Litteratur udover forskningsartikler:Foundations of Computing - Algorithms and Data Structures, Spring 2011

COURSE BOOK

Robert Sedgewick & Kevin Wayne, "Algorithms, 4th ed.", chapter 1 compendium (version of Jan 3): all contents.

Robert Sedgewick & Kevin Wayne, "Algorithms, 4th ed.", fall 2010 preliminary edition: chapter 2 except pages 164-168; all of chapter 3; 4.1, 4.2, 4.4; 5.1, 5.2, 5.5 except pages 735-741.


SUPPLEMENTARY MATERIAL

Slides from lectures

Logarithms and basic combinatorics
Elementary sorting algorithms
Amortized analysis
Generics for Sorting (2 parts)
Excerpt (pp. 75-79) from Witten, Moffat & Bell, "Managing Gigabytes", 2nd ed.


SCIENTIFIC ARTICLE

Larsson & Sadakane: Faster Suffix Sorting 
 
Afholdelse (tid og sted)
Kurset afholdes på følgende tid og sted:
UgedagTidspunktForelæsning/ØvelserStedLokale
Mandag 12.00-14.00 Forelæsning ITU 4A16
Mandag 14.00-16.00 Øvelser ITU 2A52, 4A58
Torsdag 10.00-12.00 Forelæsning ITU 2A12
Torsdag 12.00-14.00 Øvelser ITU 2A52, 2A54

Eksamen afholdes på følgende tid og sted:
EksamensdatoTidspunktEksamenstypeStedLokale
2011-06-06 09:00-11:30 (sammen med Discrete Math. til 13:30) Skriftlig eksamen ITU 3A12 og 3A14
2011-08-23 Re-exam - Please contact the course manager Skriftlig eksamen ITU 2A18 - ORAL EXAM
2011-08-23 Preparation Room Skriftlig eksamen ITU 2A03