Note: those marked with an asterisk I am not 100% confident in my answer/reasoning.
Please feel free to discuss the problems and my proposed solutions below!
Quiz
P1
NP-Complete problems are either all not solvable in polynomial time, or all solvable in polynomial time. There is no way for there to be some NP-Complete problems to be polynomial-time solvable.
P2
TSP1 reduces to TSP2 and HAM1 reduces to HAM2. As such, if either TSP2 or HAM2 are polynomial-time solvable, then so are TSP1 and HAM1 respectively.
P3
If cycles are allowed when finding the shortest path between s and t with exactly n-1 edges, then a polynomial-time solvable algorithm, such as a Bellman-Ford recurrence, can be used.
P4
Vertex covers and independent sets are complements of each other. If you can solve one in O(T(n)), then so can the other. So all three statements are true.
P5
Deleting a vertex of a TSP represented by nodes whose edges are the euclidean distances between the nodes cannot increase the cost of the optimal tour. Since the edges are euclidean distances, they’ll all be nonnegative. Removing a vertex will result in one less vertex to visit and so the total distance of the optimal tour can only get smaller.
Programming Assignment
For this assignment we need to solve the “Traveling Sales-man Problem”, more specifically for a graph of 25 points:
An exponential, though better than pure brute force, algorithm using dynammic programming was presented in lecture:
To see how good/bad the algorithm was, I implemented it exactly as presented in c++. Here it is below:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
void solvePart4Week2Q1(){
//Open up file of data point data
string filename = "/home/nathan/Programming/OSSU/Core_Theory/"
"Algorithms-Roughgarden/Part4/Week2/tsp.txt";
ifstream infile(filename);
string line;
//read in number of nodes
getline(infile, line);
int numberOfNodes = stoi(line);
//Array of data points
vector<dataPoint*> V;
double x,y;
int id = 0;
//Read in data point values and store in V.
while (getline(infile, line)){
vector<string> coors = split(line, ' ');
x = std::stod(coors[0]);
y = std::stod(coors[1]);
V.push_back(new dataPoint(id, x, y));
id++;
}
cout << setprecision(4) << fixed;
cout << "Size of V: " << V.size() << " Expected: " << numberOfNodes << endl;
cout << V[0]->getX() << ' ' << V[0]->getY() << endl;
//Create Subsets of V that contain 1, mapped by length of subset.
map< int, vector<vector<dataPoint*>>> subsets = generateChoicesOfS(V);
cout << "finished making sets" << endl;
//Create mappings from subsets to corresponding index values of Subset by
//Destination 2D array, A, which is initialized soon hereafter.
unsigned int c = 0;
//for quickest lookup of subset index, via subset pointer.
map<vector<dataPoint*>*, int> subsetIndexing;
//for finding index of a difference of two subsets, much slower lookup
//differences are not easily mapped to a subset pointer (though a mapping
//could probably be made...)
map<vector<dataPoint*>, int> diffIndexing;
for (int m = 1; m <= numberOfNodes; m++){
for (auto& s : subsets[m]){
subsetIndexing[&s] = c;
diffIndexing[s] = c++;
}
}
cout << c << endl;
cout << "finished making subset to array index map, "
"now initializing 2D array...." << endl;
vector<vector<double>> A;
vector<double> t;
//Initialize A[{1},1] to 0, all other A[S, 1] to +infinity,
//where S is in subsets.
for (int i = 0; i < c; i++){
t.clear();
for (int j = 0; j < numberOfNodes; j++){
if (i == 0 && j == 0)
t.push_back(0);
else
t.push_back(INT32_MAX);
}
A.push_back(t);
}
//Initialize A[{1,x}, x] to C_1x as well.
for (auto& subsetOfSize2 : subsets[2])
A[ subsetIndexing[ &subsetOfSize2 ] ][ subsetOfSize2[1]->getID() ]
= subsetOfSize2[0]->distance(*subsetOfSize2[1]);
cout << "Finished initializing A, now running the dynamic programming "
"algorithm..." << endl;
vector<dataPoint*> diff;
int subsetIndex, diffIndex;
//cycle through m = 2,3,4,...., n
for (int m = 3; m <= numberOfNodes; m++){
cout << m << "..." << endl;
//cycle through each subset S ⊆ {1,2,3,...,n} of size m and containing 1
for (auto& S : subsets[m]){
//cycle through j in S, skipping j = 1:
for (int j = 1; j < S.size(); j++){
//cycle through k in S...
for (int k = 1; k < S.size(); k++){
//... skipping k = j (since j = 1 was skipped above,
//k = 1 will be implicitly skipped as well):
if ( j != k){
diff = S;
diff.erase(diff.begin() + j);
subsetIndex = subsetIndexing [ &S ];
diffIndex = diffIndexing [ diff ];
//A[S, j] = min(A[S, j], A[S-{j}, k] + C_kj)
//note: C_kj is distance from k to j.
A[ subsetIndex ][ S[j]->getID() ]
= min( A[ subsetIndex ][ S[j]->getID() ],
A[ diffIndex ][ S[k]->getID() ]
+ S[k]->distance(*S[j]));
}
}
}
}
}
cout << "Finished the dynamic programming algorithm,"
" now searching for min value..." << endl;
//initialize result to max value
int result = INT32_MAX;
//cycle through j = 2,3,...,n
for (int j = 1; j < numberOfNodes; j++){
//result = min(result, A[V, j] + C_j1])
result = min(result, (int)(A[c-1][j] + V[j]->distance(*V[0])));
}
//print result
cout << "Answer: " << result << endl;
}
I created a quick dataPoint data structure for handling the data and computing euclidean distances between points:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/******************************************************************************/
/******************************************************************************/
/* dataPoint Header */
/******************************************************************************/
/******************************************************************************/
#include <math.h>
class dataPoint {
public:
dataPoint(int id, double x, double y);
dataPoint(const dataPoint& d):dataPoint(d.getID(), d.getX(), d.getY()){}
double distance(dataPoint other);
int getID() const;
double getX() const;
double getY() const;
bool operator==(const dataPoint& other);
private:
const int ID;
const double X, Y;
};
/******************************************************************************/
/******************************************************************************/
/* dataPoint Implementation */
/******************************************************************************/
/******************************************************************************/
dataPoint::dataPoint(int id, double x, double y) : ID(id), X(x), Y(y){
}
double dataPoint::distance(dataPoint other) {
return pow( pow((this->X - other.getX()), 2)
+ pow((this->Y - other.getY()), 2), 0.5);
}
int dataPoint::getID() const {
return ID;
}
double dataPoint::getX() const {
return X;
}
double dataPoint::getY() const {
return Y;
}
bool dataPoint::operator==(const dataPoint& other) {
return getID() == other.getID();
}
I also needed a way to generate subsets of a given set. Doing some research online I found a clever way to do so using bit shifting. The function that generates my subsets is below:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <typename T>
map< int, vector<vector<T>>> generateChoicesOfS(vector<T> set){
map< int, vector<vector<T>>> result;
vector<T> s;
int n = set.size();
for (int i = 0; i < (1<<n); i++){
s.clear();
//cycle through possible number of elements
for (int j = 0; j < n; j++){
if ((i & (1<<j)) > 0){
s.push_back(set[j]);
}
}
//skip empty set
if (s.size() == 0)
continue;
//only take those that contain first element.
if (s[0] == set[0]){
result[s.size()].push_back(s);
}
}
return result;
}
The map it returns organizes the subsets by size. So if I want all of the subsets with size of 3, just call the map with 3.
As the algorithm is O(n22n) the implementation takes an awful long time, around 2 hours of run time. Reading the forums on coursera some students discussed an excellent idea using “Divide and Conquer”. If you split the points into two halves, the algorithm is instant for each case. Then, using the results of both half-problems, it’s only a few checks away from constructing the optimal solution. I would like to make a more general implementation of this method, I may return to this another day however as I have other things I need to work on.