IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
Kursusnavn (dansk):Foundations of Computing - Algorithms and Data Structures 
Kursusnavn (engelsk):Foundations of Computing - Algorithms and Data Structures 
Semester:Efterår 2014 
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:30 
Maks. antal deltagere:45 
Formelle forudsætninger:The course Foundations of Computing - Discrete Mathematics (SGDM) or similar.
The course Introductory Programming (GP) or similar.

-----
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. 
Læringsmål:After the course the student should be able to:

•Clearly explain how algorithms perform computations and manipulate data structures through assignments, method invocations, nested loops, and recursion, where the language of specification ranges from natural language to a concrete programming language (Java).
•Implement abstractly specified computations and data structures in an imperative programming language (Java), making use of the abstractions provided by the language.
•Analyze time and space usage of algorithms/programs, and use this to assess scalability.
•Argue for correctness of programs.
•Choose among and make use of the most important algorithms and data structures in libraries, based on knowledge of their functionality and complexity.
•Design algorithms for specialized 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, for example cache performance, and use of CPU cores. 
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 (using tilde, order-of-growth, and big-O notation), standard library algorithms and data structures for: sorting, sets, maps, and graphs, correctness arguments, algorithmic problem solving by reduction to known problems, encapsulation of abstract data structures, and hardware factors affecting performance. 
Læringsaktiviteter:12 forelæsninger og 12 øvelsesgange

The lectures cover theory and exercise provide training as to practical applying the theory.

Both theoretical reasoning as and concrete experience with applying theoretical ideas in programming are central. In particular, 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 

Obligatoriske aktivititer:During this course students will be required to hand in mandatory
assignments (solving algorithmic problems, including programming), that
need to be completed and approved before being eligible to register for the
examination. There are a total of six assignments, out of which the
students must reach an overall level of approval. 
Eksamensform og -beskrivelse:X. experimental examination form (7-scale; external exam), 7-trins-skala, Ekstern prøve

The duration of the written examination is 4 hour(s). During the written exam, students have access to any written aids that they bring on paper or installed in local computer hardware (disk, USB memory, etc.). Software use during the exam is restricted to viewing documents and editing answers. Internet communication is restricted to accessing specific servers dedicated to the exam (detailed specifications to be given). Accessing any other internet services is prohibited. For instance, web browsing, access to cloud services, use of search engines, or communicating with individuals via the internet is prohibited.

The re-examination may, in the event that the number of participating students is small, be held as an oral exam (B11) with similar restrictions during preparation time as during the written exam.  

Litteratur udover forskningsartikler:Robert Sedgewick and Kevin Wayne: Algorithms, 4th edition, Addison-Wesley, 2011.