[go: up one dir, main page]
Scribd
Upload
7 views3 pages

Aziz Daa Assignment

The document provides definitions of Dynamic Programming (DP) and outlines its purpose of improving runtime through memory storage of computations. It includes two examples of problems solvable by DP techniques: partitioning a set into two equal sums and the 0/1 knapsack problem, detailing their algorithms and time complexities. The complexities for the partition problem is O(n x target) and for the knapsack problem is O(n x W).

Uploaded by

harryjhonsonpncjapan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views3 pages

Aziz Daa Assignment

The document provides definitions of Dynamic Programming (DP) and outlines its purpose of improving runtime through memory storage of computations. It includes two examples of problems solvable by DP techniques: partitioning a set into two equal sums and the 0/1 knapsack problem, detailing their algorithms and time complexities. The complexities for the partition problem is O(n x target) and for the knapsack problem is O(n x W).

Uploaded by

harryjhonsonpncjapan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

AZIZ SHAHZAD

BSCS 4th SEMESTER


DESIGN ANALYSIS OF ALGORITHM
21122021

Assignment

Q: Write 3 different definitions of Dynamic Programing (DP).


Ans: Dynamic Programming:-
• Dynamic programming is the technique of storing repeated
computations in memory, rather than recomputing them every time.
• The ultimate goal of Dynamic programming is to improve run time.
This process allows you to take more space to take less time
• In Dynamic programming, the word ‘programming’ is synonym for
planning to mean the process of determining the sequence of
decisions that have to be made, while ‘Dynamic’ suggested the
evolution of the system over time.

Q: Give 2 examples of problem that can be solved using DP techniques.


a. state the Problem,
b. Give the solution (Algorithm) of the Problem
c. Compute the Complexity of the Algorithms.

Ans:
1. Problem: Partition a Set into Two Equal Sums
• Given a set of positive integers, determine if it can be partitioned into
two parts having equal sum using dynamic programming approaches.
Let,
S = {1, 5, 11, 5}
• Algorithm:
Step 1. Calculate the total sum of the set S. [O(n)]
Step 2. If the total sum is odd, return False. [O(1)]
Step 3. Set target to half of the total sum. [O(1)]
Step 4. Create a set possible_sums and initialize it with {0} (sum of 0 is
possible). [O(1)]
Step 5. For each element in set S: [O(n x target)]
• Create a temporary set n_sums to store new sums. [O(1)]
• For each sum in possible_sums, add current element to it and add
the result to n_sums. [O(n x target)]
• Add all sums in n_sums to possible_sums. [O(target)]
Step 6. After processing all elements, check if target is in
possible_sums. [O(1)]
• If target is in possible_sums, return True. [O(1)]
• If target is not in possible_sums, return False. [O(1)]

• Complexity:
Step 1: [O(n)]
Step 2: [O(1)]
Step 3: [O(1)]
Step 4: [O(1)]
Step 5: [O(n x target)]
Step 6: [O(1)]
Total time complexity = O(n) + O(1) + O(1) + O(1) + O(n x target) +O(1)
= O(n x target)

2. Problem: 0/1 Knapsack Problem

• You are given n items, each with a weight and a value, and a knapsack with a
weight capacity W. You need to determine the maximum value you can carry in
the knapsack without exceeding the weight capacity.
• Algorithm:

Step 1: Define a function knapsack (n, W, weights, values, memo):

• If n == 0 or W == 0, return 0
• If memo [n] [W] is not null, return memo [n] [W]
• If weights [n-1] > W, call knapsack (n-1, W, weights, values, memo).
• Otherwise
• Call knapsack (n-1, W, weights, values, memo).
• Store the maximum of the two results in memo[n][W].
• Return memo [n][W].

Step 2. Define the function solveKnapsack (weights, values, W)

• Set n to the length of weights.


• Create a 2D array memo of size (n+1) x (W+1) initialized to null
(memoization table).
• Call knapsack(n, W, weights, values, memo) and return the result

• Time Complexity:

Step 1. O(1)
• O(1)
• O(1)
• O(1)
• O(1)
• O(1)
• O(1)

Step 2. O( n x W)

• O(1)
• O( n x W)
• O(n x W)

Total Time Complexity = O(1) + O(n x W)

= O( n x W)

You might also like