Exam: What you need to know

Topics

Part I: Programming Languages

1. General introduction to Programming Languages ([SCOTT] chapter 1).

   1. Language design.
   2. Classification of programming languages.
   3. Compilation and interpretation.
   4. Overview of compilation.

2. Clojure fundamentals.

   1. Read, Evaluate, Print, Loop (REPL).
   2. Comments.
   3. Global and local bindings (def, let).
   4. Basic data types (nil, booleans, numbers, strings, characters, symbols, keywords) and their functions: +, +', -, *, *', /, <, <=, =, not=, ==, >, >=, boolean, char, char?, dec, even?, format, inc, keyword?, neg?, nil?, number?, odd?, pos?, quot, rem, str, string?, symbol?, and zero?.
   5. The quote (') special form.
   6. Logic operations: not, and, or. Short-circuit evaluation.
   7. Conditions (if, cond, case). Truthy and falsy values.
   8. Functions. Definition (defn) and application. Parameters. Multi-arity and variadic functions. Docstrings. Anonymous functions and closures. The apply function.
   9. Special forms. How they differ from functions.
   10. Repetitions. Recursion and loop/recur.
   11. Functional programming. Higher-order functions.
   12. Destructuring.

3. Clojure collections.

   1. The concept of sequence.
   2. Sequence functions: butlast, concat, cons, count, cycle, distinct, drop, drop-while, empty?, every?, filter, first, interleave, interpose, iterate, last, map, mapcat, nth, partition, partition-by, range, reduce, remove, repeat, rest, reverse, seq, seq?, some, sort, split-at, split-with, take, and take-while.
   3. Collection types (lists, vectors, maps, and sets).
   4. Lazy sequences.
   5. List functions: conj and list.
   6. Vector functions: assoc, conj, get, nth, vec, and vector.
   7. Map functions: assoc, contains?, dissoc, frequencies, get, keys, merge, vals, and zipmap.
   8. Set functions: conj, contains?, disj, get, and set.

4. Parallel programming.

   1. Concurrency and parallelism concepts.
   2. Speedup.
   3. Hardware support for parallelism (multiprocessors, SMT, multi-cores).
   4. The pmap function.

Part II: Automata Theory

1. Finite Automata.

   1. General concepts and terminology (automaton, finite state machine, deterministic and non-deterministic finite automata, alphabet, string, length of string, Kleen star, Kleen plus, language).
   2. Formal definition of a DFA (Deterministic Finite Automaton).
   3. DFA state diagrams.

2. Regular Expressions.

   1. General concept.
   2. Equivalence between regular expressions and finite automata.
   3. Syntax. Metacharacters. Special escape sequences.
   4. Clojure regular expression functions: re-matches, re-find, and re-seq.

3. Context-Free Grammars.

   1. General concept.
   2. Formal definition of a CFG (Context-Free Grammar).
   3. CFG derivations and derivation trees.
   4. The instaparse package for building parsers in Clojure.

4. Turing Machines.

   1. General concept, components and history.
   2. TM terminology: accept, reject, loop infinitely, and halt.
   3. Formal definition of a TM.
   4. TM state diagrams.
   5. Universal Turing Machine.

5. Theory of Computation

   1. Decidable languages (recursive languages). Recognizable languages (recursively enumerable language).
   2. Undecidable problems. Typical examples (Entscheidungsproblem, halting problem).
   3. The Church-Turing thesis.
   4. Turing completeness. Examples of Turing-complete and non-Turing-complete languages.
   5. The Chomsky hierarchy. Languages and grammars type 0, 1, 2, 3.

Allowed Items During the Exam

NOTE: Once the exam starts you are not allowed to share any items with anyone else.

1. Pen, pencil, eraser, pencil sharpener.

2. Simple scientific calculator. You are not allowed to use a cell phone, programmable calculator, tablet, computer, or any other electronic device.

3. Personal cheat sheet with the following characteristics:

   Must be one of these: \(5 \times 8\) inches index card (\(12.7 \times 20.32\) cm). Half letter size sheet of paper (\(13.97 \times 21.59\) cm). Must be handwritten. Computer-made cards/sheets are not allowed. You can write in both sides of the card/sheet. Must include your student ID and full name on the upper-left corner of both sides of the card/sheet. There are no restrictions on the specific content written on the card/sheet.

Sample Questions

1. Write a Clojure function called contains-all-digits? that takes an integer argument \(n\) and returns true if \(n\) contains each of the ten digits from 0 to 9 at least once, or false otherwise.

   Examples:

   (contains-all-digits 1023456789)
   => true
   
   (contains-all-digits 1236)
   => false
   

2. You are given the following Clojure code:

   (defn mystery
     ([x] (mystery x #(* 2 %) #(inc %)))
     ([a b c] (c (b a))))
   
   (defn wierd
     [& t]
     (let [n (count t)]
       (cond
         (zero? n) 1
         :else (inc (apply wierd (rest t))))))
   

   What is the result of evaluating the following expressions?

   1. (mystery 5)
   2. (wierd 4 8 15 16 23 42)
   3. (mystery 2 dec inc)
   4. (mystery 10 wierd (fn [z] (* z z)))

3. You have a sequential program that takes 10 seconds to execute using 1 processor. The parellel version of the same program takes 2 seconds to execute using 8 processors. Calculate its speedup.

4. What is the difference between an ordinary Turing machine (TM) and a universal Turing machine (UTM)?

5. Given \(\Sigma = \{ 0, 1 \} \), you want to define a language \( L \) comprised of all strings that start and end with exactly the same symbol. Thus, these strings belong to this language: 0, 010, 11001010101. Yet, these other strings do not: \( \varepsilon \), 01, 110, 010010011.

   1. Draw a state diagram of a DFA that accepts \( L \).
   2. Write a regular expression that accepts \( L \).
   3. Write a CFG that accepts \( L \).
   4. Draw a state diagram of a TM that accepts \( L \). NOTE: The final position of the tape head is inconsequential.
   5. According to the Chomsky hierarchy, what type of grammar and language is \(L\)?