Homework #4 Solution

Problem Description

P loves complicated things. Hence, in the graph theory, cliques are P’s favorite since they are the most complex structure within all simple graphs. One day, P found a new interesting game called \click clique" on a gaming website. The rule of the game is described as follows.

When the game starts, you are given a simple undirected graph G = (V; E). For each move, you can click a clique C of G, and it will remove those vertices and edges from the graph. That is, the graph will become the induced subgraph of V nC after the move. You can make arbitrary number of moves until the graph is empty. When the game ends (i.e. the graph becomes empty), you will receive stars according to the number of moves you make. Furthermore, you can receive full 3 stars only when you make the minimum number of moves. As a clique lover, P can’t bear to miss the full stars in the game. Thus, P comes and asks you for help. Given a simple graph, please tell P an optimal way to nish the game.

Input

The rst line of the input contains an integer T indicating the number of testcases. For each testcase, the rst line contains two integers N; M indicating the number of vertices and edges in the graph, respectively. The following M lines each contains two integers u; v describing the edges of the graph.

•1    T    1000

•1    N    80
•0    M    N(N1)

2

    • 0   u; v < N

    • 1   C   800 where C is the number of maximal clique in the graph.

    • It is guaranteed that the given graph is simple.

    • Each test group will include its previous test groups.


Test Group 0 (0 %)
Test Group 3 (30 %)
• Sample Input
•T  10

• n   50
Test Group 1 (10 %)
•C  500
• n   7
Test Group 4 (40 %)
•C  800
• T   3
Test Group 2 (20 %)



• n   14

•1  C  100





2
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Output

For each testcase, the rst line output an integer R, which is the minimum number of moves P needs to make.

Then each of the following R lines output the vertices that P should click in each move in the format of \k v1 v2 : : : vk", where k is the number of vertices in this move and fvig are the indices of these vertices. You can output fvig in any order.

Note that the summation of k in each testcase should be equal to N. If there are multiple optimal solutions, you can output any of them.


Sample Input 1
Sample Input 2
Sample Input 3
1



2



2











4
2


6
6


3
3














1
2


0
1


1
2














0
2


0
2


0
2














4
6


1
2


0
1














0
1


1
3


3
0














1
2


3
4


















2
3


4
5


















0
3






















0
2










1
3






Sample Output 2
Sample Output 3









Sample Output 1
1



3



















3
2
0
1
2
0
2

3



3



1
1


3
0
1
2
1
2


1
3


1
3


1
0


1



2
4
5

1
1


4
1
2
0 3


Notes

A clique is de ned as a complete subgraph. That is, a set C V is a clique if and only if 8u; v 2 C and u 6= v, (u; v) 2 E.

A maximal clique is a clique that cannot be extended by adding any other vertex. That is, there is no proper superset of C which is also a clique. Formally speaking, a clique C is maximal if and only if @C S V such that S is a clique.

Hints

    1. std::bitset is a good data structure and it might be useful in this problem.

    2. You may want to use (integer) linear programming to solve this problem. Please see the following section to use the provided linear programming solver. (Of course, you are not forced to use it if you want to implement it by yourself.)



3
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



3. You are welcome to use any heuristic method to solve this problem. Happy hacking.

Linear Programming Solver

The GLPK (GNU Linear Programming Kit)1 package is intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems. You can include the GLPK library (<glpk.h>) and use it in this problem. See GLPK Manual2 for more information about the usage.

There is also a packed version of the GLPK tools provided for you to use it easier. The full header le can be downloaded here3. You can include it by #include "ypglpk.hpp" in your solution.
There are three functions de ned in the namespace \ypglpk". You can follow the instruction below to use them. All the std::vector below are 0-based. Note that if the parameters violate the restriction, the behavior is unde ned.



std::pair<double,std::vector<double>> linear_programming( const std::vector<std::vector<double>> &A,

const std::vector<double> &b, const std::vector<double> &c);


    • The function linear_programming(A,b,c) is used to solve the standard linear programming problem.

    • Parameters: A 2 Rm n; b 2 Rm; c 2 Rn where n is the number of structural variables and m is the number of constraints.

    • Targets: Maximize c x subject to Ax   b; x 2 Rn.

    • Return value: pair of (optimal value c x , optimal vector x ). If the solution is infeasible or unbounded, the return value is (negative in nity -ypglpk::INF, empty vector vector<double>()).



std::pair<double,std::vector<double>> mixed_integer_linear_programming( const std::vector<std::vector<double>> &A, const std::vector<double> &b, const std::vector<double> &c, const std::vector<bool> &isint);


    • The function mixed_integer_linear_programming(A,b,c,isint) is used to solve the mixed integer

linear programming problem, which can restrict some structural variables to be integers.

    • Parameters: A 2 Rm n; b 2 Rm; c 2 Rn; isint 2 ftrue; f alsegn where n is the number of structural variables and m is the number of constraints.

    • Targets: Maximize c x subject to Ax   b; x 2 Rn, and 8i with isinti = true; xi 2 Z.

    • Return value: pair of (optimal value c x , optimal vector x ). If the solution is infeasible or unbounded, the return value is (negative in nity -ypglpk::INF, empty vector vector<double>()).



void set_output(bool output);


    • https://www.gnu.org/software/glpk/

    • http://most.ccib.rutgers.edu/glpk.pdf
    • http://www.csie.ntu.edu.tw/~giver/ADA/hw4/ypglpk.hpp


4
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



    • The function set_output(output) is used to set whether GLPK to output verbose information about the (MI)LP solver.

    • The default setting is output=false. You may enable it to debug your code with more information about the constraints and the solver. However, please do not set it to true when you submit to the judge; otherwise, you will certainly get Wrong Answer verdict due to the unexpected output.



Local Testing

Here4 is a simple example code to demonstrate how to use the provided header le. It should be able to be compiled and run successfully on the judge (although you will receive Wrong Answer).

The installed GLPK version on the judge system is 5.0. (The version of the GLPK package does not a ect the correctness. It only a ects the performance in some cases since the later version might have better presolver and branching strategy.)

For CSIE students, you are highly recommended to run the program on the CSIE workstation, as there is already an installed GLPK 5.0 package for you. You can simply put your source code and the given header le together and compile them with the command below Compilation.

Otherwise, to compile and run the GLPK library successfully, please refer to the Appendix GLPK Installation to install it.


Compilation

After having an environment with installed GLPK package, you can compile the provided codes (or your source code) by adding the additional linker argument -lglpk to the compilation command. Note that the order of the arguments is essential. The linker argument should be put after the source code. For example (assume that the lename of the source code is \example.cpp"):


g++ -std=c++17 -O2 -oexample example.cpp -lglpk -Wall



Demonstration

You can try to compile and run the provided example program to ensure there is no problem with the package. Below is a script to download the provided les, compile them, and run the program. (Note that the compilation command and the execution command might di er if you built the package from source by yourself. See the Appendix GLPK Installation for more information.)


curl -o example.cpp ’https://www.csie.ntu.edu.tw/~giver/ADA/hw4/example.cpp’ curl -o ypglpk.hpp ’https://www.csie.ntu.edu.tw/~giver/ADA/hw4/ypglpk.hpp’ g++ -std=c++17 -O2 -oexample example.cpp -lglpk -Wall ./example



And the expected output of the program execution should be like    gure 1.







    • http://www.csie.ntu.edu.tw/~giver/ADA/hw4/example.cpp


5
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4


























































Sample output of the example.cpp program














6
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Problem 2 -


P


Game (Programming) (13 points)

This task has unusual time limit and submission quota. Please read the notes carefully.

Problem Description

King

P

loves to play board games. He is especially good at playing Connect4.






















Connect Four (Connect4) is a two-player connection board game in which the players take turns dropping their pieces into a seven-column, six-row vertically suspended grid. The pieces fall straight down, occupying the lowest available space within the column. The game’s objective is to be the rst to form a horizontal, vertical, or diagonal line of four with one’s pieces. The game is determined to be a tie if a player can’t make a move (i.e., the board is fully lled).

The following    gure shows an example game:
















You, as a local Connect4 champion, are invited by King P to have a series of matches with him. Since King P is a nice person, he will always let you move rst. Additionally, since King P is very busy, he can’t pay full attention to the games. Sometimes, he will make a random move instead of using his strong mind. Given these advantages, can you defeat King P?

Scoring

There are multiple test groups. In each test group, there are two parameters, a probability p and a threshold thres. For each testcase within the test group, you will play 100 games of Connect4 against King P. When it’s King P’s turn, he has a probability p to make the decision using his strong mind. Otherwise, he will make a random move (each valid column has the same chance to be chosen).

7
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Suppose that you got x wins and y ties out of all 100 games in a single testcase, your score score is de ned as 2x + y. That is, each win gives you two points, while each tie gives you a single point. You will get Accepted i score thres.


Test Group 0 (2 %)

• King    P    always drops his piece in the leftmost valid column.

    • thres = 190


Test Group 1 (8 %)    Test Group 2 (10 %)  Test Group 3 (10 %)  Test Group 4 (15 %)

• p = 0:0    • p = 0:5    • p = 0:5    • p = 0:7

• thres = 150    • thres = 120    • thres = 170    • thres = 110


Test Group 5 (15 %)    Test Group 6 (15 %)    Test Group 7 (25 %)

• p = 0:85    • p = 0:85    • p = 0:85

• thres = 110    • thres = 140    • thres = 170


Implementation details

First of all, the columns are numbered from 0 to 6. You need to implement the following procedure:


int decide(int yp_move)

In each game, decide(-1) will be called rst. You should return the rst move (index of the column) you want to make. Every subsequent call of the function denotes that King P placed his piece in column yp move. You should return the next move you want to make.


It is guaranteed that the game hasn’t nished yet when yp move 6= -1. However, there are multiple games within a single testcase. Please properly reset all your variables whenever decide(-1) is called.


Local testing tool & Template

We’ve provided a local testing tool for you. The tool will connect to our sever (so it needs network connectivity) and play against the exactly same strategy on the judge (i.e., King P). So please submit your solution to the judge only if it runs correctly at local.

Please download connect4 public.zip5, which contains the following two    les:


connect4.cpp

This is the template le for you to work on. This is also the le you should submit for this problem. You can pass Test Group 0 by submitting this le without any modi cations. You can (and should) include any header you need on your own. Feel free to use global variables.


    • http://w.csie.org/ b08902107/ADA/connect4 public.zip







8
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



connect4.h

This is the local testing tool. We already included this le in your solution. You should directly compile connect4.cpp. It’s recommended to add -std=c++17 and -O2 ag when compiling locally. For Windows users, you need to append -lws2 32 to the compiler option.


It will ask for p and the number of games you want it to repeat. It is encouraged to take a look at the tool and change it as you like. Feel free to borrow any code from the tool.

Additionally, there are two \switches" located at the very beginning of this tool:

    • CONNECT4 DEBUG: The tool will output the state of the game board if this  ag is de ned.


•    CONNECT4 INTERACTIVE: The tool will let you (instead of King P) play with your own code if this ag is de ned.


About the execution time

The local testing tool will help you measure the total time it takes to run your code on your computer (not including King P’s thinking time). King P will spend approximately 3 seconds per testcase on the judge. However, beware that the execution time might change a lot on the judge. It’s a good idea to run the same code locally and on the judge once and take the time di erence as a reference. The time limit to this problem should be more than enough.

Notes

    1. The time limit for this problem is 40 seconds per testcase (100 games). However, you can only submit 5 times per day.

    2. Do not write your own main function and do not try to interact with stdin and stdout.

    3. Feel free to use any random number generators. However, it’s encouraged to use a xed seed so that your judge verdict can be deterministic.

    4. The judge uses a xed random seed, so you should get the same verdict (Accept or Wrong Answer) if you submit the same deterministic code twice. (Note that this does not hold for local testing tool, as it uses a di erent seed for every new invocation.)

    5. Do not try to steal any data from the grader. Similar behavior will be regarded as cheating and will receive heavy penalties. If you nd weird behavior from the grading or the local test tool, please contact TA.

Hints

    1. It is important to examine why your code loses.

    2. It might be easier to debug by playing with your own code (see the instruction above on how to do this).

    3. This is an open question, we don’t have a model solution. You can use your imagination to come up with some good strategies.

    4. You can ask TAs for some additional hints if you don’t have any idea. However, we can’t really debug your ideas for you.

    5. You can also come to play with TAs if you like.


9
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Problem 3 -


P


Record (Programming) (11 points)

Problem Description

As a competitive programming athlete, P has participated in N contests, and the ith contest has a unique ID i. However, P knows that he got score si in the ith contest and feels slightly dissatis ed with those results. Due to his self-esteem, P wants to let his scores become increasing over time by concealing some of the contest records.

P, who is the travel to the past

1.
Convince
P
2.
Convince
P
Notice that
P



of other contests,


enemy ofP, would like to interfere him. Since
P
is a great time traveler, he will




and do one of the following operations many times:

to participate in an extra contest.

not to participate in a contest.

may perform the operations at any time. Any operation will not a ect the scores you don’t need to worry about the Butter y E ect.

P entrusts you, his assistant, to perform the concealment. Unfortunately, P doesn’t want to tell you the exact scores of each contest. You can only ask him many times about \whether the score of the ath contest is less than the bth contest", but not too many because P is busy. You also need to
keep updating the concealment after
P
has done any operation.







Oh,Pdoes not care about minimizing the number of concealed contests.
P
will accept any
approximate solution that is at most twice as many as the minimum.



Implementation details

Include "ada-hw4-p3.h" in the rst line of your code, and then you should implement the following procedures:


std::vector<int> init(int N)


    • N:


P


has participated in N contests initially. The ith contest’s position is i initially.

    • This procedure is called exactly once, and should return a single array D. The elements of the

returned array should form a subset of 0 to N 1 in any order, describing the IDs of contests you want to conceal. An empty array is also valid when you don’t want to conceal any contest.



std::vector<int> insert(int p, int id)


    • p: position of the inserted contest. After the insertion, the idth contest will have position p, and the original contests whose positions are greater than or equal to p will be increased by one.

    • id: the ID of the inserted contest.

    • This procedure should return a single array D. The elements of array should form a subset of the current contest ID list (after the insertion) in any order, describing the IDs of contests you want to conceal. An empty array is also valid when you don’t want to conceal any contest.



10
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4




std::vector<int> remove(int p)


    • p: position of the removed contest. After the deletion, the contest having position p will be removed, and the original contests whose positions are greater than p will be decreased by one.

    • This procedure should return a single array D. The elements of array should form a subset of the current contest ID list (after the removal) in any order, describing the IDs of contests you want to conceal. An empty array is also valid when you don’t want to conceal any contest.

The above procedures can make calls to the following procedure:


bool compare(int a, int b)


    • a: the  rst contest’s ID you want to compare.

    • b: the second contest’s ID you want to compare.

    • Both the the compared contests should exist (a removed contest is regarded as disappeared). And a 6= b.

    • The procedure returns true if the ath contest’s score is less than the bth contest’s score. Other-wise, it will return false.

    • The grading program will record the number of calls of this procedure, which is relate to the condition of getting Accepted.

    • The time complexity of the procedure is O(1).

Examples

Consider a scenario in which P has participated in 3 contests with scores [1; 4; 2], in order. The procedure init is called in the following way:


init(3)

This procedure may call compare(0, 1) which (in this scenario) returns true. It may then call compare(1, 2), which returns false.

At this point, there is su  cient information to conclude that we should conceal at least one contest.

So, the procedure init can return [2] and get Accepted.

Notice that we can return an answer having twice of the minimum answer size. Hence, if the procedure init returns [1; 2], it can also get Accepted.

After that, the procedure insert may be called in the following way:


insert(1, 3)

It means that P had convinced P to participate in the 3rd contest at position 1. Assume that the score of it is 3. The contest ID list is [0; 3; 1; 2] and the contest score list is [1; 3; 4; 2] now.

This procedure may call compare(3, 1) which returns true. At this point, there is su cient information to conclude that we can conceal only one contest. So, the procedure insert can return

    [2] and get Accepted.

11
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Continue, the procedure remove may be called in the following way:


remove(3)

At this point, there is su  cient information to conclude that we don’t need to conceal any contest.

So, the procedure remove can return [] and get Accepted.

Notice that returning any non-empty array cannot get Accepted since the minimum answer size is 0.

Constraints

Let the number of calls of insert and remove be P and Q, respectively. Then:

    • 1   N   2000

    • 0   P; Q   1000

For each call to insert, let L be the current length of the array:

    • 0   p   L

    • id = N + i  1 in the ith call of insert

For each call to remove, let L be the current length of the array:

    • 0   p < L


Test Group 0 (0 %)

    • Sample Input.



Test Group 1 (20 %)

    • No additional constraint.



Test Group 2 (20 %)

    • For the call of init, procedure compare can

be called at most N    1 times.

• P =Q=0.





Test Group 3 (30 %)

    • For the call of init, procedure compare can

be called at most N    1 times.

    • For each call of insert, procedure compare can be called at most 30 times.

    • Q=0.


Test Group 4 (30 %)

    • For the call of init, procedure compare can

be called at most N    1 times.

    • For each call of insert, procedure compare can be called at most 2 times.

    • For each call of remove, procedure compare can be called at most 2 times.










12
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Sample grader

Download "ada-hw4-p3.zip"6, extract and put them in the same directory of your code. Compile your code with the following command, assuming that your code is named ada-hw4-p3.cpp:

g++ -O2 -std=c++17 grader.cpp ada-hw4-p3.cpp -o ada-hw4-p3

We also have provided sample code (ada-hw4-p3.cpp), sample compile scripts (compile cpp.sh for Linux and Mac OS, compile cpp.bat for Windows) in the zip le.


The sample grader reads an array s of 32-bits unsigned integers indicating the scores of contests 0 to N 1 and Q operations. The sample grader reads input in the following format:

    • line 1: N Q

• line 2: s[0] s[1] : : : s[n    1]

    • line 3 + i(0   i < Q): operation[i]: could be of the following two types:

{ insert p s: Insert a contest with score s at position p. The contest’s ID will automatically become N + j 1 at the jth call of insert.

{ remove p: Remove the contest at position p.

The output of sample grader is in the following format:

    • line 1: choiceinit (t)

    • line 2 + i(0   i < Q): choicei (t)

, where:

    • choiceinit: Choice returned by init.

    • choicei: Choice returned by operation[i].

    • t: the number of calls of the procedure compare.

All of the choices will be printed in the following format:

• k c[0] c[1] : : : c[k    1]

Where k is the size of the choice and array c is the content of the choice.

Note:

    • The sample grader will not help you judge the correctness of your answer except the format error.

    • The sample grader will fail if it tries to compare two contests with the same score.




    • http://w.csie.org/ b08902103/ADA/ada-hw4-p3.zip

13
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Sample Input 1
Sample Output 1
3
2


2
1
2
(2)
1
4
2

1
2
(1)
insert 1
3
0
(0)

remove 3







Sample Input 2
Sample Output 2
3
3


3 0
1 2
(2)
3
2
1

3 0
1 2
(2)
insert 1
4
3 0
1 2
(2)
insert 2 5
1 1
(2)

remove 3






Sample Input 3
Sample Output 3
6
6




0 (5)

1
5
6
7
9
10
1 6
(1)
insert 1

8
2 7
6
(0)
insert 1

3
2 6
8
(2)
insert 6

4
2 6
8
(2)
remove 4


2 6
8
(2)
remove 7


1 6
(0)
remove 5







Hint

    1. Try to reduce this problem to the minimum vertex cover problem, which has a 2-approximation algorithm as taught in class.

    2. Do not write your own main function, and do not try to interact with stdin and stdout.

    3. Feel free to use global variables.

    4. Do not try to use complex data structures to maintain your array. Since the data size is small, you can spend linear time inserting or removing any element.

    5. All you need to return are the IDs of the contests, not the positions.

    6. For those who aren’t familiar with std::vector, take a look at the document.

    7. Do not try to steal any data from the grader. Similar behavior will be regarded as cheating and will receive heavy penalties. If you nd weird behavior from the grading, please contact TA.











14
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Problem 4 -


P


Ring (Programming) (13 points)

Problem Description

Under the rule of King P, people live from hand to mouth in the kingdom of P. In the time of crisis, people rose to rebel and used a ring to seal King P.

To ensure everyone’s safety, people decided to divide the ring into M segments and hide them at the end of the earth to prevent P from resurrecting and slaughtering the people.

This ring is decorated by N symbols, and each can be represented by a value a1; a2; ; aN , in counterclockwise order. After dividing the ring into M segments (each consisting of some consecutive symbols), we can calculate each segment’s risk value as follows.

Suppose the symbols within a segment can be represented as b1; b2; ; bk, the risk value of this segment will be

k
k  1
k
2


X
X
Xi
((bi & bi+1)  (bi+1
j bi+2)  (bi + bi+2))

bi
jbi+1   bij +
bi+1


i=1
i=1
=1



    • where x & y means applying bitwise AND operation, x j y means applying bitwise OR operation, and x y means applying bitwise XOR operation to numbers x and y.

To reduce the risk, you want to minimize the sum of the risk values of the M segments. How should you divide the M segments?

Input

The rst line contains two integers N; M, representing the number of symbols on the ring and the number of segments to be divided.

The following contains N space-separated integers a1; a2; aN , indicating the symbols on the ring.

    • 2MN1000

    • 0   ai   105

Test Group 0
(0 %)
Test Group 2 (30 %)
• Sample Input.
•N  100
Test Group 1
(20 %)
Test Group 3 (50 %)
•N  25.

• No additional constraint.

Output

Please print an integer representing the smallest sum of risk values of the M segments.






15
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Sample Input 1
Sample Output 1
5
2



14
1
2
3
4
5

Sample Input 2
Sample Output 2
5
3



10
1
2
3
4
5

Sample Input 3
Sample Output 3
5
5



15
1
2
3
4
5



Hint

    • The risk-value function has no speci c meaning and you don’t have to focus on it.

    • You can check this sample code to see how to calculate the risk value.










































16
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Problem 5 -    NPC & Reduction (Hand-Written) (30 points)

First, here present some interesting problems. The de nitions are given below:

JoJo’s Bizarre Adventure Problem (JJBAP)

Given a sequence of integers S = (a1; ; an) with cardinality n and an integer T . The JoJo’s Bizarre Adventure Problem seeks whether there is a subsequence of S whose sum equals T . This problem is known to be NP-complete.

Quintessential Quintuplets Problem (QQP)

Given a sequence of non-negative integers S = (a1;   ; an) with cardinality n and

n


i=1 ai = U.
The Quintessential Quintuplets Problem seeks whether there is a subsequence of S
whose sum equals


P

U=2.

Dragon Ball Problem (DBP)

Given a collection of n balls B with weights a1; ; an kilograms respectively, with constraint that ai 2 [0; 1], i.e., a single ball’s weight is at most 1 kilogram and at least 0 kilogram (yes, ai may be 0, to make the following problem simpler). The Dragon Ball Problem seeks to partition balls into a minimum number of bins such that all the bins weigh at most 1 kilogram.

Recall that if problem Y can be reduced to problem X in polynomial time, we denote this by
    • p X. It also means that X is at least as hard as Y because if you solve X, you solve Y . An immediate corollary is the transitivity of \ p", i.e. if Z p Y and Y p X then we will have Z p X.

Reminder: It is good to practice how to write down proofs properly. Do not use pseudocode to explain how your algorithm works. Also, keep your proof and algorithm as readable as possible. If you want to make sure whether you can get full credit with your solution, you are encouraged to contact TAs via email or discuss with TAs during TA hours.

You may assume the transitivity of \ p" and the NP-completeness of JJBAP in the following problems.
For each \show that Y    p X", please

    • Show the correctness of your reduction. In particular, if Y and X are decision problems, f is a transformation between the instances of Y and those of X, L is an instance of Y and f(L) is an instance of X, you need to show that the answer to L is \yes" if and only if the answer to f(L) is \yes".

    • Provide a polynomial-time reduction algorithm for f and brie y explain why your algorithm meets the time requirement. In particular, if f is your transformation, explain why it takes polynomial time to complete the transformation. This can be done within two sentences in the following problems. If your reduction algorithm is too complicated to explain in one or two sentences, it is probably wrong.

Here begins the problem section:

    1. (6 points) Consider a variant of JJBAP : given a sequence of non-negative integers S = (a1; ; an) with cardinality n and an integer T , and determine whether there is a subsequence of S whose sum equals T . Let’s denote this problem JJBAP+.

17
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



In fact, JJBAP and JJBAP+ are equivalent with respect to polynomial-time reduction, i.e., JJBAP+ p JJBAP and JJBAP p JJBAP+. An immediate consequence is that JJBAP+ is also NP-complete. It is straightforward to see that JJBAP+ p JJBAP . Please show the other direction.

Hint: you wish the transformed ai are all non-negative, so you can solve JJBAP by solving JJBAP+ given the transformed problem instance. Let L = (a1; ; an; T ) be an instance of JJBAP , then consider a transformation f from instances of JJBAP to those of JJBAP+, in the sense that

f(a1; a2;    ; an; T ) = (a1 + K; a2 + K;    ; an + K; K;    ; K; T + nK)

|  {z  }
n K’s

How do you choose K? And, when do you need to do the transformation? Don’t forget to justify that the answer to the problem instance L is \yes" if and only if the answer to f(L) is \yes".

More Hint: This problem is considered to be tricky. min ai is not a good enough choice for K. Absolute value and its triangle inequality may be useful for this problem.

    2. (0 points) Show that JJBAP p QQP using the result in the previous problem. Mimic the proof given in the lecture slides. This problem is just an extra exercise for you and will not be graded.

Hint: add some integers to the original problem instance.

    3. (6 points) Show that QQP p DBP . Write down the corresponding decision problem of DBP and let’s call this problem DDBP . Show that QQP p DDBP , and deduce that QQP p DBP .

    4. (3 points) Brie y explain why QQP and DBP DDBP are both NP. Deduce that QQP and DBP DDBP are NP-complete from the previous results.

5. (6 points) If P 6= N P , show that there is no polynomial time (3=2 )-approximation for DBP , where > 0 is any small positive number.


The following problems will guide you to give an example that \small additional restrictions may change a problem a lot".

We say a collection of balls B su ces (c; m)-Kuan’s rst condition if each ball in B is at least c kilogram and there are only m di erent types of weights in B for some c > 0 and m 2 N. Fix c and m, and we call the DBP problem with (c; m)-Kuan’s rst condition as (c; m)-Kuan’s DBP . Here you will show that (c; m)-Kuan’s DBP is in the complexity class P can be solved in polynomial time.

    6. (3 points) For example, there are 5 balls which weigh =4, 1/2, 1/2, 1/3, 1/4 respectively, then there are totally 9 choices of the balls to form a valid content of a single bin. The content of a single bin may be one of the following form:

        ◦ fg, i.e., it’s an empty bin.

        ◦ f =4g

        ◦ f1=2g

        ◦ f1=3g

        ◦ f1=4g

        ◦ f1=2; 1=2g

        ◦ f1=2; 1=3g


18
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



    • f1=2; 1=4g

    • f1=3; 1=4g

Note that f =4; 1=2; 1=4g, f1=2; 1=2; 1=3g and f1=2; 1=3; 1=4g are not valid contents of a single bin, since they all exceed the weight limit.

Find an upper bound of \the number of choices of the balls that form a valid content of a single bin", and represent it with m and c. Your answer should be an integer independent of n.

Hint: Consider the number of combinations. Note that there may be balls with identical weights, especially as n ! 1.
    7. (3 points) Denote the upper bound you found in the previous problem as M. Now given k indistinguishable bins, you can compute the number of ways to put all the balls inside these k

bins, denote this number k). Show that k) is bounded-above by CM kM for some CM , which is a positive constant independent of choice of k and may depend on M. You can either \justify the existence of CM " or \write down your favorite CM and simply explain why your CM meets the requirement". Again, the sum of weight of the content in any single bin should not exceed 1 kilogram.

Remark: In fact, it is equivalent to show k) = O(kM ) with respect to the variable k. If you use this fact, you also need to write down the reason why they are equivalent.

    8. (3 points) Based on the previous results, provide an O(nM+1) time algorithm for (c; m)-Kuan’s DBP , where L is some non-negative integer independent of n. Analyze the time complexity

of your algorithm and justify the asymptotic bound rigorously as you did in Homework #1. Deduce that (c; m)-Kuan’s DBP (c; m)-Kuan’s DDBP , the decision version of (c; m)-Kuan’s DBP , is in the complexity class P .





















(c; m)-Kuan’s second condition: You should go to bed at 0037














19
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Problem 6 -    Merry Christmas (Hand-Written) (20 points)

Please see the class slides for the de nition of the Traveling Salesman Problem (TSP) and what it means to have a TSP whose edge costs satisfy the triangle inequality.

In class, Ada has learned a 2-approximation algorithm using Minimum Spanning Tree (MST) algorithms to solve TSP on a graph G whose edge costs satisfy the triangle inequality. Now, Ada wants to design a better algorithm with a smaller approximation ratio. Can you help?

    1. (2pt) Describe the su  cient and necessary condition for G to contain an Eulerian cycle.

    2. (4pt) Given that T is a tree and V 0 = fvertex v with odd degree j8v 2 T g, prove that jV 0j is even.

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V; E), a perfect matching in G is a subset M of E, such that every vertex in V is adjacent to exactly one edge in M.

    3. (6pt) Let V 0 V , such that jV 0j is even, and let M be a minimum cost perfect matching on V 0. Prove that cost(M) OP T =2.(this OPT is the TSP problem’s OPT)

    4. (8pt) Given a function Oracle which can nd a minimum cost perfect matching of V in poly-nomial time, please design a 3/2-approximation algorithm to solve this problem and show that

        (a) It is 3/2-approximation.

        (b) The time complexity of your algorithm is polynomial.




































20
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



Appendix

GLPK Installation

For some common Linux distributions or MacOS (you may need to install Homebrew7 using the installation command in its o cial website) user, you may install the GLPK package from their o cial package repositories. For example:



    • Arch Linux (GLPK 5.0): sudo pacman -Syu glpk

    • Ubuntu/Debian (GLPK 4.65): sudo apt install libglpk-dev

    • MacOS (GLPK 5.0):

brew install glpk

    • Fedora/CentOS (GLPK 4.xx): sudo yum install glpk

    • or for newer version of Fedora/CentOS (GLPK 5.0): sudo dnf install glpk

Note that for MacOS users that uses GNU g++ instead of clang++ (default g++), and install the GLPK package from Homebrew, since the GNU g++ does not use the system’s library that includes the installed GLPK package, you may need to provide additional compilation arguments to specify the path to nd the GLPK package. For example, you may try to use the below compilation command (assume your g++ is GNU g++):


g++ -std=c++17 -O2 -oexample example.cpp -I /usr/local/include \ -L /usr/local/lib -lglpk -Wall

For Windows user, you may install the GLPK package from Cygwin8:

    1. Download the Cygwin installer9 and execute the installer. Below assume you install the cygwin at the default directory C:\cygwin64.

    2. Follow the default installation settings to download from an arbitrary mirror.

    3. At the package selection page, change the view to \Full" and install the following package:

        ◦ Search for g++ and select the package gcc-g++ package with version 10.2.0-1.

        ◦ Search for glpk and select both package glpk and libglpk-devel with version 5.0-1.

    4. After the installation, copy the source code and the header  le to the C:\cygwin64\home directory.

    5. Run the C:\cygwin64\Cygwin batch  le, and you should see a terminal (simple linux shell).

    6. Type ls into the terminal and you should see the  les you put in the previous step (step 4).

    7. At last, you can simply run the compilation command described above to compile your program, and run it with ./example command.


    • https://brew.sh/index_zh-tw

    • https://www.cygwin.com/

    • https://www.cygwin.com/setup-x86_64.exe


21
Algorithm Design and Analysis (NTU CSIE, Fall 2021)    Homework #4



For other Unix-based operating systems which are able to run curl, tar, gcc, g++, make commands, you can use the following script to build and install GLPK package from source:


curl -o glpk-5.0.tar.gz https://ftp.gnu.org/gnu/glpk/glpk-5.0.tar.gz tar -xzvf glpk-5.0.tar.gz && cd glpk-5.0 ./configure && make && sudo make install

    • cd to the directory that contains your source codes and the given header g++ -std=c++17 -O2 -oexample example.cpp -lglpk -Wall LD_LIBRARY_PATH=/usr/local/lib ./example

    • you can use ‘sudo make uninstall‘ command in the glpk-5.0 directory

    • to uninstall the GLPK package

Moreover, if you do not have root access (or do not want to install the package globally, you can use the following script to install it in a rootless location:


    • assume your current working directory is $HOME,

    • the glpk package will be installed at $HOME/glpk-5.0/build

curl -o glpk-5.0.tar.gz https://ftp.gnu.org/gnu/glpk/glpk-5.0.tar.gz tar -xzvf glpk-5.0.tar.gz && cd glpk-5.0

./configure --prefix=$PWD/build && make && make install

    • cd to the directory that contains your source codes and the given header g++ -std=c++17 -O2 -oexample example.cpp -I $HOME/glpk-5.0/build/include \ -L $HOME/glpk-5.0/build/lib -lglpk -Wall LD_LIBRARY_PATH=$HOME/glpk-5.0/build/lib ./example

If you still have any problem with the GLPK package or failed to compile or run the programs locally, feel free to email TAs for help as soon as possible. Besides, to let us gure out the problem sooner, please provides the environment (operating system), the problem detail you encountered, and maybe some screenshot or error message you saw when you are asking for help.































22