Dansk - English
Short version - Full version
Computer Science (Fall 2012) |
|||
| Course code : | ICOMP3-U1 | ||
| ECTS Credits : | 5 | Status : | Compulsory |
| Revised : | 27/09 2011 | Written : | 29/05 2008 |
| Placement : | 3. semester | Hours per week : | 4 |
| Length : | 1 semester | Teaching Language : | English |
| Objective : | 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. Learning outcomes (i) Ability to 1. describe binary and integer and floating point presentation 2. define and identify basic data structures and algorithms 3. define and identify efficiency of a simple algorithm used with a specific data structure (ii) Ability to 1. analyse and compare advantages and disadvantages using basic algorithms together with different data structures 2. analyse and compare strength and weaknesses of basic sorting algorithms 3. analyse algorithms with respect to efficiency 4. analyse examples of 1. and 3. in the students own solution (iii) Ability to 1. discuss solutions involving items listed in the Principal Content 2. estimate efficiency of an algorithm with worst, average, and best case 3. estimate and analyse a specific solution 4. estimate and summarize efficiency measurements 5. reflect on a data structure application |
||
| Principal Content : | • • 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 |
||
| Teaching method : | The lessons consist of theory combined with practical exercises and course assignments. During the semester the student will have to hand in a number of mandatory course assignments. | ||
| Required prequisites : | Documented knowledge corresponding to PROG2. | ||
| Recommended prerequisites : | You are already competent at programming in Java. You should feel confident in design and implement programs using classes and methods. You have used some basic structures like arrays and Arraylists in Java. | ||
| Relations : | COMP3 is normally taken together with NET3 and DIST3. The project course in the third semester includes COMP3 and NET3 and DIST3. | ||
| Type of examination : | Look under remarks | ||
| External examiner : | External | ||
| Marking : | 7 step scale | ||
| Remarks : | Oral examination based on a specified project and probing of the students’ knowledge about the theoretical background. 7-step scale. Grades are defined above. 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 |
||
| Teaching material : | 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 |
||
| Responsible teacher : | Henrik Kold Mikkelsen
, hokm@dtu.dk |
||