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
Program should print out percentage of correct answers of each students. At end of exam, program print percentage of students which passed exam.
Define some everyday if else statements you use to determine action. What are the branches of your statement? What are the relational and Boolean operators you used in your ex
In this programming assignment, you are asked to simulate the recursive factorial function given in the class. Your program is to be a nonrecursive version of the factorial
Write the program which simulates checkout line at supermarket. Line is a queue object. Customers( i.e customer objects) arrive in random integer intervals of 1-4 minutes.
Enter your C++ instructions into a source file named Introductory11.cpp. Also enter appropriate comments and any additional instructions required by the compiler. Displa
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
The first programming project involves writing a program that merges two files that contain polynomials. To merge two files, the input files must be in sorted order.
Write a program which permits a user to enter any number of integers, which are then stored in the array. After user enters integers, perform the following operations on arr