| Semester | |
| Module # | INF-ALG-10 |
| Programmes | Computer Science Bachelor, Business Information Systems Bachelor |
| IBR Group | ALG (Prof. Fekete) |
| Type | Lab |
| Lecturer | |
| Credits | 5 |
| Hours | 0+3 |
| Time & Place | This lab is structured around intensive weekly exercises that you can complete at your own pace at home. We will hold regular support sessions where you can ask questions and present your solutions. The default session time is Tuesdays at 16:45 in IZ305, though additional slots may be offered if needed. The lab runs for the first six to eight weeks of the semester, making it more time-intensive, with a workload of up to two days per week. It is followed by an optional team project. You can earn 5 credits for the lab and an additional 5 credits for the project. If multiple students choose to complete only the lab but not the team project, the schedule may be relaxed to allow for a more flexible timeframe. |
| Start | Kickoff: The Kickoff event will be on Monday, April 7th, 15:00-16:30 in IZ305. (please let me know if you cannot make it to the kickoff, and we may be able to find a solution.) |
| Prerequisites | For a successful experience in this course and to effectively work on the projects, students are expected to meet the following prerequisites:
Please ensure you meet these requirements to engage fully in the course activities. If you have any questions or need clarification on the prerequisites, feel free to reach out to us. |
| Language | German/English |
| Certificates | You have to successfully complete and present all exercises. |
| Registration | To register for this module, write a mail to krupke@ibr.cs.tu-bs.de or sign up for the mailing list. You can cancel any time. At the beginning of the semester, you will get a mail with the details for kickoff meeting. You can also just show up at the kickoff meeting, but a registration on the mailing list is still recommendable to get all updates. |
| Content | Optimization challenges are pervasive across numerous real-world applications within computer science, ranging from route planning to job scheduling. Certain problems, like the shortest path, can be solved efficiently and optimally with a solid theoretical foundation. However, a significant number of these challenges are classified as NP-hard, indicating that, for these problems, there is no known algorithm capable of consistently solving every instance efficiently to proven optimality. In such instances, heuristic approaches, such as genetic algorithms, are frequently employed as practical solutions. Yet, the question arises: Is it possible to devise algorithms that yield optimal solutions within a feasible timeframe for reasonably sized instances? This laboratory course is dedicated to exploring three sophisticated techniques that hold the potential for computing optimal solutions for a vast array of problems within practical limits. These techniques include:
For algorithm engineers and operations researchers, mastering these techniques opens the door to modeling and solving a wide spectrum of combinatorial optimization problems. By the end of this course, you will have acquired the skills to leverage these powerful methodologies, enabling you to approach NP-hard problems not only with theoretical insight but with practical, actionable solutions. |
| References |
|