CS200 Spring 2016 HW3

Procedure

Create a plain text file called hw3.txt, which looks like this: 
    Q1a:
    answer for question #1a

    Q1b:
    answer for question #1b
    …
Turn it in via web checkin, or like this: 
    ~cs200/bin/checkin HW3 hw3.txt
Do not turn in a paper copy.

Drawing Trees

For the following questions, draw trees using / and \, as follows. Avoid using tabs. 
                    a
                   / \ 
                  /   \ 
                 b     c
                /     / \
               d     e   f
  1. Draw the minheap that would be created by inserting these numbers, one by one, into an initially empty tree (78 first, 34 last):

    78, 90, 56, 12, 34

  2. Consider the previous heap, represented as an array. Show the array, with the root at the left, like this:

    89, 45, 23, 67

  3. Draw the maxheap that would be created by inserting these numbers, one by one, into an initially empty tree:

    14, 14, 21, 35, 62, 37, 30

  4. Consider the previous heap, represented as an array. Show the array.
  5. Consider this graph: 
                A ───────> B          C ───────> D
            │          │          ∧          │
            │          │          │          │
            ∨          ∨          │          ∨
            E ───────> F ───────> G ───────> H
    Show all possible topological orderings. They should all start with A.
  6. Consider this undirected graph, with edge weights: 
                      1          3          4
            A ──────── B ──────── C ──────── D
            │          │          │          │
           2│          │5         │2         │ 3
            │          │          │          │
            E ──────── F          G ──────── H
                  3                     1
    List the edges of the minimum spanning tree, like this: AB, AE, BC, CD, DH. Of course, that’s not a spanning tree, because F and G weren’t included.