Please use this identifier to cite or link to this item:
https://elibrary.tucl.edu.np/handle/123456789/15439
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Shrestha, Rajendra | - |
dc.date.accessioned | 2023-03-05T05:42:18Z | - |
dc.date.available | 2023-03-05T05:42:18Z | - |
dc.date.issued | 2015 | - |
dc.identifier.uri | https://elibrary.tucl.edu.np/handle/123456789/15439 | - |
dc.description.abstract | Subset Sum Problem is an important decision problem in complexity theory and cryptography. Subset sum problem can simply be described as: given a set of positive integers S and a target sum t, is there a subset of S whose sum is t? The complexity of subset sum can be viewed as depending on two parameters: n , the number of values, and m, the precision of the problem (number of bits required to state the problem). Backtracking algorithm for Subset Sum Problem can be modeled as a binary tree where each node represents a single activation of the recursive code. The worst-case time complexity is O(2 n ) when n is used as the complexity parameter [7]. Dynamic Programming breaks a problem down into smaller problems and solves them recursively as divide-and-conquer technique. It solves the problem in O(m.n 2 ) time. Dynamic Dynamic Programming is the extension of the Dynamic Programming with a dynamically allocated list of target sums. It has the time complexity of 2 O(x) when the total bit length x of the input set is used as the complexity parameter. The empirical analysis shows that time complexity of DP and DDP increase sub-exponentially when bit length, m, is increased by 1. At the same time BT is not sensitive to m and its time complexity increases exponentially when number of inputs, n, is increased by 1. Keywords: Subset Sum Problem, Backtracking, Dynamic Programming, Dynamic Dynamic Programming, Total Bit Length | en_US |
dc.language.iso | en_US | en_US |
dc.publisher | Department of Computer Science & Information Technology | en_US |
dc.subject | Backtracking | en_US |
dc.subject | Dynamic programming | en_US |
dc.subject | Total bit length | en_US |
dc.subject | Subset sum problem | en_US |
dc.title | An Empirical Evaluation of Algorithms for solving Subset Sum Problem in terms of Total Bit Length | en_US |
dc.type | Thesis | en_US |
local.institute.title | Central Department of Computer Science and Information Technology | en_US |
local.academic.level | Masters | en_US |
Appears in Collections: | Computer Science & Information Technology |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Cover page.pdf | 339.86 kB | Adobe PDF | View/Open | |
Chapter page.pdf | 1.04 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.