+1-415-670-9189
info@expertsmind.com
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
where
  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
 
Minimize


Ask Question & Get Answers from Experts
Browse some more (Programming Languages) Materials
This assignment introduces you to the Perl language and CGI programming. You will use your scripting and html skills to build a Perl program that will gather user input to t
Write a recursive method that searches a string for a Byrd. A Byrd has the following properties. Its first character is an 'A'. If it is a two character Byrd then its
Write a program that calculates how much a person earns in a month if the salary is one penny the first day, two pennies the second day, four pennies the third day.
Write a program to find the common songs in these lists. Let user enter the list sizes n and m and the songs. While testing your program for submission, make sure that the l
Write a program which will read the unspecified number of positive numbers from keyboard and determine the sum and average of these numbers.
One use case is to make a flight reservation. List all other use cases at a comparable level of abstraction. Summarize the purpose of each use case with a sentence.
Design a project to allow a student to access current grades and/or create a "What-if" situation on a continuing basis to understand where they are at any given point in the
Write down program which asks user to enter number between 1 and 100. Use input validation to make sure that a valid number is entered before continuing program.