Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt
You are on page 1/ 10
Lecture 4
Divide and Conquer
Selection sort • Idea: Find the smallest element in the array Exchange it with the element in the first position Find the second smallest element and exchange it with the element in the second position Continue until the array is sorted
2 Algorithm
SELECTION-SORT(A) n ← length[A] for j ← 1 to n - 1 do smallest ← j for i ← j + 1 to n do if A[i] < A[smallest] then smallest ← i exchange A[j] ↔ A[smallest]
3 Analysis of Selection sort Selection Sort(A) Cost Times
n ← length[A] C1 1 for j ← 1 to n - 1 C2 n do smallest ← j C3 (n-1)
n 1 for i ← j + 1 to n C4 (n j 1) j 1
do if A[i] < A[smallest] C5
n 1 (n j ) j 1
then smallest ← i C6 n 1 j 1 (n j ) exchange A[j] ↔ A[smallest] C7 (n-1)
4 Strassen’s matrix multiplication The problem:
n n Multiply two matrices A and B, each of size
A B C nn nn nn
5 The conventional method
c00 c01 a00 a01 b00 b01
3 for loops = * c10 c11 a10 a11 b10 b11
a00 * b00 + a01 * b10 a00 * b01 + a01 * b11
= a10 * b00 + a11 * b10 a10 * b01 + a11 * b11
n C ij Aik Bkj k 1 Time complexity =O(N3)
6 The divide and conquer approach
ae+bg af+bh a b e f = * ce+dg cf+dh c d g h 8 multiplications C A B
• A,B and C are square matrices of size N N 4 additions
• a, b, c, d are sub-matrices of A, of size N / 2 N / 2 • e, f, g, h are sub-matrices of B, of size N / 2 N / 2
