Answers to exercises:


Lecture 2:
   1. a) insertion sort of sorted arrays has linear complexity, because we don't need to move elements
   2. c) insertion sort of arrays sorted in reverse order has the worst-case complexity (n^2) because at each step we move all the elements one position to the right in order to make room for the new element to insert.
   3. b) we add 2 (N-1) times -> 2 N -1 -> O (N)

Lecture 3:
   1. c) O(N) because we need to move the other elements one position to the left   
   2. a) repeated insertions and deletions because we could reach the end of the array

Lecture 4 (Nils Anders):
   1. b) O(1) for enqueue, O(N) for deleting the minimum
   2. a)
  
Lecture 5:
   1. c) for n >= 16 (theoretically)
   2. demonstration on slides

Lecture 6:
   1. b) 2 because it's a multigraph 
   2. c) 6
   3. b) No, because the number of 2|V| <= |E| <= 4|V|
   4. a) Yes - with a stack (see later in the course)

Lecture 7:
   1. c) O(|V|+|E|) - see complexity explanation on next slides
   2. Partition into strong components: {7}, {8}, {9}, {0,1,2}, {3}, {4,5,6}
   3. c) Unweighted graphs, because we don't use the weights in any way
   4  d) Priority queue - better complexity

Lecture 8: 
   1. a) because we count the edges and not the nodes
   2. a) 
   3. and traversal on levels is equivalent to BFS
   4. b)
   5. c)
   6. c) if it had a right child, it wouldn't be the largest value from the left subtree

Lecture 9:
   1. b) 
   2. c) (1,2 and 4 are true)
   3. c) explanation later

Lecture 10 (AVLs):
   1. b)
   2. b) see with visualgo, explanations next slide
   
Lecture 11 (Andreas): 
    no questions

Lecture 12 (Red-Black): 
   1. c)
   2. a)