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
• Bin. Heap structures; priority queues; Fibonacci Heaps
• Graphs; traversing graph
• Spanning trees; shortest path
• Searching and sorting techniques
• Dynamic Programming

Litteraturhenvisninger:

Notes and slides
Recommended literature:
Michael T. Goodrich: “Data Structures & Algorithms in Java”
ISBN:
Other titles of interest:
Frank M Carrano: “Data Structures and Abstractions with Java”
ISBN: 0-13-204367-x

Bemærkninger:

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.
Oral examination. Questions will be based on the course assignment. Moreover general questions to the topics of the principal content will be raised

Kursusansvarlig:

Henrik Kold Mikkelsen , Ballerup Campus, rum X 1.75, Tlf. (+45) 3588 5153 , hokm@dtu.dk