E Lesson 6

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

MCA 2 All right are reserved with CU-IDOL DESIGN AND ANALYSIS OF ALGORITHMS Course Code: MCA 632 Semester: Third e-Lesson: 6 SLM Unit: 7 www.cuidol.in Unit-7(MCA 632)

Design and Analysis of Algorithms 33 OBJECTIVES INTRODUCTION  Student will be able to learn about greedy  In this unit we are going to learn about approach to design some more algorithm. algorithm analysis through greedy method.  Student will be able to solve Huffamn code Under this you will learn and understand the concept of shortest path algorithm problems and Dijkastra Algorithm   Student will be able to learn to do Heap Sort Huffamn code is used to compress the data Student will be able to learn Optimal binary search tree.  Heap sort  www.cuidol.in Unit-7(MCAQ-613021)) INSTITUTE OF DAIlSlTAriNgChEt aArNeDreOsNeLrvINeEd LwEiAthRNCIUN-GIDOL

TOPICS TO BE COVERED 4 Greedy Method 2: Single source Shortest paths Dijkastra’s Algorithm Optimal Tree Problem Huffman Trees and Codes Transform and Conquer Approach Heaps and Hear Sort www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

Greedy Method 5  A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.  How do you decide which choice is optimal? Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision. www.cuidol.in Unit-7(MCA 632) 5All right are reserved with CU-IDOL

The single-source 6 shortest path problem • shortest paths from v0 to all destinations Fig. 2.8: Single-source shortest path Unit-7(MCA 632) All right are reserved with CU-IDOL www.cuidol.in

The single-source 7 shortest path problem • Given a connected weighted directed graph G(V,E), associated with each edge ⟨u,v⟩∈E, there is a weight w(u,v). The single source shortest paths (SSSP) problem is to find a shortest path from a given sourcer to every other vertex v∈V-{r}. The weight (length) of a path p=⟨ v0 , v1 ,…, vk ⟩ is the sum of the weights of its constituent edges: w(p)= ∑ w i( vi-1 , vi ). where i=1to k The weight of a shortest path from u to v is defined by δ(u,v)=min{w(p): p is a path from u to v}. www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

8 Algorithm 1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty. 2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first. 3) While sptSet doesn’t include all vertices ….a) Pick a vertex u which is not there in sptSet and has minimum distance value. ….b) Include u to sptSet. ….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v. www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

Dijkastra’s Algorithm 9 In the cost adjacency matrix, all entries not shown are +. 1 2 34 5 67 8 0 10 2 300 0 3 1000 800 0 4 1200 0 5 1500 250 0 6 1000 900 1400 Fig. 2.9: Implementation 0 1000 7 All right are reserved with CU-IDOL 0 8 1700 www.cuidol.in Unit-7(MCA 632)

10 Vertex Iteration S Selected (1) (2) (3) (4) (5) (6) (7) (8) Initial ---- 15 6 + + + 1500 0 250 + + + + + 1250 0 250 1150 1650 2 5,6 7 + + + 1250 0 250 1150 1650 + + 2450 1250 0 250 1150 1650 3 5,6,7 4 3350 + 2450 1250 0 250 1150 1650 3350 3250 2450 1250 0 250 1150 1650 4 5,6,7,4 8 3350 3250 2450 1250 0 250 1150 1650 5 5,6,7,4,8 3 6 5,6,7,4,8,3 2 5,6,7,4,8,3,2 www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

Huffman Code 11 In telecommunication, how do we represent a set of messages, each with an access frequency, by a sequence of 0’s and 1’s? To minimize the transmission and decoding costs, we may use short strings to represent more frequently used messages. This problem can by solved by using an extended binary tree which is used in the 2-way merging problem. Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

Huffman Code 12 • Symbols: A, B, C, D, E, F, G freq. : 2, 3, 5, 8, 13, 15, 18 • Huffman codes: A: 10100 B: 10101 C: 1011 D: 100 E: 00 F: 01 G: 11 A Huffman code Tree Fig. 2.9: Implementation Unit-7(MCA 632) All right are reserved with CU-IDOL www.cuidol.in

Huffman Code 13 Huffman (C) Unit-7(MCA 632) All right are reserved with CU-IDOL 1. n=|C| 2. Q=C 3. for i=1 to n-1 4. do 5. z=allocate_Node() 6. x=left[z]=Extract_Min(Q) 7. y=right[z]=Extract_Min(Q) 8. f[z]=f[x]+f[y] 9. Insert(Q,z) 10. return Extract_Min(Q) www.cuidol.in

Huffman Code 14 Analysis The Q is initialized as a priority queue with the character C. Q=C can be performed by using Build_Heap in O(n) time. For loop takes (|n|-1) times because each heap operation requires O(log n) time. Hence the total running time of Huffman code on the set of n characters is O(n log n). www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

Transform and Conquer 15 Transform and Conquer: Instances and Structuring Either the problem or algorithm can be transformed in one of three ways: • Instance simplification: the instances of the problem can be transformed into an easier instance to solve. Example - Presorting • Representation change: the data structure can be transformed so that it is more efficient. Example- Binary search tree and Heaps • Problem reduction: the problem can be transformed to an easier problem to solve. www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

Heap Sort 16 • Heap Sort Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element. • What is Binary Heap ? Let us first define a Complete Binary Tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap. The heap can be represented by binary tree or array. www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

Heap Sort 17 • Why array based representation for Binary Heap? Since a Binary Heap is a Complete Binary Tree, it can be easily represented as array and array based representation is space efficient. If the parent node is stored at index I, the left child can be calculated by 2 * I + 1 and right child by 2 * I + 2 (assuming the indexing starts at 0). • Heap Sort Algorithm for sorting in increasing order: 1. Build a max heap from the input data. 2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree. 3. Repeat above steps while size of heap is greater than 1. www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

Heap Data Structure 18 • Def: A heap is a nearly complete binary tree with the following two properties: – Structural property: all levels are full, except possibly the last one, which is filled from left to right – Order (heap) property: for any node x Parent(x) ≥ x From the heap property, it follows that: “The root is the maximum element of the heap!” A heap is a binary tree that is filled in order www.cuidol.in Unit-7(MCA 632) 1A8ll right are reserved with CU-IDOL

Heap Data Structure 19 Max-heaps (largest element at root), have the max-heap property: for all nodes i, excluding the root: A[PARENT(i)] ≥ A[i] Min-heaps (smallest element at root), have the min-heap property: for all nodes i, excluding the root: A[PARENT(i)] ≤ A[i] www.cuidol.in Unit-7(MCA 632) 1A9ll right are reserved with CU-IDOL

Example of Heap Data 20 Structure MAX-HEAPIFY(A, 2, 10) A[2]  A[4] A[2] violates the heap property A[4] violates the heap property A[4]  A[9] Heap property restored 2A0ll right are reserved with CU-IDOL Fig. 2.10: Implementation Unit-7(MCA 632) www.cuidol.in

Heap Data Structure 21 Complexity: max_heapify has complexity O(logN), build_maxheap has complexity O(N) and we run max_heapify N−1times in heap_sort function, therefore complexity of heap_sort function is O(NlogN). Complexity Analysis of Heap Sort Worst Case Time Complexity: O(n*log n) Best Case Time Complexity: O(n*log n) Average Time Complexity: O(n*log n) Space Complexity : O(1) Heap sort is not a Stable sort, and requires a constant space for sorting a list. Heap Sort is very fast and is widely used for sorting. www.cuidol.in Unit-7(MCA 632) 2A1ll right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 22 1. Which of the following is not greedy approach method? b) Heap Sort a) Huffman Code d) Spanning tree c) Binary search 2. Time Complexity of Optimal binary search tree. Select one: a) O(logn) b) O(n) c) O(n!) d) O(n^2) 3. Transform and conquer algorithm can be transformed in following ways a) Instance simplification b) Representation change c) Problem reduction d) All of the above www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 23 4. Which of the following does not belongs to the same algorithm paradigm which the others belong to a) Minimum and Maximum Problem b) Knapsack Problem c) Selection Problem d) Merge Sort 5. Time complexity of Huffman code is b) O(nlog n) a) O(n) d) O(log n) c) O(1) 6. Time complexity of Heap sort is b) O(n2) a) O(n) d) O(log n) c) O(nlog n) Answers:1)-c 2)a 3)-d 4)-d 5)-b 6)-c www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

SUMMARY 24 This presentation includes unit 7. As we discussed in previous presentation, greedy approach provides an optimal solution in local situation. Here we are some examples like Dijkastra’s algorithm, Huffman code and Heap sort. Dijkastra is a single source shortest path algorithm. Huffman code is used to minimize the transmission and decoding costs, we may use short strings to represent more frequently used messages. And Heap sort is a sorting method to arrange the elements under greedy approach by creating trees. www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 25 Q1. Discuss Dijkastra’s algorithm. Ans. This is a single source shortest path algorithm. For Further details please refer to the SLM Q2. what is an optimal Huffman code for alphabet b of the following set of frequencies a: 45, b:13, c:12, d:16, e:9, f:5 Ans. Go through previous slides to calculate the code. For Further details please refer to the SLM Q3. Why are we using Heap Sort. Ans. We use heap sort to sort elements with decreased complexity level.. For Further details please refer to the SLM www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

REFRENCES 26 1) Data Structures and Algorithms made easy By Narasimha Karumanchi. 2) The Algorithm Design Manual, 2nd Edition by Steven S Skiena 3) Fundamentals of Computer Algorithms - Horowitz and Sahani 4) https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/ 5) https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/ 6) https://www.geeksforgeeks.org/heap-sort/ www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL

27 THANK YOU www.cuidol.in Unit-7(MCA 632) All right are reserved with CU-IDOL