Introduction Welcome to your last programming assignment of the Advanced Algorithms and Complexity class! In this programming assignment, you will be practicing solving NP-complete problems. Of course, currently we don’t know efficient algorithms for solving these problems, but in some special cases there are efficient algorithms, and for some problems there are algorithms exponentially more efficient than the brute-force approach, although they still have exponential running time themselves.
Learning Outcomes Upon completing this programming assignment you will be able to: 1. design a part of integrated circuit; 2. plan a totally cool party; 3. find the optimal route for a school bus; 4. reschedule the exams.
Passing Criteria: 2 out of 4 Passing thisprogramming assignmentrequires passingat least2out of4code problemsfrom thisassignment. In turn, passing a code problem requires implementing a solution that passes all the tests for this problem in the grader and does so under the time and memory limits specified in the problem statement.
Contents 1 Problem: Integrated Circuit Design 3
2 Problem: Plan a Fun Party 5
3 Problem: School Bus 8
4 Advanced Problem: Reschedule the Exams 11
5 General Instructions and Recommendations on Solving Algorithmic Problems 14 5.1 Reading the Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.2 Designing an Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.3 Implementing Your Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.4 Compiling Your Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.5 Testing Your Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.6 Submitting Your Program to the Grading System . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.7 Debugging and Stress Testing Your Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6 Frequently Asked Questions 17 6.1 I submit the program, but nothing happens. Why? . . . . . . . . . . . . . . . . . . . . . . . . 17 6.2 I submit the solution only for one problem, but all the problems in the assignment are graded. Why? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.3 What are the possible grading outcomes, and how to read them? . . . . . . . . . . . . . . . . 17 6.4 How to understand why my program fails and to fix it? . . . . . . . . . . . . . . . . . . . . . 18 6.5 Why do you hide the test on which my program fails? . . . . . . . . . . . . . . . . . . . . . . 18 6.6 My solution does not pass the tests? May I post it in the forum and ask for a help? . . . . . 19 6.7 My implementation always fails in the grader, though I already tested and stress tested it a lot. Would not it be better if you give me a solution to this problem or at least the test cases that you use? I will then be able to fix my code and will learn how to avoid making mistakes. Otherwise, I do not feel that I learn anything from solving this problem. I am just stuck. . . 19
1 Problem: Integrated Circuit Design Problem Introduction
In this problem, you will determine how to connect the modules of an integrated circuit with wires so that all the wires can be routed on the same layer of the circuit.