Overordnede kursusmål:

Through this course the student will
Know about well-known data structures as those listed below. You will be able to implement these structures.
• Be able to analyse algorithms with respect to efficiency
• Determine which structures are appropriate in various situations
• Be confident in learning new structures beyond what’s presented during this course
• Even more important the fundamental knowledge of data structures transcends to any language or operating system. Twenty years from now you will still be using the data structures that you learn this semester.

Evaluation (ref. learning out-comes)
02: if the student fulfils the criteria from (1 -3)
7: if further the criteria from (4 - 7) are met
12: if all criteria from (1 - 12) are met

Læringsmål:

En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• Ability to describe binary numbers, integer and floating point presentation
• Ability to define and identify basic data structures and algorithms
• Ability to define and identify efficiency of a simple algorithm used with a specific data structure
• Ability to analyse and compare advantages and disadvantages using basic algorithms together with different data structures
• Ability to analyse and compare strength and weaknesses of basic sorting algorithms
• Ability to analyse algorithms with respect to efficiency
• Ability to analyse examples of 4. and 5. in the students own solution
• Ability to discuss solutions involving items listed in the Principal Content
• Ability to estimate efficiency of an algorithm with worst, average, and best case
• Ability to estimate and analyse a specific solution
• Ability to estimate and summarize efficiency measurements
• Ability to reflect on a data structure application

Kursusindhold:

• Binary notations, storing integers and fractions
• Precondition and post condition specifications
• Time analysis strategies
• Algorithms and their efficiency
• Dynamic arrays
• Linked lists
• Iterators
• Stacks and queues
• Recursive thinking
• Set and maps
• Hash tables and hash functions
• Heap structures; priority queues
• Graphs; traversing graphs
• Spanning trees; shortest path
• Searching and sorting techniques

Litteraturhenvisninger:

Notes and slides
Text books:
Michael T. Goodrich: “Data Structures & Algorithms in Java”
ISBN:
Koffman & Wolfgang: “Data Structures, Abstraction and Design Using Java”
ISBN: 978-0-470-12870-1

Bemærkninger:

Oral examination based on a specified project and probing of the students’ knowledge about the theoretical background.
Through the course the students will have to solve a number of compulsory course assignments. To be admitted for examination all compulsory assignments have to be handed in within the time limits indicated in the assignment. Furthermore all assignments have to be approved

Kursusansvarlig:

Henrik Kold Mikkelsen , Ballerup Campus, rum X 1.75, Tlf. (+45) 3588 5153 , hokm@dtu.dk
Roger Munck-Fairwood , Ballerup Campus, rum X 1.49, Tlf. (+45) 3588 5188 , romu@dtu.dk
Christen Monberg , chrmo@dtu.dk