For each of the greedy algorithms that are given below for solving the “wiring (

Question

For each of the greedy algorithms that are given below for solving the “wiring (i.e., connecting) black dots to white dots” problem, do the following:

(i) write pseudo-code to implement the algorithm

(ii) analyze the worst-case running time of the algorithm (i.e., O()). For each algorithm:

Input: dots[1..2n] where dots[i] = ‘B’ or ‘W’; assume the array contains n ‘B’ dots and n ‘W’ dots, n > 0

Output: pairs[1..n] where pairs[i] = (index position of a ‘B’ in dots[], index position of a ‘W’ in dots); these indices represent the ‘B’ and ‘W’ entries that you’re “connecting” (e.g., (3, 5) means you’re connecting the entry in dots[3] to the entry in dots[5])

a. Wire (i.e., connect) the ith black dot to the ith white dot, i = 1..n (i.e., working “left” to “right”, connect each black dot to the first unconnected white dot it finds).

b. Wire (i.e., connect) the black and white dots that are closest to each other. Then connect the next two closest unconnected black and white dots. Continue until all black and white dots are connected. That is, start by using the minimum amount of wire to get a valid connection made, then progressively use more wire (in the same fashion) as needed.

Explanation / Answer

1

Know what pseudocode is. Pseudocode is a step-by-step verbal outline of your code that you can gradually transcribe into programming language. Many programmers use it to plan out the function of an algorithm before setting themselves to the more technical task of coding. Pseudocode serves as an informal guide, a tool for thinking through program problems, and a communication device that can help you explain your ideas to other people.

2

3

4

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.