Activity 1

Group the following problems according to their “difficulty”. The three types of problems are:

• tractable, namely problems for which we know algorithms that run reasonably efficiently.
• intractable, namely problems for which the best algorithms we know are still extremely slow.
• undecidable, namely problems for which we know of now solutions (and even better if we can prove that no such solutions exist).

Here is the list of problems:

1. write a program that given a set of n numbers determines if we can split the numbers up in two groups so that the sums within each group are equal to each other.
2. write a program that given a list of numbers determines which one is the largest.
3. write a program that takes a source code as input and determines whether that code would create an infinite loop
4. write a program that given a graph with costs on each edge and given two nodes on the graph determines which path from one node to the other minimizes the total cost (we call this the shortest-path problem in algorithms)
5. write a program that takes as input a pair of source codes and determines whether the two source codes always produce identical results when given the same input.
6. write a program that takes as input a graph and a number K of colors, and determines if there is any way to “color” the nodes of the graph using at most K colors so that neighboring nodes have different colors.
7. write a program that takes as input a list of numbers and returns their median (that’s the number that is right in the middle if we order the numbers from smallest to largest).

Activity 2

Explain how a SISO program can process the following kinds of inputs:

• A list of an arbitrary number of integers.
• Two strings of predetermined length (say each of length 20).
• Two strings of non-predetermined length.
• Three strings of non-predetermined length.
• A list of an arbitrary number of strings of non-predetermined length.