Path complexity of maximum segment sum problem
Various software complexity metrics have been proposed in literature. A program complexity measure called path complexity is proposed in . Path complexity P(A,n) of an algorithm A is defined to be the number of program execution paths of A over all inputs of size n. It defines a partition of input space of program A into equivalence classes on the basis of different program execution paths. All the inputs belonging to an equivalence class are equivalent to each other in a sense that they follow same execution path. We present path complexity analysis of four different algorithms for one-dimensional maximum segment sum problem which shows that algorithms with different computational complexity may be equivalent to each other in their path complexity. We also present lower bounds on one dimensional as well as two dimensional maximum segment-sum problems. A different perspective and several observations on one dimensional problem are given
- M Tech Dissertations 
Showing items related by title, author, creator and subject.
Vora, Dhairya (Dhirubhai Ambani Institute of Information and Communication Technology, 2011)Cloud computing refers to the provision of computational resources on demand. Resource allocation is an important aspect in cloud computing. Cloud user asks for resources in terms of a lease. Lease stores the information ...
Limbachiya, Dixita (Dhirubhai Ambani Institute of Information and Communication Technology, 2019)Bio-computing uses the complexes of biomolecules such as DNA (Deoxyribonucleic acid), RNA (Ribonucleic acid) and proteins to perform the computational processes for encoding and processing the data. In 1994, L. Adleman ...
Joshi, Ashwini Kumar (Dhirubhai Ambani Institute of Information and Communication Technology, 2008)In spite of the many defense techniques, software vulnerabilities like buffer overflow, format string vulnerability and integer vulnerability is still exploited by attackers. These software vulnerabilities arise due to ...