Algorithms and Satisfiability
2024/2025
Recommended prerequisite for participation in the module
The module builds on knowledge gained from the courses: The Theoretical Basis of Computer Science, Algorithms and Data Structures as well as Syntax and Semantics.Content, progress and pedagogy of the module
Disclaimer.
This is an English translation of the module. In case of
discrepancy between the translation and the Danish version, the
Danish version of the module is valid.
Learning objectives
Knowledge
The student must gain knowledge of the following theories and methods:
- algorithm design techniques such as share-and-rule, greedy algorithms, dynamic programming, backtracking, branch-and-bound algorithms, randomized algorithms, linear programming, and approximate algorithms for solving NP-complete problems.
- techniques in advanced algorithm analysis such as amortized analysis, analysis of expected complexity and experiments with algorithms
- examples of core algorithms and data structures for solving a variety of problems from different areas of computer science such as external memory algorithms, multi-threaded algorithms, text search, advanced graph algorithms, and geometric calculations.
- satisfiability, Boolean modeling and computation, AI applications, planning and scheduling.
- binary decision charts, algorithms for this data structure and application to solve satisfiability problems
Skills
- be able to account accurately and using the subject's terminology and notation for important results within course topics and explain the principles behind the most important algorithms and compliance results
- be able to select and apply algorithm design and compliance techniques for a given problem
- be able to recognize a range of problems from different areas of computer science and select the most appropriate algorithms and data structures to solve them
Competences
- be able to apply concepts and techniques within algorithms and compliance theory
- facing a computer science problem, be able to develop and analyze efficient algorithms and data structures for solving the problem
Type of instruction
The teaching is organized in accordance with the general teaching methods for the education, cf. section 17.
Extent and expected workload
The student is expected to spend 27.5 hours per ECTS, which for this activity means 137.5 hours.
Exam
Exams
| Name of exam | Algorithms and Satisfiability |
| Type of exam | Written or oral exam |
| ECTS | 5 |
| Assessment | 7-point grading scale |
| Type of grading | Internal examination |
| Criteria of assessment | The criteria of assessment are stated in the Examination Policies and Procedures |
Additional information
Contact: Study Board for Computer Science via cs-sn@cs.aau.dk or 9940 8854
Facts about the module
| Danish title | Algoritmer og opfyldelighed |
| Module code | DSNDATB611 |
| Module type | Course |
| Duration | 1 semester |
| Semester | Spring
|
| ECTS | 5 |
| Language of instruction | Danish |
| Empty-place Scheme | Yes |
| Location of the lecture | Campus Aalborg |
| Responsible for the module |
Organisation
| Education owner | Bachelor of Science (BSc) in Computer Science |
| Study Board | Study Board of Computer Science |
| Department | Department of Computer Science |
| Faculty | The Technical Faculty of IT and Design |
