Assignment 6: Programming Exercises (in Picat)

  1. sphere_volume(r) : a function that computes the volume of a sphere, given its radius r.

  2. quadratic_equation(a,b,c): a function that computes the real roots of a given quadratic equation a*X^2+b*X+c=0.

  3. number_of_zeros(lst): a function that returns the number of zeros in a given simple list of numbers lst.

  4. draw_pascal(n): a function that takes an integer n as a parameter and prints the first n rows of the Pascal's triangle.

  5. euler(): returns the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0, where each "_" is a single digit.

  6. days(date1,date2): a function that takes two dates, date1 and date2, in some format, and returns the number of days from date1 to date2, inclusive.

  7. remove_consecutive_dups(lst): return a copy of lst with consecutive duplicates of elements eliminated. For example, for lst = [a,a,a,a,b,c,c,a,a,d,e,e,e,e], the returned list is [a,b,c,a,d,e].

  8. remove_dups(lst): return a copy of lst with duplicates of elements eliminated. For example, for lst = [a,a,a,a,b,c,c,a,a,d,e,e,e,e], the returned list is [a,b,c,d,e].

  9. replicate(lst,n): Replicate each of the elements of lst a given number of times. For example, for lst = [a,b,c] and n = 3, the returned list is [a,a,a,b,b,b,c,c,c].

  10. split_list(lst,n): split lst into two parts with the first part having n elements, and return a list that contains these two parts.

  11. min_max_median(lst): a function that takes a simple list of numbers lst as a parameter and returns a list with the min, max, and the median of lst. Can you devise an algorithm that has an expected linear running time?

  12. bc(n,k): return the binomial coefficient "n choose k". Can you figure out a method that is less likely to cause an overflow than using the formula (n*(n-1)*...*(n-k+1))/(k*(k-1)*...*2)?

  13. subsets(s,n): return the set of n-element subsets of s.

  14. max_subarray(arr): return a contiguous subarray within arr which has the largest sum.

  15. There are 3 water jugs. The first jug can hold 3 liters of water, the second jug can hold 5 liters, and the third jug is an 8-liter container that is full of water. At the start, the first and second jugs are empty. The goal is to get exactly 4 liters of water in one of the containers. Write two programs in Picat to solve this problem, one treating it as a constraint satisfaction problem and the other modeling it as a planning problem.