Analysis of Algorithms : An Active Learning Approach

8.4 TESTING POSSIBLE SOLUTIONS 229

for j = 1 to N do

for k = 1 to graph[j].edgeCount do

if (colors[j] = colors[ graph[j].edge[k] ]) then

return no

end if

end for k

end for j

return yes

You should see that this algorithm properly checks the colors for the graph

provided. It goes through each node and if that node is directly connected to

another node that has the same color, it stops and returns no. If all are different,

it returns yes. If we analyze the time complexity of this algorithm, we see that

the outer for loop will do N passes. The inner loop looks at each edge con-

nected to the current node. The overall process, therefore, does a comparison

for each node’s edges. This means that this algorithm is in O(edges), which is

clearly polynomial because the number of edges is less than N^2. This, therefore,

meets our requirements.

8.4.3

1. Develop an algorithm to check a proposed decision solution for the follow-
   ing problems:
   a. Bin packing problem
   b. Traveling salesperson problem
   c. Backpack problem
   d. Subset sum problem
   e. CNF-satisfiability problem

9.2.6 Exercises