6 ECTS credits
165 h study time
Offer 2 with catalog number 2020074BNR for all students in the 1st and 2nd semester at a (B) Bachelor - advanced level.
PREREQUISITES:
In the course series "Algorithms and Data Structures 1&2", a number of algorithms is presented that belong to the basic vocabulary of a computer scientist. In principle, the algorithms and data structures are independent of any specific programming language. We use a combination of Pseudo-code and Scheme to illustrate the algorithms.
CONTENTS:
This course covers the following subjects:
- The memory hierarchy, internal memory, external memory, kinds of files, caching
- External data structures: Storage, Indexing and B-trees on disk
- External algorithms : external sorting (multiway merge sort, polyphase sort)
- 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 made available on the learning platform. Additional reading can be found in the books "Introduction to Algorithms" (by Cormen, Leiserson, Rivest, MIT Press, 1991) and "Database System Implementation" (by Garcia-Molina, Ullman, Widom; Prentice-Hall, 2000).
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. Both parts have an equal weight in the final mark. Absence in one of these components implies absence for the entire course.
This offer is part of the following study plans:
Bridging Programme Master of Science in Applied Sciences and Engineering: Computer Science: Standaard traject (only offered in Dutch)
Bridging Programme Master of Science in Applied Computer Science: Standaard traject (only offered in Dutch)
Preparatory Programme Master of Science in Applied Sciences and Engineering: Computer Science: Standaard traject (only offered in Dutch)
Preparatory Programme Master of Science in Applied Computer Science: Enkel voor studenten industriële wetenschappen (only offered in Dutch)
Preparatory Programme Master of Science in Applied Computer Science: Preparatory programme Toegepaste Informatica (only offered in Dutch)