Introduction


Exercise 1:
Which alternative (below) best describes algorithms and data structures?
1) An algorithm is used for solving a single problem. A data structure is a means to connect algorithms to solve more complex problems.
2) An algorithm is typically a Java program. A data structure typically consists of a CPU, RAM and a hard drive.
3) An algorithm is a step by step, detailed recipe for solving problems. A data structure expresses the content and syntax of a computer program.
4) An algorithm unambiguously describes how a problem can be solved. The algorithm stores and retrieves data from data structures

Exercise 2:
In this course we will primarily evaluate algorithms based on:
1) the efficiency of the implementation.
2) how the running time grows when the size of the input data grows towards infinity.
3) the running time of expected average input.
4) the memory usage of expected average input.
5) their elegancy. 

Exercise 3:
An instance of a certain problem is:
1) a sub-class of the problem. 
2) a super-class of the problem.
3) the solution to the problem.
4) an algorithm which solves the problem.
5) input to an algorithm which solves the problem.
6) unsolvable in polynomial time. 

Exercise 4:
Which is a common way of representing graphs in a computer?
1) A list of all paths (with all different lengths) you can walk from all possible vertices. 
2) An adjacency matrix where a '1' at indices i,j represent an arc from the vertex with index i to the vertex with index j. 
3) This is impossible. Graphs are of dimension >= 2, whereas computers can only store 1-dimensional data, in lists. 
4) You draw an image using ASCII-graphics, which the computer then reads. 

Exercise 5:
In this exercise we will have a look at a variant of the game Nim. The rules of our version are the following:
	"Two players take turns removing sticks from a pile on the table. Whoever picks up the last stick loses. 
	Each player must remove at least one and at most 7 sticks each turn."

a)
If there are 4 sticks left, how many of those will you have to remove to be sure to win?
1) 1
2) 2
3) 3
4) 4

b)
If there are 4 sticks left, how many of those will you have to remove to be sure to win?
1) 1
2) 2
3) 3
4) 4
5) 5
6) 6
7) 7

c)
If there are 250 sticks left, how many of those will you have to remove to be sure to win?
(Hint: Find a general strategy and use induction to show it is a winning strategy.)
1) 1
2) 2
3) 3
4) 4
5) 5
6) 6
7) 7