|Kursusnavn (dansk):||Grundlæggende strukturer for beregninger - Algoritmer og datastrukturer |
|Kursusnavn (engelsk):||Foundations of Computing - Algorithms and Data Structures |
|Semester:||Efterår 2010 |
|Udbydes under:||cand.it., softwareudvikling og -teknologi (sdt) |
|Omfang i ECTS:||7,50 |
|Min. antal deltagere:||0 |
|Forventet antal deltagere:||12 |
|Maks. antal deltagere:||80 |
|Formelle forudsætninger:|| |
|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.
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.
This course is mandatory for students enrolled in the Development Technology track on SDT. Find the track described here:
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:||A2: Skriftlig eksamen med alle skriftlige og trykte hjælpemidler, 7-trins-skala, Ekstern censur|
Students need to hand in 3 mandatory assignments before December 3 2010 in order to be eligible for the exam.
|Litteratur udover forskningsartikler:|| Bundle of Algorithms in Java, Parts 1-5: Fundamdentals, Data Structures, Sorting, Searching, and Graph Algorithms –3rd Edition.
By Robert Sedgewick