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

Assignment Help
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
Create a binary image at least 64x64 in dimensions. Using Octave's existing functions, perform Average, Gaussian and Laplacian filters on the image. Display the original imag
In this, you are required to write the function which takes string as its input, chops sentence into words, and for each word, capitalizes the rst letter
Consider a program to enter codes of one to eight characters along with an associated telephone number and associated notes. A code can represent a person's name, a person'
you can use the instructions 'blt' (branch on less than), 'ble' (branch on less or equal), 'bgt' (branch on greater than) and 'bge' (branch on greater or equal) - Translate
Write a program that will ask the user to enter 4 quiz scores for 3 students.  You will need to fine the lowest quiz grade and drop it out when you calculate the average
Given two int variables, firstPlaceWinner and secondPlaceWinner , write some code that swaps their values. Declare any additional variables as necessary.
Write a program that prompts the user for two numbers, finds the sum and difference for those numbers and displays a descriptive label for each computation by calling two di
Write down the C++ program which asks the user to enter 12 temperatures for each month in year and store them in one-dimensional array called "temps".