Select this to skip to main content [CSUSB] >> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CSci620] >> final [Source]
[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Grading]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Wed May 26 17:13:31 PDT 2004

Contents

    CSci620 Final

      8 questions, 25 points each (12 minutes per answer).

      Preparation

        Bring
      1. At least 10 sheets of blank paper plus two or three writing sticks.
      2. The specification of the language Minsky [ Minsky.html ] because several questions may refer to this LRM.
      3. A single 8.5><11 inch sheet of notes -- -- --(cheatsheet)

      Rubric

       Answer all 8 questions. All questions need long answers and/or short essays.

      Each is worth 25 points.

      Start each question on a new sheet of paper.

      Use both sides.

      Put last 4 digits of SSN/StId on each sheet.

      No access to computers (any machine that can access the Internet or compile, interpret, check, parse, or analyze any computer language discussed in this course).

      No wireless communication.

      I give credit for working and for incomplete answers. Do not erase your working.

      Question Topics Spring 2004

        Presentation
      1. Show that you recall at least one presentation of a term paper made by another student in this class.

        Syntax
      2. Show that you understand BNF, EBNF, Chomski types, ... Parse strings according to given grammar/BNF. Recall mathematical definition of a grammar. Show how to apply productions to calculate strings in a language. Translate EBNF into BNF. Correct a simple ambiguity in BNF.

        Semantics
      3. Given the formal abstract syntax and semantics of an unusual language show how to determine the meaning of a program/expression/statement in the language.

        [ Minsky.html ]

        Translation

      4. Define and relate: lexers, parser, interpreters, compilers, quads, syntax improvement, recursive descent. Given a production write the associated subprogram/function from a typical recursive descent parser or interpreter for it.

        Imperative Languages
      5. Describe effect of Von Neumann architecture on imperative languages. Provide names of typical imperative languages. Show how a given imperative language fits the paradigm. List differences between two imperative languages. Describe features of imperative languages: I/O, arithmetic, GOTOs, control structures, loops, special commands/directives, data structures, records, pointers, runtime errors, functions and procedures, activation records and the run time stack, parameter passing. Give a rough translation of a small FORTRAN program into a language like C++ or Java with only approximate I/O formatting.

        Object-Oriented Languages
      6. Explain why OO languages evolved: what needs did they meet? Use imperative+>OO transition as an example of language evolution. Describe the features that distinguish OO from imperative, Give examples of OO features in a language like C++, Java, or C#(your choice). Compare C++ and Java. Describe 2 or 3 features in Java that serve concurrency. Give an example of a difficulty with concurrent programming that does not occur in normal programs. Show how to express a simple data structure (stack, queue,...) in an OO language. How successful was the shift from imperative to OO paradigm? Write a short essay on the future of C++(or Java) that states your opinions and gives reasons for them.

        Functional Languages
      7. Name the most Long lasting and famous functional language, and its two main variants. Describe LISP data in terms of C++/Java. Describe S-expressions and give examples. Explain a COND function in terms of C++/Java. Given a small LISP function definition and a call trace the resulting evaluation. Describe association lists: form of data, typical operations. Describe the Property list: typical function calls. Know whether you can describe the semantics of LISP using LISP as a metalanguage. Show how to express a simple data structure (stack, queue,...) in LISP. Write a short essay on the future of LISP that sates your opinions and gives reasons for them.

        Logic Programming
      8. Describe the propositional calculus,first order (lower) predicate calculus. Give an example of Modus Ponens, truth table, quantifier, predicate, proposition, and connectives. Give an example of a Prolog database containing facts and rules and trace how a typical query accesses these to give results. Given a Prolog program plus some queries, show what Prolog responds. Show how to express a simple data structure (stack, queue,...) in Prolog. Distinguish '=' and 'is' in Prolog -- with examples. Define and trace a Prolog recursive definition.

      Topics/skills not needed in Spring 2004

      1. Axiomatic semantics.
      2. Operational Semantics (not in book)
      3. Improving a given syntax.
      4. Fixed point theory (not in book).
      5. Writing good FORTRAN or Pascal.

    . . . . . . . . . ( end of section CSci620 Final) <<Contents | Index>>

    Glossary

  1. BNF::="Backus-Naur Form", for syntax and grammar, developed by Backus and Naur.
  2. EBNF::="Extended " BNF.
  3. HTML::= "HyperText Markup Language", used on the WWW.
  4. HTML_page::syntax= "<HTML>" head body.
  5. Java::="An " OO " Language from Sun".
  6. LISP::= "LISt Processing Language".
  7. LRM::="Language Reference Manual".
  8. OO::="Object-Oriented".
  9. Prolog::="Programming in Logic".
  10. TBA::="To Be Announced".
  11. UML::="Unified Modeling Language".
  12. URL::=Universal_Resource_Locator,
  13. Universal_Resource_Locator::syntax= protocol ":" location, where
    Net
    1. protocol::= "http" | "ftp" | "mailto" | ... ,
    2. location::= O( "//" host) O(pathname).

    (End of Net)
  14. WWW::= See http://www.csci.csusb.edu/dick/cs620/, index to web site for this class.
  15. XBNF::="eXtreme" BNF, developed by the teacher from EBNF, designed to ASCII input of syntax, semantics, and other formal specifications.

Formulae and Definitions in Alphabetical Order