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. Consider the following representation of a binary tree: an empty tree is represented by the atom nil, and a non-empty binary tree is represented as a tuple {Value,Left,Right}, where Value is the node value, Left is the left subtree, and Right is the right subtree. Write the following functions and predicates on binary trees:

    • inorder(BTree): a function that returns the in-order traversal of BTree as a list.
    • bst(BTree): a predicate that tests if BTree is a binary search tree.
    • lookup(BTree,Val): a predicate that test if a given value occurs in a binary search tree.

12. 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?

13. Write a program to evaluate arithmetical expressions that use + and * applied to nonnegative integer arguments. Expressions are in reverse-Polish notation, e.g., 3 4 + 5 *, 1 3 + 5 7 + *.

14. 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)?

15. subsets(S,N): return the set of N-element subsets of S.

16. max_subarray(Arr): return a contiguous subarray within Arr which has the largest sum.

17. 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 a program in Picat to solve this problem.