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
Write a piece of pseudocode that takes a number entered by the user and prints out every number from that number up to 100 and then prints END.
Create a class name Tape that includes fields for length and width in inches and properties for each field. Also include a ToString () method that returns a string const
Given the right triangles described below, write a program to compute the lengths of the remaining sides using a program. Determine if the following triangles are right-angled
Create an XHTML document with the JavaScript code to open and build the DOM tree for orders.xml as in the seminar, but them also loads in and builds another DOM tree for ano
Write an anonymous block that places a substitution variable (&) into a local variable of type varchar2. You will need to convert the types and round them to nearest tens un
Create a program which computes a person's body mass index? Design a modular program that calculates and display a person's body mass index (BMI).
Write complete PAYROLL program for a company in which each employee falls into one of 3 categories - Administrative, Factory Employee or Salesperson.
Create the class Polynomial. Internal representation of the Polynomial is the array of terms. Each term contains the coefficient and the exponent.