Give a Divide-and-Conquer algorithm that finds the distance between the closest

Question

Give a Divide-and-Conquer algorithm that finds the distance between the closest pair of points on a straight line. (You may assume the line to be parallel to the X-axis). Also give an analysis of your algorithm

Explanation / Answer

A divide­and-conquer algorithm proceeds as follows. lf the problem is small, it is solved directly. lf the problem is large, the problem is divided into two or more parts called subproblems. Each subproblem is then solved after which solutions to the subproblems are combined into a solution to the original problem. The divide-and-conquer technique is also used to solve the subproblems; that is, the subproblems are further divided into subproblems, which are divided into subproblems, and so on. Eventually, small problems result that can be solved directly. The solutions to the various subproblems are then Combined into a solution to the original problem. Recursion is of- ten used to solve a subproblem. As an example, an array of two or more elements can be sorted by using a divide-and-Conquer algorithm in which the original array is divided into two parts. lf either part Consists of one element, that part is already sorted. Parts containing two or more elements are sorted recursively. Finally, the two sorted arrays are merged into a single sorted array. The sorting algorithm is called mergesort and is discussed in Section 5.2. We begin in Section 5.1 by introducing the divide-and-conquer technique with a tiling problem. After discussing mergesort (Section 5.2), we turn to a geometry problem that has an elegant diVide­and-conquer solution (Sec- tion 5.3). The chapter concludes with a divide-and-conquer algorithm for multiplying matrices (Section 5.4), which is asymptotically faster than the algorithm derived directly from the definition of matrix multiplication. In succeeding chapters, we will again have occasion to use the divide-and- conquer technique (see, e.g., Section 6.2, Quicksort, and Section 6.5, Selec- tion). 5.1 A Tiling Problem A right tromino, hereafter Called simply a tromino, is an object made up of three 1 1 squares, as shown in Figure 5.1.1. We Call an 11 11 board, with one 1 1 square (on the unit grid lines) removed, a deficient board (see Figure 5.1.2). Our tiling problem can then be stated as follows: Given a deficient n n board, where n is a power of 2, tile the board with trorninoes. By a tiling of the board with trominoes, we mean an exact Covering of the board by trominoes without having any of the trorninoes overlap each other or extend outside the board. Suppose that we are given a deficient n n board, where n is a power of 2. If 11 = 2, we can tile the board because the board is a tromíno (see Figure 5.1.1). Suppose that n > 2. A divide­and-Conquer approach to solving the tiling problem begins by dividing the original problem (tile the n n board) into subproblems (tile smaller boards). We divide the original board into four 11/2 n/2 subboards [see Figure 5.1.4(a)]. Since n is a power of 2, 11/2 is also a power of 2. The subboard that Contains the missing square [in Figure 5.1.4(a), the upper-left subboard] is a deficient n/2 n/2 subboard, so we can recursively tile it. The other three n/ 2 n/ 2 subboards are not deficient, so we cannot directly recursively tile these subboards. However, if we place a tromino as shown in Figure 5.l.4(b) so that each of its 1 1 squares lies in Using divide and Conquer to tile a deficient 11 11 board with trominoes. In (a), the original n 11 board is divided into four 11/2 11/2 subboards. The subboard containing the missing square is then tiled recur- sively. A tromino is placed as shown in (b) so that each of its 1 1 squares lies in one of the three remaining subboards. These 1 1 squares are then considered as missing. The remaining subboards are then tiled recursively. one of the three remaining subboards, we can consider each of these 1 1 squares as missing in the remaining subboards. We can then recursively tile these deficient subboards. Our tiling problem is solved.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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