Average case analysis of algorithms for the maximum subarray problem

Simple item page
dc.contributor.authorBashar, Mohammad Ehsanulen
dc.date.accessioned2008-09-07T22:50:57Z
dc.date.available2008-09-07T22:50:57Z
dc.date.issued2007en
dc.description.abstractMaximum Subarray Problem (MSP) is to find the consecutive array portion that maximizes the sum of array elements in it. The goal is to locate the most useful and informative array segment that associates two parameters involved in data in a 2D array. It's an efficient data mining method which gives us an accurate pattern or trend of data with respect to some associated parameters. Distance Matrix Multiplication (DMM) is at the core of MSP. Also DMM and MSP have the worst-case complexity of the same order. So if we improve the algorithm for DMM that would also trigger the improvement of MSP. The complexity of Conventional DMM is O(n³). In the average case, All Pairs Shortest Path (APSP) Problem can be modified as a fast engine for DMM and can be solved in O(n² log n) expected time. Using this result, MSP can be solved in O(n² log² n) expected time. MSP can be extended to K-MSP. To incorporate DMM into K-MSP, DMM needs to be extended to K-DMM as well. In this research we show how DMM can be extended to K-DMM using K-Tuple Approach to solve K-MSP in O(Kn² log² n log K) time complexity when K ≤ n/log n. We also present Tournament Approach which solves K-MSP in O(n² log² n + Kn²) time complexity and outperforms the K-Tupleen
dc.identifier.urihttp://hdl.handle.net/10092/1194
dc.identifier.urihttp://dx.doi.org/10.26021/3213
dc.language.isoen
dc.publisherUniversity of Canterbury. Computer Science and Software Engineeringen
dc.relation.isreferencedbyNZCUen
dc.rightsCopyright Mohammad Ehsanul Basharen
dc.rights.urihttps://canterbury.libguides.com/rights/thesesen
dc.subjectMaximum Subarray Problemen
dc.subjectDistance Matrix Multiplicationen
dc.subjectAll Pairs Shortest Path Problemen
dc.subjectShortest Pathen
dc.subjectExpected Timeen
dc.subjectAverage Timeen
dc.subjectAverage Case Analysisen
dc.subjectBinary Heapen
dc.subjectPrefix Sumen
dc.subjectDirected Acyclic Graphen
dc.subjectX + Y Problemen
dc.subjectBinary Tournament Treeen
dc.subjectSolution Seten
dc.subjectMSPen
dc.subjectK-MSPen
dc.subjectDMMen
dc.subjectK-DMMen
dc.subjectAPSPen
dc.subjectK-Tupleen
dc.titleAverage case analysis of algorithms for the maximum subarray problemen
dc.typeTheses / Dissertations
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorUniversity of Canterburyen
thesis.degree.levelMastersen
thesis.degree.nameMaster of Scienceen
uc.bibnumber1064310en
uc.collegeFaculty of Engineeringen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_fulltext.pdf
Size:
757 KB
Format:
Adobe Portable Document Format
Download
Collections
Engineering: Theses and Dissertations