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
In the video clip, the monkey is moving. Firstly, red markers create on head, body, hands and feet of monkey. And then track the monkeys' movement with calculating the cente
Application should be adaptive enough to render on multiple devices with various form factors. To make customer experience best advanced capabilities like geo-location, augmen
Browse the Web and choose a site that could benefit from box properties available in CSS. Make a screen capture of the page and indicate how you would change border and sp
Write a program which bounces the blue ball inside JPanel. Ball must begin moving with the mousePressed event. When ball hits edge of JPanel, it must bounce off edge.
Graphics provide significant richness to the user experience on web sites. Discuss how each of these sites uses graphics in good or poor ways.
Create the logic for a program that accepts input values for the projected cost of a vacation and the number of months until vacation. A summary of the technical experiences
Create an interface DisplayCharacters and another class ShapeCharacter. ShapeCharacter contains a method for displaying either the default alphabet or the user's selected c
Design the logic for an application that allows a user to enter an ordered item continuously until a sentinel value is entered. After each item, display its price or the