Sample Problems -- CMSC 331 -- Spring 25

Stuff to Study and/or Think About

	
1.  What are the types of the following:

    fun zed x = x + 1.0;
 
    fun zwop f g (a,b) = (f (g a), g (f b));

    fun f [] = 0 |
        f (a::b) = a + (f b);

    fun that [] = [] |
        that ((a,b)::l) = ((a+1)==b)::that(l);

2.  Write a ML function to find the smallest int in a int list.

3.  Use a truth table to show that    ~(A \/ B) =  (~A /\ ~B)

4.  Write a grammar which generates all of the sentences  (ab)^n(ba)^n
    (strings like:  abba ababbaba  ababababbabababa, where n>0)

5)  Write the ML code to implement the queue Data Structure:
     
     front(empty) = ERROR     deq(empty) = empty
     front(enq(a,S)) = a      deq(enq(a,S)) = S

6)  Write a BNF grammar for the lambda calcuulus.
 
    Then, write an EBNF version.

7)  Write a ruby function to sort a list of strings.

8) Assuming x & y are both ints, determine the weakest precondition for:

if (x > y)
  then y = 3*x + 2
  else y = 3*x - 2
end
{ y > 3 }


9) compare and contrast:  check & unchecked exceptions


10) Given the definitions:
     2 = \f . \x. f (f x)
     plus = \m. \n. \f. \x. m f (n f x)

     compute the value of (plus 2 1)

11) To allow a function to change a parameter value, pointers must be used.  Discuss.

12) Compare and contrast cooperative/competitive synchronization.

13) Give two reasons why languages need to provide support for concurrency.

14) Write a Prolog function which finds the third item in a list (or 0 if the list is too short).
SO:
third([1,2,3],X) would return X=3
third([1,2,3,4],X) would return X=3
third([],X) would return X=0

15) Why do many languages allow multiple catches in a try-catch construct?

16) Semaphores are made up of what two primary structures?  (that is:  the data, not the functions!)

17) Which types of parameters (in/out/in-out) can be used in a recursive function.

18) What features of HDFS are used to make Map-Reduce more efficient?

19) input = LOAD 'files.txt' USING PigStorage() AS (name, year, ave:float);
What is the schema (type spec) of the "input" relation?