TU Delft
Year
print this page print this page     
NEDERLANDSENGLISH
Organization
2016/2017 Electrical Engineering, Mathematics and Computer Science Bachelor Computer Science and Engineering
TI1316
Algorithms and Data Structures
ECTS: 5
Responsible Instructor
Name E-mail
Dr. H.S. Hung    H.Hung@tudelft.nl
Dr. R.J. Krebbers    R.J.Krebbers@tudelft.nl
Instructor
Name E-mail
Dr. Y. Zhang    Yanxia.Zhang@tudelft.nl
Contact Hours / Week x/x/x/x
0/0/4/0 hc; 0/0/2/0 instr.; 0/0/4/0 lab
Education Period
3
Start Education
3
Exam Period
3
5
Course Language
English
Expected prior knowledge
Java programming
Course Contents
Algorithms and data structures are fundamental notions in computer science . Understanding how they can be exploited in combination for better programming implementations in terms of time and space complexity is vital for writing efficient code.This course enables the student to:

Understand, explain, and implement standard data structures.
Understand, explain, and implement standard algorithms.
Apply standard data structures and algorithms to solve programming tasks.
Analyse and compare implementations with respect to their time and space complexity.
Understand, explain, and apply standard programming techniques in the context of standard data structures.
Study Goals
1. Data Structures

- data containers
-- vector
-- list
-- tree
-- set
- ordered data structures
-- stack
-- queue
-- priority queue
-- heap
-- map
- operations on data structures
-- iterative implementations
-- recursive implementations

The student can explain essential data structures, explain and analyse the core properties of these data structures, and explain, develop, and adopt iterative and recursive implementations of operations on these data structures, and analyse and compare space and time complexity of these operations.

2. Sorting

- selection sort
- insertion sort
- heap sort
- merge sort
- quick sort
- bucket sort
- radix sort

The student can explain and implement various sorting algorithms, analyse and compare space and time complexity of these algorithms, and choose sorting algorithms for different problem scenarios.

3. Searching

- search structures
-- search trees
-- AVL trees
-- Splay trees
-- (2, 4) trees
- backtracking

The student can explain data structures which support efficient search and their invariants, explain, develop, and adopt implementations of operations on these data structures, analyse and compare space and time complexity of these operations, choose search structures for different problem scenarios, and explain, implement, and analyse backtracking algorithms.

4. Graphs and Graph Algorithms

- graph data structures
-- directed graphs
-- undirected graphs
-- weights
-- representations
- graph algorithms
-- graph traversals
-- path finding
-- cycle finding
-- connectivity
-- topological ordering
-- shortest path
-- minimum spanning tree

The student can explain various kinds of graphs, explain, analyse and compare different data structures for graphs, explain, develop and adopt implementations of operations on these data structures, analyse and compare space and time complexity of these operations, choose graph data structures for different problem scenarios, explain, implement, apply and analyse generic graph traversal strategies, and explain, develop and adopt implementations of various graph algorithms.
Education Method
1. Lectures (7w x 2c/w x 2h/c)

In the lectures, new data structures and algorithms are introduced by discussing example applications, their specifications, different implementations, and underlying basic theories.

2. Practicals (7w x 4h/w)

In the weekly lab assignments, students implement and analyse basic data structures and algorithms. Each lab assignment comes with several public tests as well as hidden specification tests. Students can rely on the public tests to improve their solution, while the specification tests indicate whether their solution is sufficient.
Literature and Study Materials
Datastructures and Algorithms in Java, M.Goodrich & R.Tamassia, ISBN 978-1118771334
Books
Datastructures and Algorithms in Java, M.Goodrich & R.Tamassia, ISBN 978-1118771334
Prerequisites
TI1206
Assessment
1. In the computer-based lab assignments, students need to implement and analyse various data structures and algorithms.

Assignments must be submitted weekly. Each student has 5 late days to use during the course. Each student can only use one late day per week. Late days are not used in the case of severe and provable sickness. This will only be considered if the sickness is reported in the first week of sickness via the course email address: TI1316-EWI@tudelft.nl with the heading [Reporting Sickness for Week X].

Each late day constitutes a 24-hour extension; students cannot split late days into smaller increments. Once a student runs out of late days, any further late submission results in failing the course.

All actual, detailed work on assignments must be individual work. Students are encouraged to discuss assignments, the Java programming language, its libraries, and general solution techniques with each other. If students do so, they must acknowledge those people in their submission.
Students should not look for assignment solutions elsewhere; but if material is taken from elsewhere, then its source must be acknowledged in the submission.
Students are not permitted to provide or receive any kind of solutions of assignments. This includes partial, incomplete, or erroneous solutions.
Students are also not permitted to provide or receive programming help from people other than the teaching assistants, PhD students associated with this course, or the course instructors.
Any violation of these rules will be reported as a suspected case of fraud to the Board of Examiners and handled according to the EEMCS Faculty's fraud procedure.

The contribution of each assessment type to your final grade is summarised below:

* A: Weekly Analysis Assignments 10% - grading will be based on the best 7 assignments out of 8
Weekly Implementation Assignments pass/fail - to pass, your implementations have to pass ALL specification tests.
* M: Mid Term Exam 20%
* F: Final Exam 70%
* R: Resit Exam this constitutes a second chance for either M, F or both; see final grade calculation below
* Final Grade: Maximum of { M(20%)+F(70%)+A(10%), R(90%)+A(10%), M(20%)+R(70%)+A(10%) }

IMPORTANT: To take the final exam, all assignments must be passed. Failure to pass the assignments constitutes course failure. Under special circumstances, exceptions to these rules can only be given in coordination with TU Delft study advisors.
Permitted Materials during Tests
During all exams, students are allowed to use any version of the course text book on algorithms and data structures, excluding all electronic media devices. Photocopies of the course textbook are permitted. Highlighting and small hand written notes inside the book are permitted but not extensive experts of code or calculations.
Tags
Algoritmics
Programming
Programming concepts
Judgement
The contribution of each assessment type to your final grade is summarised below:

* A: Weekly Analysis Assignments 10% - grading will be based on the best 7 assignments out of 8
Weekly Implementation Assignments pass/fail - to pass, your implementations have to pass ALL specification tests.
* M: Mid Term Exam 20%
* F: Final Exam 70%
* R: Resit Exam this constitutes a second chance for either M, F or both; see final grade calculation below
* Final Grade: Maximum of { M(20%)+F(70%)+A(10%), R(90%)+A(10%), M(20%)+R(70%)+A(10%) }

IMPORTANT: To take the final exam, all assignments must be passed. Failure to pass the assignments constitutes course failure. Under special circumstances, exceptions to these rules can only be given in coordination with TU Delft study advisors.