Inlämning av Examensarbete / Submission of Thesis

Muhammmad Imran Shafi; Muhammad Akram MCS-2008-34, pp. 57. TEK/avd. för interaktion och systemdesign, 2008.

The work

Författare / Author: Muhammmad Imran Shafi, Muhammad Akram,
Titel / Title: Functional Approach towards Approximation Problem
Abstrakt Abstract:

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.

Ämnesord / Subject: Datavetenskap - Computer Science\Artificial Intelligence
Datavetenskap - Computer Science\Electronic Security
Nyckelord / Keywords: Approximation algorithms, functional languages, imperative languages, bipartite graph, Haskell

Publication info

Dokument id / Document id:
Program:/ Programme Magisterprogram i Datavetenskap/MSC in Computer science
Registreringsdatum / Date of registration: 09/27/2008
Uppsatstyp / Type of thesis: Masterarbete/Master's Thesis (120 credits)


Handledare / Supervisor: Mia Persson
Examinator / Examiner: Guohua Bai
Organisation / Organisation: Blekinge Institute of Technology
Institution / School: TEK/avd. för interaktion och systemdesign
S-372 25 Ronneby
+46 455 38 50 00
Anmärkningar / Comments:

Muhammad Imran Shafi: 29A Sodergatan 19547 Marsta, 0737171514,
Muhammad Akram C/O Saad Bin Azhar
Folkparksvagen 20/10 Ronneby, 0762899111