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…
Contents
INTRODUCTION
CHAPTER 1: PROBLEM DEFINITION/GOALS
1.1 Research discipline and application area
1.2 Challenge/Problem focus
1.2.1 Problems or Research Questions
1.2.2 Why problem or questions are important
1.3 Goal/Results
1.3.1 Our Contribution
CHAPTER 2: BACKGROUND
2.1 Functional Programming
2.2 Evolution of Functional Languages
2.2.1 Lambda Calculus
2.2.2 Haskell
2.2.2.1 Goals and Principles for Haskell design
2.3 DNA array data analysis
2.3.1 Oligonucleotide fingerprinting
2.4 NP Problems
2.4.1 The NP-hardness of CMV(2)
2.4.2 Solution for hard problems
2.4.3 Relaxation on polynomial time solution
2.4.4 Non generic solution
2.5 Approximation algorithm
2.5.1 Approximation of CMV(p)
2.6 Graphs theory
2.6.1 Order of Graph
2.6.2 Degree of Vertex
2.6.3 Types of Graph
2.6.4 Undirected graphs
2.6.5 Directed graphs
2.6.6 Bipartite graphs
2.6.7 Complete bipartite graph
2.7 Imperative languages
2.7.1 Foundation Imperative Languages
CHAPTER 3: METHODOLOGY
3.1 Research framework
3.2 Conceptual Framework
3.2.1 No dependence on a single theory
3.2.2 Involving various aspects of practitioner’s knowledge
3.2.3 Practitioner’s arguments to address a certain problem
3.3 Data validation
CHAPTER 4: DATA COLLECTION
4.1 Preparation Work
4.2 Technology choice
4.3 Relevance, Originality, and Validity of Study
CHAPTER 5: DISCUSSION/ANALYSIS
5.1 Previous Work
5.2 Our Contribution
5.3 Algorithm Explanation
5.4 Findings of Study
5.4.1 Syntax
5.4.2 Way of Thinking
5.4.3 List/Set Operations
5.4.4 Approximate Algorithms
5.4.5 List Comprehension
5.4.6 Pattern Matching
5.4.7 Code Extension / Reusability
5.4.8 Algebraic Data Type
5.4.9 Lazy Evaluation
5.4.10 Readability
CHAPTER 6: CONCLUSIONS & FUTURE WORKS
REFERENCES
APPENDIX A
APPENDIX B
Author: Muhammmad Imran Shafi, Muhammad Akram
Source: Blekinge Institute of Technology
Download URL 2: Visit Now