Write a haskell program to calculates a balanced partition
Course:- Programming Languages
Reference No.:- EM13167

Assignment Help
Expertsmind Rated 4.9 / 5 based on 47215 reviews.
Review Site
Assignment Help >> Programming Languages

Write a program in Haskell which calculates a balanced partition of N items where each item has a value between 0 and K such that the difference b/w the sum of the values of first partition, S1, and the sum of the values of the second partition, S2, is minimized. Each partition does not have to have the same number of elements.

One classical way to do this is by using dynamic programming. For dynamic programming to be efficient you should avoid recalculating intermediate results. This can be tricky in a functional language as it does not store state information. The solution is data memorization. Intermediate results are stored is a data structure when they are initially calculated and then simply retrieved when needed.

Here is an example of data memorization in calculating a Fibonacci number.

import Data.Array

fibonacci :: Integer -> Integer
fibonacci n = memo!n
  memo = array (0, n) [ (i, fib i) | i <- [0..n] ]
  fib 0 = 0
  fib 1 = 1
  fib i = memo!(i-1) + memo!(i-2)

This example uses the Array module. Since Haskell is a lazy programming language it only calculates a function when it is needed.

Implement a solution to the balanced partition in Haskell.

Put your comment

Ask Question & Get Answers from Experts
Browse some more (Programming Languages) Materials
Identify two key OO concepts and explain them as if you were communicating with a nonprogrammer with a limited technology background, using non-programming, non-computing, r
CMS Systems, Inc. is a company that provides information systems consulting services to companies in the telecom industry in the United States and the United Kingdom. create
You will implement the calculator using stacks and queues. Your calculator should support following operators: Parenthesis. The input will be given in form of infix expression
EENG 330: Microelectronics - Create a frequency vector called, omega which has one row and whose columns contain the elements 0.0, 0.02, 0.04, ..., 7.0 such that MATLAB does
Write program to compute volume flow rate in cubic feet per second of water flowing through pipe of diameter d in inches and a velocity of v feet per second.
Use the Internet to research the advantages, features, and common examples of OOP and EDP. Note: You may use the Association for Computing Machinery (ACM) Digital Library to
Write an HTML form that prompts the user to enter a value. In PHP, write a script to determine whether the value contains an integer , a decimal-place number.
Application Development and Programming Languages,  Programming languages have evolved since the First Generation Languages (1GLs) in the 1940s. The 1GLs were machine language