CMSC331 0101 Final

The CMSC331 final for section 0101 for the Fall 2002 semester will be given on Tuesday, 17 December from 1:00pm to 3:00pm in our regular classroom. It will be a closed book exam. The exam will cover all of the material in the course, however the emphasis will be on the material we've covered since the midterm examination.

The syllabus gives the topics we covered. You are responsible for all of the material in the assigned readings mentioned in the syllabus as well as material covered in class. Copies of the slides used in class are online and linked to the syllabus.

Below are some questions and problems that you can use in preparing for the final. You should also look at the final used in Fall 2000.

General topics

Here is a list of topics that you should be familiar with. You should:

• Be able to explain the difference between high level and low level languages

• Be able to name four benefits provided by high level languages

• Be able to explain the difference between a compiler and an interpreter

• Understand the basic difference between semantics and syntax

• Understand the difference between prefix, postfix and infix notation

• Understand operator precedence and associatively

• Be able to write a simple BNF grammar for a language described in English.

• Be able to show a parse tree given a grammar and a string in that language

• Be able to prove that a BNF grammar is ambiguous and to show how to change it to remove the ambiguity.

• Be able to explain what an invariant is and be able to identify them in an algorithm

• Know the difference between a data object and data representation

• Understand the difference row-major and column-major layouts for multidimensional arrays

• Be able to explain the differences between records and arrays

• Understand unions and why they are not type safe

• Understand pointers: why they are used and the problems they bring

• Understand type checking and type equivalence

• Be able to illustrate the difference between lexical and dynamic scope

• Be able to explain different kinds of polymorphism and give an example of each

• Be able to explain several benefits of inheritance

• Be able to explain the idea of exceptions and how they work in Java

• Be able to explain the idea of garbage collection and why it's useful

• Be able to explain interfaces in Java and the idea of interfaces as "adjectives" (e.g. class Foo implements Sortable) and why coding "to an interface" increases code reusability

• Be able to compared and contrast procedural (e.g. C) programming with object oriented programming

• Be able to compare and contrast functional and imperative programming languages

• Understand that functional programming is expression-oriented programming and that programs are expressions that evaluate to values

• Be able to understand simple programs written in java, Lisp and ML (section 0101) or Prolog (section 0201)

• Be able to define basic data structures using Lisp lists and to write simple recursive list processing functions.

• Be able to write simple programs written in Java, Lisp and ML (section 0101) or Prolog (section 0201)

• Understand that programming languages are simply tools that we use to do our job of solving problems!

General Concepts

• Define tail recursion. Why is it of interest.

• Give three examples of "programming paradigms" and, for each one, identify a programming language that typifies it.

• Design patterns and interfaces
  • An important concept is the idea of interfaces, that is, the only thing one object should know about another object is the interface it implements. Give examples from a few design patterns that exemplify the interface idea.
  • Many objects will implement several interfaces but another object might only know one of the interfaces it implements. Explain why is is useful to structure things this way. Give an example of a situation where this would happen.

• You are developing a program and must choose between two imperative languages, one of which is interpreted and the other of which is compiled. Under what conditions should you use one instead of the other? Under what conditions does your choice not matter? Cover the following (mutually exclusive) conditions:
  1. You're in a hurry to make the program work.
  2. The program must execute efficiently and with maximal speed.
  3. The program must occupy very little memory.
  4. The program needs a lot of dynamic memory.
  5. The program is huge.
  6. The program is small.
  7. The program must be ported to a lot of machines.

• True or False: In any object-oriented programming language, if object a is an instance of class A, and object b is an instance of class B, and B is a subclass of A, then the amount of data in b is less than or equal to the amount of data in a. Why is this true or false?

• For each of C++, Java, and Lisp, give: (1) An application that is well-suited to this language (e.g., Device Drivers to C++) (No, you can't use that example), (2) What needs of the application make it well-suited to the language (e.g., need for low-level, fast code), (3) What characteristics of the language match the needs of the application (e.g., C++ lets you manipulate memory efficiently).
• Give three examples of functions or services that an IDE provides. List two advantages and one disadvantage of using an IDE like bluej.

Languages, parsing and grammars

• What does YACC stand for? What does LEX stand for?

• Give an example of a language that can not be recognized by a context free grammer?

• Give an example of a language that can not be recognized by a gegular grammar but can be recognized by a context free one.

• A finite language is one which has a finite set of sentences. Can any finitie language be recognized by a regular expression?

• Give LEX and YACC files for English ("Standard American" dialect). Use the back of the page if neccessary.

• Describe how a recursive descent parser works.

• Consider the following BNF grammar:

1. (extra credit) Describe the semantics of the following faces:
   1. :+Q
   2. D-;|
• Write a context-free grammar using EBNF for each of the following languages.
  • All binary numbers with 1 or more digits that are palindromes. A palindrome is a sequence of characters that has the exact same sequence when read from left-to-right as it does from right-to-left. E.g., ``101'' and ``0110'' are palindromes.
  • All sequences of vowels that include exactly one occurrence of the letter ``e'' and whose length is >0. Do not include the letter ``y'' as a vowel.

Java

• Which of the following are keywords in Java. Select the two correct answers.
1. friend
2. NULL
3. implement
4. synchronized
5. throws
• Which of the following are Java keywords. Select the four correct answers.
1. super
2. strictfp
3. void
4. synchronize
5. instanceof
• Which of these are Java keywords. Select the five correct answers
1. TRUE
2. volatile
3. transient
4. native
5. interface
6. then
7. new
• What is the "sandbox" model of execution? Where and why is it employed in Java?
• Java programs fall into one of two categories: applications and applets. Explain the major differences between the two. Give an example class definition (i.e., the line that includes the word "class") for each.
• Java's event model is used heavily in providing GUI (Graphical User Interface) support. Explain the principles of the event model. Illustrate your explanation by describing how a program could respond to a Button that a user might press.
• What is "the AWT"? SWING? How do they differ?
• Explain why, as a general principle, the attributes of a class should be declared private or protected.
• An array containing the first 5 prime numbers is required as part of a class. Write a single line of code that declares and initialises the array together with ensuring its values can't be changed subsequently.
• Write a method getValidAge() that reads a valid age for a human being from the user (keyboard). The method should have the following signature: public static int getValidAge() A valid age is one considered to be between 0 and 125 inclusive.
• What's a design pattern? What's it good for?
• Why would anyone ever want to use Model-View-Controller pattern? Why would anyone ever not want to use Model-View-Controller pattern?
• Programming Language Comparison. To the left of each of the following language features, write the word Java if Java provides the feature but C++ does not, C++ if C++ provides the feature but Java does not, both if both Java and C++ provide the feature, or neither if neither Java nor C++ provide the feature.

     1. __________ a common ancestor for all classes
     2. __________ built-in graphics
     3. __________ call by reference
     4. __________ call by value
     5. __________ compilers that automatically correct all program
     errors
     6. __________ garbage collection
     7. __________ inheritance
     8. __________ multiple inheritance
     9. __________ operator overloading
    10. __________ parameterized types 
    11. __________ function closures
    12. __________ type inferencing
  

• Which of the following statements are correct. Select the four correct answers.
1. A Java program must have a package statement.
2. A package statement if present must be the first statement of the program (barring any comments).
3. If a Java program defines both a package and import statement, then the import statement must come before the package statement.
4. An empty file is a valid source file.
5. A Java file without any class or interface definitions can also be compiled.
6. If an import statement is present, it must appear before any class or interface definitions.
• Suppose that the following code appears in a Java program:

  if (x instanceOf Foo)
     throw new IllegalArgumentException("Foo");
  

  This code is not in a try/catch block, and IllegalArgumentException does extend RuntimeException. Is the following statement true or false: The method that uses this code must have a throws clause after its parameter list, otherwise there will be a compilation error.

• Suppose that Foo is a Java class that extends Thread, and f is a Foo object. What is the primary difference between activating f.run( ) verses activating f.start( )?
• What gets displayed on the screen when the following program is compiled and run. Select the one correct answer.

  
  protected class example {
  	public static void main(String args[]) {
  		String test = "abc";
  		test = test + test;
  		System.out.println(test);
  	}
  }
  
  

  1. The class does not compile because the top level class cannot be protected.
  2. The program prints "abc"
  3. The program prints "abcabc"
  4. The program does not compile because statement "test = test + test" is illegal.

• Select the one most appropriate answer. A top level class without any modifier is accessible to -

  1. any class
  2. any class within the same package
  3. any class within the same file
  4. any subclass of this class.
• True or False: In Java an abstract class cannot be sub-classed.
• True or False: In Java a final class must be sub-classed before it can be used.
• Which of the following are true: Select the three correct answers.

  1. A static method may be invoked before even a single instance of the class is constructed.
  2. A static method cannot access non-static methods of the class.
  3. Abstract modifier can appear before a class or a method but not before a variable.
  4. final modifier can appear before a class or a variable but not before a method.
  5. Synchronized modifier may appear before a method or a variable but not before a class.
• What method modifier makes the method available to all classes in the same package and to all the subclasses of this class?
• What gets printed on the standard output when the class below is compiled and executed by entering "java test lets see what happens". Select the one correct answer.

  
  public class test {
     public static void main(String args[]) {
        System.out.println(args[0]+" "+args[args.length-1]);
     }
  }
  
  

1. The program will throw an ArrayIndexOutOfBounds exception.
2. The program will print "java test"
3. The program will print "java happens";
4. The program will print "test happens"
5. The program will print "lets happens"
• What gets printed on the standard output when the class below is compiled and executed by entering "java test lets see what happens". Select the one correct answer.

  
  public class test {
     public static void main(String args[]) {
        System.out.println(args[0]+" "+args[args.length]);
     }
  }
  
  

1. The program will throw an ArrayIndexOutOfBounds exception.
2. The program will print "java test"
3. The program will print "java happens";
4. The program will print "test happens"
5. The program will print "lets happens"
• What all gets printed on the standard output when the class below is compiled and executed by entering "java test lets see what happens". Select the two correct answers.

  
  public class test {
     public static void main(String args[]) {
        System.out.println(args[0]+" "+args.length);
     }
  }
  
  

1. java
2. test
3. lets
4. 3
5. 4
6. 5
7. 6
• What happens when the following program is compiled and run. Select the one correct answer.

  
  public class example {
     int i = 0;
     public static void main(String args[]) {
        int i = 1;
        i = change_i(i);
        System.out.println(i);
     }
     public static int change_i(int i) {
        i = 2;
        i *= 2;
        return i;
     }
  }
  
  

1. The program does not compile.
2. The program prints 0.
3. The program prints 1.
4. The program prints 2.
5. The program prints 4.
• What happens when the following program is compiled and run. Select the one correct answer.

  
  public class example {
     int i = 0;
     public static void main(String args[]) {
        int i = 1;
        change_i(i);
        System.out.println(i);
     }
     public static void change_i(int i) {
        i = 2;
        i *= 2;
     }
  }
  
  

1. The program does not compile.
2. The program prints 0.
3. The program prints 1.
4. The program prints 2.
5. The program prints 4.
• What happens when the following program is compiled and run. Select the one correct answer.

  
  public class example {
     int i[] = {0};
     public static void main(String args[]) {
        int i[] = {1};
        change_i(i);
        System.out.println(i[0]);
     }
     public static void change_i(int i[]) {
        i[0] = 2;
        i[0] *= 2;
     }
  }
  
  

1. The program does not compile.
2. The program prints 0.
3. The program prints 1.
4. The program prints 2.
5. The program prints 4.
• What happens when the following program is compiled and run. Select the one correct answer.

  
  public class example {
     int i[] = {0};
     public static void main(String args[]) {
        int i[] = {1};
        change_i(i);
        System.out.println(i[0]);
     }
     public static void change_i(int i[]) {
        int j[] = {2};
        i = j;
     }
  }
  
  

1. The program does not compile.
2. The program prints 0.
3. The program prints 1.
4. The program prints 2.
5. The program prints 4.
• A thread-safe program works correctly with multiple threads operating simultaneously. What is the relationship (if any) between thread-safeness and mutual exclusion? Is thread-safeness a property of a program or a process? Explain. Describe two mechanisms intended to deal with the issue of mutual exclusion between threads.

Lisp

• What does (weird 1) return given this definition:

       (defun weird (i) (let ((i (* i 2))) (let ((i (* i 3))) i))) 

• Given the Lisp functions

  (defun w1 (i) (setq i 1) i)
  (defun w2 (i) (setf (car i) 2) 'i)
  (defun w3 () (let ((i 3) (j '(4 5))) (w1 i) (w2 j) (list i j)))
  

  what are the values of (w1 3), (w2 '(4 5)), and (w3)?

• Consider the function LENGTH which takes a list and returns the number of top-level elements in it. A simple non-tail recursive version can be written as:

       (defun length (l)
       (if (atom l) 0 (1+ (length (cdr l)))))
   

  Write a tail-recursive version. Hint: try completing the following approach:

       (defun length (l)(tail-recursive-length (l 0))
  	 (defun tail-recursive-length (List N) ...)
   

• The builtin Lisp function mapcar applies a function to each element of a list and returns a list of all results. Implement it in Lisp recursively without using any other mapping function or global variables. You may not use `map', `mapc', `mapcan', etc. You will at least need `if', `null', `cons', `car', `cdr', and `apply'. Examples:

  
       (defun add (lst) (+ (car lst) (cadr lst)))
       (mapcar #'add '()) => ()
       (mapcar #'add '((1 2) (3 4))) => (3 7)
       (mapcar #'(lambda (i) (+ i 1)) '(1 2 3 4)) => (2 3 4 5)
  
  

  Write mapcar for 2 arguments only -- don't worry the extra cases described in books.

• Write iota as a LISP function that takes a positive integer as an argument and returns a list of the numbers between 1 and that integer.

       clisp> (iota 5)
       (1 2 3 4 5)
       clisp> (iota 0)
       nil
       clisp> (iota -2)
       nil

• Consider the following Lisp function definition:

(defun mystery (lis a) (cond ((null lis) a) (t (mystery (cdr lis) (cons (car lis) a))) ))

Give the values of the following expressions, explaining your reasoning.

1. (mystery '() '(1 2 3 4 5))
2. (mystery '(1 2 3 4 5) '())

• What does y evaluate to in the following and why does this not mean that LISP is call-by-reference?

  
  Clisp> (defun foo (x) (setf (car x) 1))
  
  Clisp> (setf y '(a b c))
  
  Clisp> (foo y)
  
  Clisp> y
  
  
  
  

• Lists to Cons Cells. Draw a box and pointer representation of the following lists: (1 2 3) (((1))(2) 3) (1 . 2) ((()))
• Show the values returned by each of the following expressions.

    > (setq L1 (cons '(1 2) (cons (cons 3 nil) '(4 (5)))))
    
  
    > (car (cdr (cdr L1))
    
    
    > (cdr (car L1))
  
  
  

• Write a simple Lisp function CONTAINS which takes two arguments both of which are arbitrary S-expressions and returns T if the first is equal to or contained somewhere within the second and NIL otherwise. For example:

    > (CONTAINS 'C '(A '(B (C)) D))
    T
    > (CONTAINS 'E '(A '(B (C)) D))
    NIL
    > (CONTAINS '(B (C)) '(A '(B (C)) D))
    T
    > (CONTAINS '(A B) '(A B))
    T
    > (CONTAINS 'A 'A)
    T
    > (CONTAINS '(B (C)) 33)
    NIL
  

• Give at least two reasons why macros are useful in Lisp.
• Write a function, vector-min-max , that returns, as two values, the minimum and maximum element of a vector. Show the value printed by the following code:

  (setf v (vector 1 10 4 7 5))
  (multiple-value-bind (min max) 
    (vector-min-max v) 
    (format t "min ~A max ~A%" min max))
  

• Write a recursive function that returns the depth of the most deeply nested atom of a list. The depth of an empty list is 0, the depth of any atom in a linear list is 1, the depth of any atom in a list inside a list is 2, and so on. You can use the system defined function max that returns the maximum of its arguments. Your function should work like this:

  (maxdepth nil) = 0
  (maxdepth '(a)) = 1
  (maxdepth '(a (b))) = 2
  (maxdepth '(a ((b h) c) j)) = 3
  

• Write a function that takes a list lst and a number n and returns a new list in which the elements of lst are grouped into sublists of length n. The last sublist might be shorter than n if there are no more elements in the list. Example:

  (collect '(a b c d) 2) = ((a b) (c d))
  (collect '(a b c d e) 3) = ((a b c) (d e))
  

• Write a function that takes one argument, a number, and returns the greatest argument passed to it so far [Hint: you need a function that keeps its state] Examples:

  (max-of 3) = 3
  (max-of 5) = 5
  (max-of 1) = 5
  

• You are given the following definitions:

  (defun foo ()
    (let ((x 5))
         #'(lambda (y) (* x y))))
  
  (defun bar ()
    (let ((x 4))
  	 (funcall (foo) 3))) 
  

  Show the value returned by the function call (explain briefly your result): (bar)

• Explain what is wrong with the following definition of pop and rewrite the macro to work correctly:

  (defmacro my-pop (lst)
    `(let ((var (car ,lst)))
          (setf ,lst (cdr ,lst))
          ,var)))
  

• Define a macro my-dolist to work as the system defined macro dolist. Show the result of expanding the macro in the following example:

  (my-dolist (x lst) (format t "~A" x))
  

• Write recursive Lisp functions height and weight each of which take one s-expression and return an integer for the height and weight of their argument, where: takes an s-expression and returns its height, where

  • the height of an atom is 0.
  • the height of a list is one plus the maximum height of any of the elements of the list.
  • the weight of a non-nil atom is 1.
  • the weight of the empty list is 0.
  • the weight of a list is the sum of the weights of its elements.
• A queue is a list data structure in which elements are added to one end and removed from the other end. Thus, in contrast to a stack, which imposes a last-in-first-out (LIFO) ordering on its members, a queue imposes a first-in-first-out (FIFO) ordering on its members. Your task here is to construct an operator in Common LISP for this new abstract data type. This operator is called enqueue, which puts an element on the "back end" of a list. Here's how it works:

       > (setq x '(a b c))
       (A B C)
       > x
       (A B C)
       > (enqueue 'd x)
       (A B C D)
       > x
       (A B C D)
       >
  

  Hint: to modify a list structure by adding newElement to its end, find the last cons cell (lastConsCell) of the list and do something like

       (setf (cdr lastConsCell) (cons newElement nil))

• Write a function called shuffle which takes two lists as input (assume both lists have the same length) and returns one list which contains the first element of the first list followed by the first element of the second list followed by the second element of the first list and so on, like this:

       > (shuffle '(A K Q) '(J 10 9))
       (A J K 10 Q 9)
  

  Write two different versions of this function -- one using iteration and one using recursion.
• Given the following LISP code

       (defun unknown ( L )
          (cond
             ((null L) nil )
             (t (cons (list (cadar L) (caar L))
                      (unknown (cdr L))))))
  

  what is the result of evaluating the following expression?

       (unknown '((1 a) (2 b) (3 c) (4 d) (5 e)))
  

• What is the result of evaluating the following LISP expression?

       ((lambda (x y) (+ x y y 3)) 2 5)
  

• In the following expression, put squares around the free variable references, and circles around the bound variable references. Put lines between the bound references and the places they are bound. Also, show the result returned by each expression.

      (let ((x 1))
        (let ((f (function (lambda (y) (list y x)))))
             (let ((x 2)) (list x (funcall f x)))))
    
      RESULT: 
  

• Many languages have a macro facility. They were first used in assembly languages and helped to relieve some of the tedious and repetitive coding required by assembly language.
  • What is the difference between a macro and a function?
  • Briefly describe the macro facility in Common Lisp.

• Why doesn't this work in Common Lisp:

  (defun bogus (some-function-of-one-argument)
     (some-function-of-one-argument '(a b c)))

• Define a closure. Why is it useful.
• Suppose we define the function adder as:

       (defun adder (n)(lambda (x) (+ x n)))
  

  What should (funcall (adder 10) 5) return. How would you describe what (adder N) returns where N is some number?

• Suppose we define the function curry as:

    (defun curry (function &rest args)
        (lambda (&rest more-args)
           (apply function (append args more-args))))
  

  What should (funcall (curry #'+ 100) 5) return. Can you describe what curry does?

• Consider the problem of creating a strem of the Fibonacci numbers (e.g., 1 1 2 3 5 8 13 ...). The series is defined as fib(1)=1, fib(2)=1 and fib(N)=fib(N-1)+fib(N-2). Write a simple expression that assigns the variable FIBS a value that is an infinte stream of the Fibonacci numbers. (Hint: you can do this easily by binding FIBS to a stream whose first elment is one, whose second element is one, and whose remaining elements are a stream formed by adding the streams FIBS and (SCDR FIBS)).

• To what will each of the following expressions evaluate assuming an environment in which X is 10 Y is 100 and Z is 1000.
  • (* x y)
  • ((lambda (x y) (* x y)) 2 3)
  • ((lambda (x) (* x y)) 2)
  • ((lambda (y) (* x y)) 2)
  • ((lambda () (* x y)) )
• Briefly describe what the following functions does.

  (defun foo (f g)
    (lambda (x) (funcall f (funcall g x))))
  

  What should the arguments F and G be if this function is to make sense? How would you describe the return value of each of these expressions
  • (foo #'1+ #'abs)
  • (foo #'not #'integerp)
  • (foo (lambda (x) (> x 0.5)) (foo (lambda (x) ( + 0.1 x)) #'abs))

Other