Chapter 11: Trees

Describe an algorithm for finding a spanning tree with minimal weight containing a specified set of edges in a connected weighted undirected simple graph.

Draw the ordered rooted tree corresponding to each of these arithmetic expressions written in prefix notation. Then write each expression using infix notation.

1. \({\bf{ + }} * {\bf{ + - 53214}}\)
2. \( \uparrow {\bf{ + }}23{\bf{ - }}51\)
3. \( * {\bf{/93 + }} * {\bf{24 - 76}}\)

List the vertices of the ordered rooted trees in Figures 3 and 9 of Section 11.3 in level order.

What is the value of each of these prefix expressions?

a) \({\bf{ - }} * {\bf{2/}}8{\bf{4}}3\)

b) \( \uparrow {\bf{ - }} * 33 * 425\)

c) \({\bf{ + - }} \uparrow 3{\bf{2}} \uparrow 23{\bf{/}}6{\bf{ - }}42\)

Suppose that an airline must reduce its flight schedule tosave money. If its original routes are as illustrated here, which flights can be discontinued to retain service between all pairs of cities (where it may be necessary to combine flights to fly from one city to another)?

A chain letter starts with a person sending a letter out to \({\bf{10}}\) others. Each person is asked to send the letter out to \({\bf{10}}\) others, and each letter contains a list of the previous six people in the chain. Unless there are fewer than six names in the list, each person sends one dollar to the first person in this list, removes the name of this person from the list, moves up each of the other five names one position, and inserts his or her name at the end of this list. If no person breaks the chain and no one receives more than one letter, how much money will a person in the chain ultimately receive?

Express the algorithm devised in Exercise \(22\) in pseudo code.

Use Huffman coding to encode these symbols with givenfrequencies: a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30.

What is the average number of bits required to encode a character?

Devise an algorithm for listing the vertices of an ordered rooted tree in level order.

Explain how breadth-first search or depth-first search canbe used to order the vertices of a connected graph.