Analysis Q implemented as a binary heap. Line 2 can be performed by using BUILD-HEAP (P. 145; CLR) in O(n) time. FOR loop executed |n| - 1 and since each heap operation requires O(lg n) time. => the FOR loop contributes (|n| - 1) O(lg n) => O(n lg n) Thus the total running time of Huffman on the set of n characters is O(nlg n). LECTURE-23 An Activity Selection Problem An activity-selection is the problem of scheduling a resource among several competing activity. Problem Statement Given a set of activities with and start time, and finish time of an ith S n Si fi, activity. Find the maximum size set of mutually compatible activities. Compatible Activities Activities and are compatible if the half-open internal [si, and [sj, i j fi) fj) do not overlap, that is, and are compatible if and i j si fj sj fi ≥ ≥ Greedy Algorithm for Selection Problem I. Sort the input activities by increasing finishing time. . . . f1 f2 fn ≤ ≤ ≤ II. Call GREEDY-ACTIVITY-SELECTOR (s, f) = length [s] n A={i} j = 1 for i = 2 to n do if si fj ≥ then A= AU{i} j = i return set A
Analysis Q implemented as a binary heap. Line 2 can be performed by using BUILD-HEAP (P. 145; CLR) in O(n) time. FOR loop executed |n| - 1 and since each heap operation requires O(lg n) time. => the FOR loop contributes (|n| - 1) O(lg n) => O(n lg n) Thus the total running time of Huffman on the set of n characters is O(nlg n). LECTURE-23 An Activity Selection Problem An activity-selection is the problem of scheduling a resource among several competing activity. Problem Statement Given a set S of n activities with and start time, Si and fi, finish time of an ith activity. Find the maximum size set of mutually compatible activities. Compatible Activities Activities i and j are compatible if the half-open internal [si, fi) and [sj, fj) do not overlap, that is, i and j are compatible if si ≥ fj and sj ≥ fi Greedy Algorithm for Selection Problem I. Sort the input activities by increasing finishing time. f1 ≤ f2 ≤ . . . ≤ fn II. Call GREEDY-ACTIVITY-SELECTOR (s, f) n = length [s] A={i} j = 1 for i = 2 to n do if si ≥ fj then A= AU{i} j = i return set A
DAA%20Lecture%20Notes%20(I%20&%20II).docx