6 ECTS credits
158 h study time
Offer 1 with catalog number 1023842BNR for all students in the 2nd semester at a (B) Bachelor - advanced level.
In the courses "Algorithms and Data sctructures", we study the algorithms and data structures every computer scientist should know. In principle, this is all indpendent of a particular programming language. We use a combination of pseudo-code (for understanding the underlying principles) and scheme (for the practical component).
CONTENT
This course covers the following subjects:
- Amortized Analysis: disjoint sets, the union-find problem
- Graphs: definition and representation using adjacency structures.
- Graph Traversals: DFS, BFS, characterization based on edge classification.
- Undirected Graph problems: connectivity, edge connectivity, biconnectivity and computing spanning forests (Prim, Kruskal, Boruvka).
- Directed Graph problems: strong connectivity, Topological Sorting DAGs, reachability and shortest paths in graphs (Bellman-Ford, Dijkstra, Floyd-Warshall, Lawler)
- Dynamic Programming
- The SAT Problem: Advanced Search Algorithms
A course text is made available on Canvas. Additional reading can be found in the book "Introduction to Algorithms" (by Cormen, Leiserson, Rivest, MIT Press, 1991).
Knowledge and Understanding: The initial goal of the course is to complete the list of algorithms and data structures that is considered common knowledge among computer scientists. Students have to be able to evaluate the algorithms and data structures studied, compare them, implement them and adjust them for concrete applications. The second goal is to expose the students to a number of highly advanced and specialised algorithms, the analysis and implementation of which largely transcends the complexity found in traditional handbooks of algorithms. For these too, students have to able to estimate performance and applicability. Furthermore, they have to understand their implementations and should be able to independently construct and analyse variants of the algorithms and data structures presented during the course.
Application of Knowledge and Understanding: Just as is the case with Algorithms and Data Structures 1, students have to be able to adapt the algorithms and data structures studied to new concrete situations. Furthermore, students should be able to design new algorithms and data structures for problems that are close to the ones studied in the course.
Making Judgements: Students should be able to evaluate and compare existing algorithms, data structures and ADT implementations. It is also expected that students can correctly judge the quality of the implementation of a data structure and/or algorithm.
Communication: Students should be able to document algorithms and data structures with sufficient precision in order to improve the communication between different developers of a big project.
The final grade is composed based on the following categories:
Oral Exam determines 50% of the final mark.
PRAC Practical Assignment determines 50% of the final mark.
Within the Oral Exam category, the following assignments need to be completed:
Within the PRAC Practical Assignment category, the following assignments need to be completed:
The exam consists of a theoretical and a practical (project or exercises) part.
The two parts have an equal weight in the final mark.
In case a grade of less than 7/20 is obtained for one of the parts, the final grade for the course equals the lowest of the two grades; otherwise, the final grade equals the average of the two grades.
Absence in one of these components implies absence for the entire course.
This offer is part of the following study plans:
Bachelor of Computer Science: Default track (only offered in Dutch)
Bachelor of Artificial Intelligence: Default track (only offered in Dutch)