Please use this identifier to cite or link to this item:
https://elibrary.tucl.edu.np/handle/123456789/15439
Title: | An Empirical Evaluation of Algorithms for solving Subset Sum Problem in terms of Total Bit Length |
Authors: | Shrestha, Rajendra |
Keywords: | Backtracking;Dynamic programming;Total bit length;Subset sum problem |
Issue Date: | 2015 |
Publisher: | Department of Computer Science & Information Technology |
Institute Name: | Central Department of Computer Science and Information Technology |
Level: | Masters |
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 |
URI: | https://elibrary.tucl.edu.np/handle/123456789/15439 |
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.