Algorithms and Data Structures (INF1, Autumn'05)
Answers for Exam Questions from 30.1.2006
Question 1
- a) False, True, True, False
- b) No, Yes
- c) G, D, H, E B, F, C, A
- d) n2
- e) 2, 1, 4
- f) for example edges: A->B, B->C and B->D
- g) root: 8 with left child 4 and right child 9;
4 with left child 2 and righ child 5; 5 with right child 7
Question 2 (sketch)
- a) s1.make; s1.push(s.new_entry(3)); s1.push(s.new_entry(2));
- b) do_pop(s: STACS) = x:=s.top; s.remove; return x
- c) (sketch): create a new temporary stack s'; as long as the stack
s is nonempty, use do_pop to move the entry to the temporary
stack and at the same time add its value to some variable stroring
the current sum; after the stack is emptied, restore its content
(by a while loop) from s'. Complexity is O(n) where n is
the size of the stack s
Question 3 (sketch)
This is a graph problem.
- a) observe that a connected network without any unnecessary links
must be a tree, hence n servers need n-1 links to connect them
into a tree
- b) we can use the abstract datatype GRAPH to represent the problem;
servers are nodes and links are undirected edges
- c) connect any three of the servers into a loop
- d) note that a graph with n nodes and n-1 edges is a tree if and
only if it is connected; it is therefore enough to pick up
any node, run (e.g.) depth-first search from that node and
check whether all nodes have been visited; if yes then the
graph does not contain a cycle; if not then there is a cycle
in the graph; complexity is O(n + (n-1)) = O(n) where n is
the number of nodes
- e) for example by modification of depth-first search so that
when we discover an edge leading to an already visited node A,
we list the parents of nodes created during the search
and stop when we see A again; complexity is O(n) where
n is the number of nodes