Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Functional Approach towards Approximation Problem
Blekinge Institute of Technology, School of Engineering, Department of Interaction and System Design.
Blekinge Institute of Technology, School of Engineering, Department of Interaction and System Design.
2008 (English)Independent thesis Advanced level (degree of Master (Two Years))Student thesis
Abstract [en]

Approximation algorithms are widely used for problems related to computational geometry, complex optimization problems, discrete min-max problems and NP-hard and space hard problems. Due to the complex nature of such problems, imperative languages are perhaps not the best-suited solution when it comes to their actual implementation. Functional languages like Haskell could be a good candidate for the aforementioned mentioned issues. Haskell is used in industries as well as in commercial applications, e.g., concurrent applications, statistics, symbolic math and financial analysis. Several approximation algorithms have been proposed for different problems that naturally arise in the DNA clone classifications. In this thesis, we have performed an initial and explorative study on applying functional languages for approximation algorithms. Specifically, we have implemented a well known approximate clustering algorithm both in Haskell and in Java and we discuss the suitability of applying functional languages for the implementation of approximation algorithms, in particular for graph theoretical approximate clustering problems with applications in DNA clone classification. We also further explore the characteristics of Haskell that makes it suitable for solving certain classes of problems that are hard to implement using imperative languages.

Place, publisher, year, edition, pages
2008. , 57 p.
Keyword [en]
Approximation algorithms, functional languages, imperative languages, bipartite graph, Haskell
National Category
Computer Science
Identifiers
URN: urn:nbn:se:bth-1245Local ID: oai:bth.se:arkivex36A305F7044FE452C12574D10058BC6DOAI: oai:DiVA.org:bth-1245DiVA: diva2:828408
Uppsok
Technology
Supervisors
Note
Muhammad Imran Shafi: 29A Sodergatan 19547 Marsta, 0737171514, Muhammad Akram C/O Saad Bin Azhar Folkparksvagen 20/10 Ronneby, 0762899111Available from: 2015-05-22 Created: 2008-09-27 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

fulltext(364 kB)41 downloads
File information
File name FULLTEXT01.pdfFile size 364 kBChecksum SHA-512
b66af1c07a35359ebcd92f5626dae4d4510f072bbb3d97bc7023f2236f268c30c65a2c1ee091619993c91c4900b4a492dde74665728cf766f4a44a0a1835159d
Type fulltextMimetype application/pdf

By organisation
Department of Interaction and System Design
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 41 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 39 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf