© studocu LP-II] Lab Manual - Advhle Bharati Vidyapeeth’s College Of Engineering, Lavale,Pune. Savitribai Phule Pune University (SPPU) Fourth Year of Computer Engineering (2019 Course) 410246: Laboratory Practice III Subject Teacher: - Dr. Prof. Uday C. Patkar Term work: 50 Marks Practical: 50 Marks Design and Analysis of Algorithms (410241) Machine Learning(410242) Blockchain Technology(410243) BHARATI VIDYAPEETH’S COLLEGE OF ENGINEERING LAVALE PUNE hosivestsreneon hy studocu. 16 by Noha Kardile (nehakardle125@amal com)Corrvetness of | Documentation of Total (ed Sign of Subject Prog Progra thence oral Teacher Expected Date of Completion: Actual Date of Completion: Group A Assignment No: 1 Title of the Assignment: Write a program non-recursive and recursive program to calculate Fibonacci numbers and analyze their time and space complexity. Objective of the Assignment: Students should be able to perform non-recursive and recursive rams to calculate Fibonacci numbers and analyze their time and space complexity Prerequisite: 1, Basic of Python or Java Programming Concept of Recursive and Non-recursive functions Execution flow of calculate Fibonacci numbers 4. Basic of Time and Space complexity 1. Introduction to Fibonacci numbers 2. Time and Space complexity BHARATI VIDYAPEETH’S COLLEGE OF ENGINEERING LAVALE,PUNE Downloaded by Neha Kardile (nchakardie125@amail com)Introduction to Fibonacci numbers . The Fibonacci series, named after Italian mathematician Leonardo Pisano Bogollo, later known as Fibonacci, is a series (sum) formed by Fibonacci numbers denoted as Fn. The numbers in Fibonacci sequence are given as: 0, 1, 1, 2,3, 5, 8, 13, 21, 38, * Ina Fibonacci series, every term is the sum of the preceding two terms, starting as first and second terms. In some old references, the term '0' might be omitted What is the Fibonacci Series? . The Fibonacci series is the sequence of numbers (also called Fibonacci numbers), where every number is the sum of the preceding two numbers, such that the first two terms are '0' and '1' . In some older versions of the series, the term '0' might be omitted. A Fibonacci series can thus be given as, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . It can be thus be observed that every term can be calculated by adding the two terms before it. . Given the first term, FO and second term, F1 as '0! and'I’, the third term here can be given as, FI=0+1= Similarly, F3=1+1=2 F4=2+1=3 Given a number n, print n-th Fibonacci Number. ONFibonacci Sequence Formula ‘The Fibonacci sequence of numbers “Fn” is defined using the recursive relation with the seed values FOO and F’ Fn=Fn-+Fn-2 Here, the sequence is defined using two different parts, such as kick-off and recursive relation. The kick-off part is FO=0 and F1=1. The recursive relation part is Fn = Fa-1+Fn-2. It is noted that the sequence starts with 0 rather than 1. So, F5 should be the 6th term of the sequence. Examples: Input: n=2 Output: 1 Tnput : Output : 34 The list of Fibonacci numbers are calculated as follows: Fa Fibonacci Number 0 0 1 1 2 1 3 2 4 37 13 8 2 9 34 and so on. sand so on. Method 1 (Use Non-recursion) A simple method that is a direct recursive implementation of mathematical recurrence relation is given above First, we'll store 0 and 1 in F{0] and F[1, respectively. Next, we'll iterate through array positions 2 to 7-2. At each position i, we store the sum of the two preceding array values in FU]. Finally, we return the value of F[7-1], giving us the number at position 1 in the sequence. Here’s a visual representation of this process:# Program to display the Fibonacci sequence up to n-th term terms = int(input("How many terms? ")) # first two terms nl, n2=0, 1 count =0 # check if the number of terms is valid ifnterms <= 0: print("Please enter a positive integer") # if there is only one term, return al elif nterms print( "Fibonacci sequence upto" nterms, print(n1) # generate fibonacci sequenceelse: print( "Fibonacci sequences") while count < nterms: print(nl) ath=nl +22 +# update values nl =n2 n2=nth count += 1 Output How many terms? 7 Fibonacci sequence: 0 1 Time and Space Complexity of Space Optimized Method ear. We have to find the sum of two terms 4 The time complexity of the Fibonacci series is T(N) ie, and it is repeated n times depending on the value of n, + The space complexity of the Fibonacci series using dynamic programming is O(1). Time Complexity and Space Complexity of Dynamic Programming «The time complexity of the above code is T(N) ice, linear. We have to find the sum of two terms and it is repeated n times depending on the value of n.+ The space complexity of the above code is O(N), Method 2 (Use Recursion) Let's start by defining F(n) as the function that returns the value of Fn, To evaluate F(n) for n> 1, we can reduce our problem into two smaller problems of the same kind: F(n-1) and F(-2). We can further reduce F(v-1) and F(y-2) to F((v-1)-1) and F((@r-1)-2); and F((n-2)-1) and F((1-2)-2), respectively. If we repeat this reduction, we'll eventually reach our known base cases and, thereby, obtain a solution to F(n). Employing this logic, our algorithm for F(n) will have two steps: 1. Check if <1. If'so, return n. 2. Check ifm > 1. Ifso, call our function F with inputs 7-1 and 7-2, and return the sum of the two results. Here’s a visual representation of this algorithm:# Python program to display the Fibonacci sequence def recur_fibo(n): ifn<=1: retuna else: return(recur_fibo(n-1) + recur_fibo(n-2)) nterms =7 # check if the number of terms is valid ifnterms <= 0: print("Plese enter a positive integer") else: print("Fibonacci sequence:") for iin range(nterms): print(recur_fiboti)) Output Fibonacci sequence: 0 Time and Space Complexity + The time complexity of the above code is T(2*N) i.e, exponential.4 The Space complexity of the above code is O(N) for a recursive series. ‘Method ‘Time complexity Space complexity Using recursion T(n) =T(n-1) + T(n-2) Om) Using DP. om) 0a) Space optimization of DP O(n) oa) Using the power of matrix own oa) method Optimized matrix method O(log n) O(log n) Recursive method in O(log n) O(log n) om) time Using direct formula O(log n) oq) DP using memoization om) oa) Applications of Fibonacci Series The Fibonacci series finds application in different fields in our day-to-day lives. The different pattems found in a varied number of fields from nature, to music, and to the human body follow the Fibonacci series. Some of the applications of the series are given as, * Its used in the grouping of numbers and used to study different other special mathematical sequences, * It finds application in Coding (computer algorithms, distributed systems, etc). For example, Fibonacci series are important in the computational run-time analysis of Euclid’s algorithm, used for determining the GCF of two integers. + Tris applied in numerons fields of science like quantum mechanics, cryptography, ete * In finance market trading, Fibonacci retracement levels are widely used in technical analysis. Conclusion- In this way we have explored Concept of Fibonacci series using recursive and non recursive method and also learn time and space complexityAssignment Question 1 2 3. 4. 5 ‘What is the Fibonacci Sequence of numbers? How do the Fibonacci work? What is the Golden Ratio? What is the Fibonacci Search technique? ‘What is the real application for Fibonacci series Reference link «-itps:/iwww scaler com/topics/fibonacci-series-in-c/ «+ huips:/:www.baeldung.com/cs fibonacei-computational-complexityDepartment of Computer Engineer Course : Laboratory Practice IL Timely Completion Teacher Expected Date of Completion:..u.sncnune Actual Date of Completion... Group A Assignment No: 2 Title of the Assignment: Write a program to implement Huffinan Encoding using a greedy strategy. Objective of the Assignment: Students should be able to understand and solve Huffinan Encoding using greedy method Prerequisit. 1. Basic of Python or Java Programming 2. Concept of Greedy method 3. Huffman Encoding concept Contents for Theory: 1. Greedy Method 2. Huffman Encoding 3. Example solved u: 1g huffman encodingWhat is a Greedy Method? «A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment, It doesa't worry whether the cusrent best result will bring the overall optimal result. + The algorithm never reverses the earlier decision even if the choice is wrong. It works in a top- down approach. + This algorithm may not produce the best result for all the problems. It's because it always goes for the local best choice to produce the global best result. Advantages of Greedy Approach + The algorithm is easier to describe. + This algorithm can perform better than other algorithms (but, not in all cases). Drawback of Greedy Approach «As mentioned earlier, the greedy algorithm doesn't always produce the optimal solution. This is the major disadvantage of the algorithm + For example, suppose we want to find the longest path in the graph below from root to leaf. Greedy Algorithm 1. To begin with, the solution set (containing answers) is empty. 2. At each step, an item is added to the solution set until a solution is reached. 3. Ifthe solution set is feasible, the current item is kept. 4, Else, the item is rejected and never considered again. Huffman Encoding ¢ Huffman Coding is a technique of compressing data to reduce its size without losing any of the details. It was first developed by David Huffinan, + Huflinan Coding is generally useful to compress the data in which there are frequently occurringcharacters. Hofliman Coding is a famous Greedy Algorithm. It is used for the lossless compression of data. It uses variable length encoding. It assigns variable length code to all the characters. ‘The code length ofa character depends on how frequently it occurs in the given text. The character which occurs most frequently gets the smallest code. The character which occurs least frequently gets the largest code. Iris also known as Huffman Encoding Prefix Rul Huffman Coding implements a rule known as a prefix rule This is to prevent the ambiguities while decoding. It ensures that the code assigned to any character is not a prefix of the code assigned to any other character ‘Major Steps in Huffman Coding- There are two major steps in Huffinan Coding- 1, Building a Huffman Tree from the input characters. 2. Assigning code to the characters by traversing the Huffinan Tree. ‘How does Huffman Coding work? Suppose the string below is to be sent over a network. BORA DSS SEG Initial string + Each character occupies 8 bits. There are a total of 15 characters in the above string. Thus, a total of 8 * 15 = 120 bits are required to send this string. + Using the Huffman Coding technique, we can compress the string to a smaller size.Huffman coding first creates a tree using the frequencies of the character and then generates code for each character. Once the data is encoded, it has to be decoded. Decoding is done using the same tree Huffman Coding prevents any ambiguity in the decoding process using the concept of prefix code ic. a code associated with a character should not be present in the prefix of any other code. The tree created above helps in maintaining the property. Huffman coding is done with the help of the following steps. Calculate the frequency of each character in the string Frequency of string 2. Sort the characters in increasing order of the frequency. These are stored in a priority quene Q. Characters sorted according to the frequency 3. Make each unique character as a leaf node, 4 Create an empty node 2, Assign the minimum frequency to the left child of z and assign the second minimum frequency to the right child of z. Set the value of the z as the sum of the above two ‘minimum frequencies.. A c B D Getting the sum of the least numbers 5. Remove these two minimum frequencies from Q and add the sum into the list of frequencies (* denote the internal nodes in the figure above). 6. Insert node z into the tree. 7. Repeat steps 3 to 5 for all the characters. B D Repeat steps 3 to § for all the characters.D Repeat steps 3 to § for all the characters. 8, For each non-leaf node, assign 0 to the left edge and 1 to the right edge ‘Assign 0 to the left edge and I to the right edge For sending the above string over a network, we have to send the tree as well as the above compressed-code. The total size is given by the table below.Department of Computer Engineering wise : Laboratory Practice IIL Character Frequency D 4*8=32bits Without encoding, the total size of the string was 120 bits. After encoding the size is reduced to 32 +15+28=75. Example: Afile contains the following characters with the frequencies as shown. If Huffman Coding is used for data compression, determine- Huffinan Code for each character 1 2. Average code length 3. Length of Huffman encoded message (in bits) Characters Frequencies | | a 10 [ rs [ 2 | ° 3 Ls ; ! - 13Department of Computer Engineering ‘Course: Laboratory Practice IL Step-01: 2999008 Ao eee? A OOOO QO Oo tCourse : Laboratory Practice IL neeringAfter assigning weight to all the edges, the modified Huffman Tree is-Department of Computer Engineering ‘Course : Laboratory Practice IL To write Huffinan Code for any character, traverse the Huffman Tree from root node to the leaf node of that character. Following this rule, the Huffman Code for each character is- a=ill e=10 i=00 o= 11001 u=1101 s=01 t= 11000Department of Computer Engineering Course : Laboratory Practice IL Time Complexity- The time complexity analysis of Huffman Coding is as follows. © extractMin( ) is called 2 x (n-1) times if there ar n nodes. #AsextractMin( ) calls minHeapify( ), it takes O(logn) time. Thus, Overall time complexity of Huftinan Coding becomes O(nlogn), Code :- ‘ob, symbol, left=None, right=None ee eden) omen Tye ret ae as aright = right ae symbols = dict() Beis) symbols. get (elenent! easy S symbol: ot oe we Ba nn (data, Ceres Tae] eum ic} print(coding[c], end = '') Sesame neers ca ruts) Ra eae Gmc en Tsp) ees (data, coding)Department of Computer Engineer Course : Laboratory Practice IL coe c ey) ears raat ire at eet) Peverstrecieant met) ee Barreaerenet ovens ight eFt.probrright.prob, left.symbol+ri Gros SO Mcone emt erie ear rere Mere hone ree Crete TO) Pnnreenscary preemies saa eee n (in bits): 16 aR oSUn soa Conclusion- In this way we have explored Concept ofHuffman Encoding using greedy method nment Question What is Huffinan Encoding? How many bits may be required for encoding the message ‘mississippi’? Which tree is used in Huffman encoding?Give one Example ‘Why Huffman coding is lossless compression? Reference linkDepartment of Computer Engineer Course : Laboratory Practice IL Timely Completion Teacher Expected Date of Completion: .ussnenune Actual Date of Completion... Group A Assignment No: 3 Title of the Assignment: Write a program to solve a fractional Knapsack problem using a greedy method, Objective of the Assignment: Students should be able to understand and solve fractional Knapsack problems using a greedy method Prerequisit 1, Basic of Python or Java Programming 2. Concept of Greedy method fractional Knapsack problem Contents for Theory: 1. Greedy Method 2. Fractional Knapsack problem 3. Example solved using fractional Knapsack problemWhat is a Greedy Method? +A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment. It doesn't worry whether the current best result will bring the overall optimal result. + The algorithm never reverses the earlier decision even if the choice is wrong. It works in a top- down approach. + This algorithm may not produce the best result for all the problems. It's because it always goes for the local best choice to produce the global best result. Advantages of Greedy Approach + The algorithm is easier to describe. + This algorithm can perform better than other algorithms (but, not in all cases). Drawback of Greedy Approach + Asmentioned earlier, the greedy algorithm doesn’t always produce the optimal solution. This is the major disadvantage of the algorithm + For example, suppose we want to find the longest path in the graph below from root to leaf. Greedy Algorithm 1. To begin with, the solution set (containing answers) is empty. 2. At each step, an item is added to the solution set until a solution is reached. 3. Ifthe solution set is feasible, the current item is kept. 4, Else, the item is rejected and never considered again. Knapsack Problem ‘You are given the following- © Aknapsack (kind of shoulder bag) with limited weight capacity.Department of Computer Engineering ‘Course : Laboratory Practice IL ‘© Few items each having some weight and value. The problem states- Which items should be placed into the knapsack such that- ‘© The value or profit obtained by putting the items into the knapsack is maximum. ‘© And the weight limit of the knapsack does not exceed. Knapsack Problem Knapsack Problem Variants Knapsack problem has the following two variants- 1. Fractional Knapsack Problem 2. 0/1 Knapsack Problem Fractional Knapsack Problem- In Fractional Knapsack Problem, + Asthe name suggests, items are divisible here + Weccan even put the fraction of any item into the knapsack if taking the complete item is notpossible. + Itis solved using the Greedy Method. Fractional Knapsack Problem Using Greedy Method- Fractional knapsack problem is solved using greedy method in the following steps- Step-O1: For each item, compute its value / weight ratio, Step-02: Arrange all the items in decreasing order of their value / weight ratio. Step-03: Start putting the items into the knapsack beginning from the item with the highest ratio. Putas many items as you can into the knapsack. Problem- For the given set of items and knapsack capacity ~ 60 kg, find the optimal solution for the fractional knapsack problem making use of greedy approach. n=5 w=60kg (w1, w2, w3, w4, w5) = (5, 10, 15, 22, 25) (b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90)‘Compute the value / weight ratio for each item- Items Weight Value x 5 30 2 10 40 15 45 22 Sort all the items in decreasing order of their value / weight ratio- W112 15 1413 (6) (4) (3.6) (3.5) (3)‘Step-03: Start filling the knapsack by putting the items into it one by one. Knapsack | Items in _ Weight | Knapsack 60 ® o 55 a 30 | ne | 7 | 20 112,15 | 160 Now, ‘© Knapsack weight left to be filled is 20 kg but item-4 has a weight of 22 kg. ‘© Since in fractional knapsack problem, even the fraction of any item can be taken. ® So, knapsack will contain the following items- <1, 2,15, (20/22) 14> Total cost of the knapsack = 160 + (20/22) x 77 = 160 +70 = 230 units ime Complexity- ‘© The main time taking step is the sorting of all items in decreasing order of their value / weight ratio. © Ifthe items are already arranged in the required order, then while loop takes O(n) time. © The average time complexity of Quick Sort is O(alogn).. © Therefore, total time taken including the sort is O(alogn)._——Depariment of Computer Engineering Code:- class Ttem: def __init_(self, value, weight): self-value = value self. weight — weight def fractionalKnapsack(W, arr): # Sorting Item on basis of ratio arr.sort(key-lambda x: (x.value/x.weight), reverse=Tre) +# Result(value in Knapsack) finalvalue = 0.0 # Looping through all Items for item in arr: # Ifadding Item won't overflow, #add it completely if item.weight <= W = itemweight finalvalue += item.value # Ifwe can't add current Item, # add fractional part of it else: finalvalue += item.value * W / item.w break +# Returning final value return finalvalue # Driver Code if__name__- Ww-50 arr = [Item(60, 10), Item(100, 20), Item(120, 30)] # Function call ‘max_val = fractionalKnapsack(W, arr) print(max_val) Output ‘Maximum value we can obtain = 24 Course : Laboratory Practice ILDepartment of Computer Engineering ‘Course : Laboratory Practice IL Conclusion-In this way we have explored Concept of Fractional Knapsack usi -edy method Assignment Question 1. What is Greedy Approach? 2. Explain concept of fractional knapsack 3. Difference between Fractional and 0/1 Knapsack 4. Solve one example based on Fractional knapsack(Other than Manual) Reference link + hups:/www.Department of Computer Engineer Course : Laboratory Practice IL Correctness of| Documentation of Timely Dated Sign of Subject zest “ Expected Date of Completion: Actual Date of Completion: Group A Assignment No: 4 Title of the Assignment Write a program to solve a 0-1 Knapsack problem using dynamic pr ramming or branch and bound strategy. Objective of the Assignment: Students should be able to understand and solve 0-1 Knepsack problem using dynamic programming Prerequisite: 1, Basic of Python or Java Programming 2. Concept of Dynamic Programmi 3.0/1 Knapsack problem Contents for Theory: & Greedy Method 2. 0/1 Knapsack problem 3. Example solved using 0/1 Knapsack problemWhat is Dynamic Programming? Dynamic Programming is also used in optimization problems. Like divide-and-conquer method, Dynamic Programming solves problems by combining the solutions of subproblems. Dynamic Programming algorithm solves each sub-problem just once and then saves its answer in a table, thereby avoiding the work of re-computing the answer every time, ‘Two main properties of a problem suggest that the given problem can be solved using Dynamic Programming. These properties are overlapping sub-problems and optimal substructure, Dynamic Pr mming also combines solutions to sub-problems. It is mainly used where the solution of one sub-problem is needed repeatedly. The computed solutions are stored in a table, so that these don’t have to be re-computed. Hence, this technique is needed where overlapping sub- problem exists. For example, Binary Search does not have overlapping sub-problem. Whereas recursive program of Fibonacci numbers have many overlapping sub-problems. Steps of Dynamic Programming Approach Dynamic Programming algorithm is designed using the following four steps — Characterize the structure of an optimal solution. Recursively define the value of an optimal solution ‘Compute the value of an optimal solution, typically in a bottom-up fashion. Construct an optimal solution from the computed information. Applications of Dynamic Programming Approach ‘Matrix Chain Multiplication Longest Common Subsequence Travelling Salesman ProblemDepartment of Computer Engineering ‘Course : Laboratory Practice IL Knapsack Problem ‘You are given the following- © Aknapsack (kind of shoulder bag) with limited weight capacity. ‘© Few items each having some weight and value The problem states- Which items should be placed into the knapsack such that- ‘© The value or profit obiained by putting the items into the knapsack is maximum. ‘© And the weight limit of the knapsack does not exceed. ? S! =x Knapsack Problem Knapsack Problem Variants Knapsack problem has the following two variants- 1. Fractional Knapsack Problem 2. O/1 Knapsack Problem,Department of Computer Engineering Course : Laboratory Practice IL 0/1 Knapsack Problem- In 0/I Knapsack Problem, «As the name suggests, items are indivisible here. © We can not take a fraction of any item. + We have to either take an item completely or leave it completely. # Ttissolved using a dynamic programming approach, 0/1 Knapsack Problem Using Greedy Method- Consider + Knapsack weight capacity + Number of items each havi w 1g some weight and value =n 0/1 knapsack problem is solved using dynamic programming in the following steps- Stey «Draw a table say “T’ with (n+1) number of rows and (w+1) number of columns. « Fillall the boxes of 0" row and 0" column with zeroes as shown-Start filling the table row wise top to bottom from left to right. Use the following formmla- TG, j) = max {T (iL, j), value + T(i-1, j—weights)} Here, T(i, j) = maximum value of the selected items if we can take items | to i and have weight restrictions of}. + This step leads to completely filling the table. + Then, value of the last box represents the maximum possible value that can be put into the knapsack. + To identify the items that must be put into the knapsack to obtain that maximum profit, + Consider the last column of the table. + Start scanning the entries from bottom to top. + Onencountering an entry whose value is not same as the value stored in the entry immediately above it, mark the row label of that entry. ¢ Affe all the entries are scanned, the marked labels represent the items that must be put into the knapsack Problem-, For the given set of items and knapsack capacity = 5 kg, find the optimal solution for the 0/1 knapsack problem making use ofa dynamic programming approach. Item Weight Value n=4 1 2 3 w=5kg 2 3 4 (w1, w2, w3, w4) = (2, 3, 4, 5) 3 4 5 (b1, b2, b3, b4) = (3, 4, 5, 6)Department of Computer Engineering wise : Laboratory Practice IIL Solution- + Knapsack capacity (w) = 5 kg + Number of items (n) =4 Step-01: ¢ Drawa table say “T° with (n+1) = 4+ 1 =5 number of rows and (w+1) = 5 +1 = 6 number of columns, © Fillall the boxes of 0 row and 0 column with 0. korn = 0 Step-02: Start filling the table row wise top to bottom from left to right using the formula- TG) =max (7 (44 j), value, + T(t ,j— weight} Finding Tt Substituting the values, we get- We have, TQ,1)=max {T(-1,1),3+T(-1,12)} isl TQ,1) = max {T(,1) ,3+TO-1)} ein} TCI) = TO.) {Ignore TO,-1 © (value), = (value), = 3 MLD“ TED (Ignore 70D) } © (weight), = (weight TAI) =0We have, (value), = (value), = (weight), = (weight) Substituting the values, we get- T(1,2)=max { T(1-1,2),3 + T(1-1,2-2)} ‘T(1,2)=max { T(0,2) 3 +T(0.0) } ‘T(1,2)= max {0,340} Ta.2)=3 (value), = (value), = 3 (weight), = (weight), = 2 (value), = (value (weight), = (weight), Substituting the values, we get- ‘T(,3)=max { T(I-1,3),3 + T(-1, 3-2) } T(L3) = max { 10,3), 3+ T,1) } T(L3) = max {0 340} T(3)=3 Substituting the values, we get- ‘T(1.4) = max { T(1-1 ,4),3+T(1-1, 4-2)} T(14) = max { T(0,4) , 3 + T(0,2) } ‘T(LA) = max {0,340} TU.4)=3Department of Computer Engineering Einding T.5)- We have, eit ° j-5 © (value), = (value), =3 . (weight), = (weight), = 2 Course : Laboratory Practice IL Substituting the values, we get- ‘T(1,S) = max { T(1-1 , 5) ,3 + T(1-1, 5-2) } TCLS) = max { T(0,5), 3+ 7,3) } T(1,5) = max {0 , 3+0} T(1,5)=3 Einding T2.)- Substituting the values, we get- We have, TQ) =max { TQ-1, 1), 4 + 12-1, 1-3) } e i-2 (2,1) =max { T(1,1), 4 + T(1,-2) } e jl = © (value), = (valug,=4 Tl) = TCI) { Ignore T(1,-2) } © (weight)i = (weight)2 = 3 T(21)=0 Finding 1(2,2)- Finding 1(2,3)- Werave sine + (value) = (aie) =4 + (aight) = (mighty = 2 ‘subttting he values we get 1.2) = max{ 1212), 4+ 121,239) T22)=max{ T.2).4+ 10-29) 122)= 104.2) nore Ta.-4)) Te2a=s Substituting the values, we gt 12.3)=max{T21,3),44 721,33) 1(2.3)=max{T(13) 4+ 1(.0)} 12.3) =max{ 3,440) e324Similarly. compute all the entries. ‘After all the entries are computed and filled in the table, we get the following table- stotofts]tets|@ T-Table +The last entry represents the maximum possible value that can be put into the knapsack. + So, maximum possible value that can be put into the knapsack = 7. Identifying Items To Be Put Into Knapsas Following Step-04, «© Wemark the rows labelled “1” and “ + Thus, items that must be put into the knapsack to obtain the maxinmam value 7 are- Item-1 and Item-2 ime Complexity + Each entry of the table requires constant time 0(1) for its computation. ¢ Tetakes 6(nw) time to fill (n+1)(w+l) table entries. + Ittakes @(n) time for tracing the solution since tracing process traces the n rows. + Thus, overall 6(aw) time is taken to solve 0/1 knapsack problem using dynamic programming# code 4A Dynamic Programming based Python # Brogram for 0-1 Knapeack problem # Returns the maximum value that can # be put in a knapsack of capacity W def mapsack(Ww, we, val, n)t dp = (Ofori inrange(W+1)] # Making the dp array ford inrange(1, ntl): # taking first i elements forw inrange(W, 0, -1): # starting from back,so that we also have data of # previous computation when taking i. items ifwt[i-t] < ¢ finding the maximum value p(w] ~max(dp(w], dplw-wt [1-1] +val [4-11) return dp[W] # returning the maximum value of knapsack 4 Driver code val = [60, 100, 120] we - (10, 20, 30] w=50 n = 1en(val)Conctusion-In this way we have explored Concept of 0/1 Knapsack using Dynamic approch Assignment Question 1, What is Dynamic Approach? 2. Explain concept of 0/1 knapsack 3. Difference between Dynamic and Branch and Bound Approach.Which is best? 4. Solve one example based on 0/1 knapsack(Other than Manual) Reference link s_of algorithms fractional_knapsack,htmDepartment of Computer Engineer Course : Laboratory Practice IL Timely Dated Sign of Subje Program Completion Teacher Expected Date of Completion: Actual Date of Completion: Group A Assignment No: § Title of the Assignment: Design n-Queens matrix having first Queen placed. Use backtracking to place remaining Queens to generate the final n-queen’s matrix. Objective of the Assignment: Students should be able to understand and solve n-Queen Problem.and understand basics of Backtracking Prerequisite 1. Basic of Python or Java Programming 2. Concept of backtracking method 3. N-Queen Problem Contents for Theory: 1. Introduction to Backtracking 2. N-Queen ProblemIntroduction to Backtracking 4 Many problems ate difficult to solve algorithmically. Backtracking makes it possible to solve at least some large instances of difficult combinatorial problems. Suppose we have to make a series of decisions among various choices, where «We don’t have enough information to know what to choose + Each decision leads to a new set of choices. + Some sequence of choices (more than one choices) may be a solution to your problem. What is backtracking? Backtracking is finding the solution of a problem whereby the solution depends on the previous steps taken. For example, in a maze problem, the solution depends on all the steps you take one-by-one. If any of those steps is wrong, then it will not lead us to the solution. In a maze problem, we first choose a path and continue moving along it. But once we understand that the particular path is incorrect, then we just come back and change it. This is what backtracking basically is In backtracking, we first take a step and then we see if this step taken is correct or not i.e., whether it will give a correct answer or not, And if it doesn’t, then we just come back and change our first step. In general, this is accomplished by recursion. Thus, in backtracking, we first start with a partial sub-solution of the problem (which may or may not lead us to the solution) and then check if we can proceed further with this sub-solution or not. Ifnot, then we just come back and change it, Thus, the general steps of backtracking are: «start with a sub-solution «check if this sub-solution will lead to the solution or not + Ifnot, then come back and change the sub-solution and confine again Applications of Backtracking: 4 N Queens Problem + Sum of subsets problemGraph coloring «Hamiltonian cycles. N queens on NxN chessboard One of the most common examples of the backtracking is to arrange N queens on an NxN chessboard such that no queen can strike down any other queen. A queen can attack horizontally, vertically, or diagonally. The solution to this problem is also attempted in a similar way. We first place the first queen anywhere arbitrarily and then place the next queen in any of the safe places. We continue this process until the number of unplaced queens becomes zero (a solution is found) or no safe place is left. If no safe place is left, then we change the position of the previously placed queen. 'N-Queens Problem: Aclassic combinational problem is to place n queens on a n'*n chess board so that no two attacks, i.e no two queens are on the same row, column or diagonal. What is the N Queen Problem? N Queen problem is the classical Example of backtracking. N-Queen problem is defined as, “given N x N chess board, arrange N queens in such a way that no two queens attack each other by being in the same row, column or diagonal”. © For N= 1, this is a trivial case. For N= 2 and N = 3, a solution is not possible. So we start with N= 4 and we will generalize it for N queens. Ifwe take n=dthen the problem is called the 4 queens problem. If we take n-8 then the problem is called the 8 queens problem. Algorithm 1) Start in the leftmost column 2) Ifall queens are place return true 3) Try all rows in the current column.Do following for every tried row. a) If the queen can be placed safely in this row then mark this (row, columa] as part of the solution and recursively check if placing queen here leads to 2 solution. bb) Ifplacing the queen in [row, column] leads to solution then return true ©) Ifplacing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step (a) to try other rows. 4) Ifall rows have been tried and nothing worked return false to trigger backtracking. 4-Queen Problem Problem 1 : Given 4 x 4 chessboard, arrange four queens in a way, such that no two queens attack each other. That is, no two queens are placed in the same row, column, or diagonal. 123 4 1 | | | | 2 3 4 4x4 Chessboard 4 We have to arrange four queens, Q1, Q2, Q3 and Q4 in 4 x 4 chess board. We will put with queen in ith row. Let us start with position (1, 1). QU is the only queen, so there is no issue. partial solution is «We cannot place Q2 at positions (2, 1) or (2, 2). Position (2, 3) is acceptable. the partial solution is <1. 3>. «Next, Q3 cannot be placed in position (3, 1) as QI attacks her. And it cannot be placed at (3. 2), (3. 3) or (3, 4) as Q2 attacks her. There is no way to put Q3 in the third row. Hence, the algorithm backtracks and goes back to the previous solution and readjusts the position of queen Q2. Q2 is moved fiom positions (2, 3) to (2, 4), Partial solution is <1, 4>+ Now, Q3 can be placed at position (3, 2). Partial solution is <1, 4, 3>. * Queen Q4 cannot be placed anywhere in row four. So again, backtrack to the previous solution and readjust the position of Q3. Q3 cannot be placed on (3, 3) o1(3, 4). So the algorithm backtracks even further. + All possible choices for Q2 are already explored, hence the algorithm goes back to partial solution <1> and moves the queen QI from (1, 1) to (1, 2). And this process continues until a solution is found. All possible solutions for 4-queen are shown in fig (a) & fig. (b) 123 4 1 1 Q, 2 2a | 3 3 Qg 4 af fof [| Fig. (a): Solution - 1 Fig, (b): Solution - 2 Fig. (d) describes the backtracking sequence for the 4-queen problem,The solution of the 4-queen problem can be seen as four tuples (x1, x2, X3, Xs), where x; represents the column number of queen Q.. Two possible solutions for the 4-queen problem are (2, 4, 1, 3) and (3, 1,4, 2 Explanation : € cee | The above picture shows an NxN chessboard and we have to place N queens on it. So, we will start by placing the first queen.‘Now, the second step is to place the second queen in a safe position and then the third queen, w ¥ wy Now, you can see that there is no safe place where we can put the last queen. So, we will just change the position of the previous queen. And this is backtracking. Also, there is no other position where we can place the third queen so we will go back one more step and change the position of the second queen. jee w w ‘And now we will place the third queen again in a safe position until we find a solution, i ‘We will continue this process and finally, we will get the solution as shown below.We need to check ifa cell (i,j) is under attack or not. For that, we will pass these two in our function along with the chessboard and its size - IS-ATTACK(i, j, board, N). If there is a queen in a cell of the chessboard, then its value will be 1, otherwise, 0. The cell (ij) will be under attack in three condition - if there is any other queen in row i, if there is any other queen in the column j or if there is any queen in the diagonals. ‘Same Cotume We are already proceeding row-wise, so we know that all the rows above the current row(i) are filled but not the current row and thus, there is no need to check for row i.We can check for the column j by changing k from 1 to i-1 in board[k][j] because only the rows from 1 to i-l are filled. ‘Queen can ony be present in these two col ‘So, check these to onl. No queen placed here Nomneedto check Check fortis cotumn for kin | to i-1 if board{k][j] return TRUE ‘Now, we need to check for the diagonal. We know that all the rows below the row i are empty, so we need to check only for the diagonal elements which above the row i If we are on the cell (i, j), then decreasing the value of i and increasing the value of j will make us traverse over the diagonal on the right side, above the row i.kei I= j+1 while k>=1 and I<=N if board[kj{l] = 1 return TRUE keke FHL Also if we reduce both the values of i and j of cel (i,j) by 1, we will traverse over the left diagonal, above the rowi. Keil I=j4 while k>=1 and b=-1 if board[k]{l] = 1 return TRUE kekeAt last, we will return false as it will be return true is not returned by the above statements and the cell (ij) is safe. ‘© can write the entire code as: IS-ATTACKG, j, board, N) // checking in the column j forkin 1 to itboard{k](]=1 return TRUE // checking upper right diagonal ‘while k>—1 and I<-N if board} (1) return TRUE kek ae // checking upper left diagonalwhile k>=1 and >=1 if board{k) (1) return TRUE ek M4 veturn FALSE Now, let's write the real code involving backtracking to solve the N Queen problem. Our function will take the row, number of queens, size of the board and the board itself - N-QUEEN(row, n, N, board), Ifthe number of queens is 0, then we have already placed all the queens. ifm setum TRUE Otherwise, we will iterate over each cell of the board in the row passed to the function and for each cell, we will check iff we can place the queen in that cell or not, We cant place the queen in a cel if it is under attack. forj inl toN if 1S-ATTACK(row, j, board, N) boardfrow][] = 1 After placing the queen in the cell, we will check if we are able to place the next queen with this arrangement or not, Ifnot, then we will choose a different position for the current queen for jin 1 toNifN-QUEEN(tow+1, a-1, N, board) return TRUE board[row][j] =0 if N-QUEEN(row*+L, n-1, N, board) - We are placing the rest of the queens with the current arrangement. Also, since all the rows up to ‘row’ are occupied, so we will star from 'row'+1". If this returns true, then we are successful in placing all the queen, if not, then we have to change the position of our current queen. So, we are leaving the current cell board{row][j] = 0 and then iteration will find another place for the queen and this is backtracking. Take a note that we have already covered the base case - if'u==0 — return TRUE. It means when all queens will be placed correctly, then N-QUEEN(row, 0, N, board) will be called and this will return true. At last, if true is not retumed, then we didn't find any way, so we will return false N-QUEEN(row, n, N, board) return FALSE QUEEN (row, n, N, board) itn—0 return TRUE for jin 1 toN if 1S-ATTACK(row, j, board, N) board{row][j] =1if N-QUEEN(row+1, »-1,N, board) return TRUE board{row][j] =0 //backtracking, changing current decision return FALSE Code :- # Python3 program to solve N Queen # Problem using backtracking globalN N=4 def printSolution(board): for iin range(N): for jin range(N): print(board| print() jJ.end =" # A utility function to check if'a queen can # be placed on board[row]|col]. Note that this, # function is called when "col" queens are # already placed in columns from 0 to col -1. # So we need to check only left side for # attacking queens def isSafe(board, row, col): # Check this row on left side for iin range(col): if board[row][i] return False # Check upper diagonal on left side for i, jin zip(range(row, -1, -1), range(col, -1, -1)): if board{ij [j] == 1: return False # Check lower diagonal on left side fori, j in zip(range(row, N, 1), range(col, -1,-1)): if board{i]{j] return Fals return True def solve NQUIil(board, col): # base case: [fall queens are placed # then return true if col >= Nz return TrueDepartment of Computer Engineer Course : Laboratory Practice IL board[ij[col] 1 # recur to place rest of the queens if solveNQUtil(board, col + 1 return True rue: # If placing queen in board[i][col # doesn't lead to a solution, then # queen from board{i] [col] board[ij|col] = 0 # if the queen can not be placed in any row in # this column col then return false return False # This function solves the N Queen problem using # Backtracking. It mainly uses solveNQUtilO to # solve the problem. It returns false if queens # cannot be placed, otherwise return true and # placement of queens in the form of Is. # note that there may be more than one # solutions, this function prints one of the # feasible solutions. def solveNQ board = [ [0, 0, 0, 0], (0, 0, 0, 0), [0, 0, 0,0}, [0, 0, 0, 0] ] if solveNQUtil(board, 0) == False: print ("Solution does not exist") return False printSolution(board) return True # Driver Code solveNQO Output Conclusion- In this way we have explored Concept of Backtracking method and solve -Queen problem using backtracking method Assignment Question 1. What is backtracking? Give the general Procedure. 2. Give the problem statement of the n-queens problem. Explain the solution. 3. Write an algorithm for N-queens problem using backtracking?Assignment No : 6 ‘MINI PROJECT 1 Theory := Multiplication of matrix does take time surely. Time complexity of matrix multiplication is O(n*3) using normal matrix multiplication. And Strassen algorithm improves It and Its time complexity Is (na(2.8074)). But, Is there any way to improve the performance of matrix multiplication using the normal method. Multi-threading can be done to improve it. In multi-threading, instead of utilizing a single core of your processor, we utilizes all or more core to solve the problem. We create different threads, each thread evaluating some part of matrix multiplication. Depending upon the number of cores your processor has, you can create the number of threads required. Although you can create as many threads as you need, a better way is to create each thread for one core. In second approach,we create a separate thread for each element in resultant matrix. Using pthread_exit() we return computed value from each thread which is collected by pthread_join(). This approach does not make use of any global variables. -- > | b threadi > [ All| Ai2 | a13 [Ais Bu] B12 | B13 [Bis thread2-> | A2i | A22 | a23 [A24] > B21 | B22 | B23 | B24 thread3 -> A31 | A32 | A33 | A34 B31 | B32 | B33 | B34 threads-> [ A41 | Aa2 | Aaa [Aas y [841 | Ba | pas [Bas Code :- 1 CPP Program to multiply two matrix using pthreads #include using namespace std; I maximum size of matrix #define MAX 4 I maximum number of threads define MAX_THREAD 4 int matA[MAXJIMAX]; int matB[MAX][MAX]. int matC[MAXJ[MAX]: int step. void* multi(void* arg) { int i= step_it+; /i denotes row number of resultant matC for (int j = 0; j < MAX: j++) for (int k = 0; k < MAX; k+#) matCii]fi] += matA[i][k] * matBIk][]: I Driver Code int main()