Scribd Logo
Upload

Welcome to Scribd!

  • 22 views

    Worksheet 6

    Uploaded by

    gol gappa
    Found 4. Conclusion: The subset sum problem is solved using dynamic programming approach. The problem is recursively solved by checking if the sum can be achieved by including or excluding the last element of the set in all the subsets. Time complexity of this algorithm is O(n*sum) where n is the number of elements in set and sum is the given sum. Space complexity is O(sum) to store the results of subproblems. 5. Viva Questions: 1. Explain the subset sum problem. 2. What is the recursive relation used in the dynamic programming solution? 3. What is the time and space complexity of this algorithm? 4. Can we optimize the space complexity

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Worksheet 6

    Uploaded by

    gol gappa
    22 views4 pages
    Found 4. Conclusion: The subset sum problem is solved using dynamic programming approach. The problem is recursively solved by checking if the sum can be achieved by including or excluding the last element of the set in all the subsets. Time complexity of this algorithm is O(n*sum) where n is the number of elements in set and sum is the given sum. Space complexity is O(sum) to store the results of subproblems. 5. Viva Questions: 1. Explain the subset sum problem. 2. What is the recursive relation used in the dynamic programming solution? 3. What is the time and space complexity of this algorithm? 4. Can we optimize the space complexity

    Original Title

    Worksheet_6

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Found 4. Conclusion: The subset sum problem is solved using dynamic programming approach. The problem is recursively solved by checking if the sum can be achieved by including or excluding the last element of the set in all the subsets. Time complexity of this algorithm is O(n*sum) where n is the number of elements in set and sum is the given sum. Space complexity is O(sum) to store the results of subproblems. 5. Viva Questions: 1. Explain the subset sum problem. 2. What is the recursive relation used in the dynamic programming solution? 3. What is the time and space complexity of this algorithm? 4. Can we optimize the space complexity

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    22 views4 pages

    Worksheet 6

    Uploaded by

    gol gappa
    Found 4. Conclusion: The subset sum problem is solved using dynamic programming approach. The problem is recursively solved by checking if the sum can be achieved by including or excluding the last element of the set in all the subsets. Time complexity of this algorithm is O(n*sum) where n is the number of elements in set and sum is the given sum. Space complexity is O(sum) to store the results of subproblems. 5. Viva Questions: 1. Explain the subset sum problem. 2. What is the recursive relation used in the dynamic programming solution? 3. What is the time and space complexity of this algorithm? 4. Can we optimize the space complexity

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 4

    UNIVERSITY INSTITUTE OF ENGINEERING

    Department of Computer Science & Engineering

    Subject Name: Design and analysis of algorithm Lab

    Subject Code: 20CSP-312

    Submitted to: Submitted by:

    Sir Hemant Saini Name: Kumari Priyanshi

    UID:20BCS9841

    Section:615

    Group: A
    INDEX

    Ex. List of Experiments Conduct Viva Record Total Remarks/Signature


    No (MM: 12) (MM: 10) (MM: 8) (MM: 30)
    Code and analyze to compute
    1.1 the greatest common divisor
    (GCD) of two numbers .

    Code to implement power


    1.2 function in O(log n) time
    complexity .

    In O(N) time complexity, find


    1.3 the frequency of elements in a
    given array.

    i) Code for inserting and


    1.4 removing elements at the start
    and end of a doubly and circular
    linked list.

    ii) Using templates, write code


    to push and pop elements, check
    Isempty and Isfull, and return
    the top element in stacks.
    Code and analyze to find an
    2.1 optimal solution to matrix chain
    multiplication using dynamic
    programming.
    To implement subset-sum
    2.2 problem using Dynamic
    Programming

    2.4

    3.1

    3.2

    Experiment – 2.2

    Student Name: Kumari Priyanshi UID: 20BCS9841


    Branch: CSE Section/Group: 615/A
    Semester: 5th Date of Performance: 17-08-2022
    Subject Name: Design and analysis of algorithm Lab
    Subject Code: 20CSP-312

    1.Aim/Overview of the practical:   

    To implement subset-sum problem using Dynamic Programming.

    2. Objective : Subset sum problem is that given a subset A of n positive integers and a
    value sum is given, find whether or not there exists any subset of the given set, the sum of
    whose elements is equal to the given value of sum.

    3. Code and Output:

    class Mjava {
    static boolean SubsetSum(int set[],int n, int sum){
    if (sum == 0)
    return true;
    if (n == 0)
    return false;
    if (set[n - 1] > sum)
    return SubsetSum(set, n - 1, sum);
    return SubsetSum(set, n - 1, sum)
    || SubsetSum(set, n - 1, sum - set[n - 1]);
    }
    public static void main(String args[])
    {
    int set[] = { 3, 34, 4, 12, 5, 2 };
    int sum = 9;
    int n = set.length;
    if (SubsetSum(set, n, sum) == true)
    System.out.println("Found");
    else
    System.out.println("Not found");
    }
    }

    You might also like