General introduction to Programming Languages ([SCOTT] chapter 1).
Clojure fundamentals.
def
, let
).
+
, +'
, 
, *
, *'
, /
, <
, <=
, =
, not=
, ==
, >
, >=
, boolean
, char
, char?
, dec
, even?
, format
, inc
, keyword?
, neg?
, nil?
, number?
, odd?
, pos?
, quot
, rem
, str
, string?
, symbol?
, and zero?
.
quote
('
) special form.
not
, and
, or
. Shortcircuit evaluation.
if
, cond
, case
). Truthy and falsy values.
defn
) and application. Parameters. Multiarity and variadic functions. Docstrings. Anonymous functions and closures. The apply
, fn?
, and ifn?
functions.
loop
/recur
.
Clojure collections.
butlast
, concat
, cons
, count
, cycle
, distinct
, drop
, dropwhile
, empty?
, every?
, filter
, first
, interleave
, interpose
, iterate
, last
, map
, mapcat
, nth
, partition
, partitionby
, range
, reduce
, remove
, repeat
, rest
, reverse
, seq
, seq?
, some
, sort
, splitat
, splitwith
, take
, and takewhile
.
conj
and list
.
assoc
, conj
, get
, nth
, vec
, and vector
.
assoc
, contains?
, dissoc
, frequencies
, get
, keys
, merge
, vals
, and zipmap
.
conj
, contains?
, disj
, get
, and set
.
Parallel programming.
pmap
function.
Finite Automata.
Regular Expressions.
rematches
, refind
, and reseq
.
ContextFree Grammars.
Turing Machines.
Theory of Computation
NOTE: Once the exam starts you are not allowed to share any items with anyone else.
Pen, pencil, eraser, pencil sharpener.
Simple scientific calculator. You are not allowed to use a cell phone, programmable calculator, tablet, computer, or any other electronic device.
Personal cheat sheet with the following characteristics:

Give three examples of Clojure builtin higherorder functions.
What is the result of the following Clojure expression?
(takewhile #(< % 10) (iterate #(+ % %) 1)))
Write a Clojure function called containsalldigits?
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:
(containsalldigits 1023456789) => true (containsalldigits 1236) => false
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?
(mystery 5)
(wierd 4 8 15 16 23 42)
(mystery 2 dec inc)
(mystery 10 wierd (fn [z] (* z z)))
Write a function in Clojure called howmanydiv3
that receives as input a sequence of integers and returns the result of counting how many of these numbers are exactly divisible by 3. For example:
(howmanydiv3 ()) => 0 (howmanydiv3 [6 2 3 12 4]) => 3 (howmanydiv3 '(2 5 7 11 19)) => 0 (howmanydiv3 [0 33 66 99]) => 4
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.
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
.
Write a regular expression that allows valid dates to be recognized using the YYYYMMDD
format defined in the ISO 8601 standard. The following should be considered to ensure that the vast majority of the recognized dates are valid (although not necessarily all):
YYYY
can range from 0000 to 9999.
MM
the first digit must be 0 or 1. If the first digit is 0, the second must be any digit from 1 to 9. If the first digit is 1, the second digit must be 0, 1 or 2.
DD
the first digit must be 0, 1, 2 or 3. If the first digit is 0, the second must be any digit from 1 to 9. If the first digit is 1 or 2, the second digit must be any digit from 0 to 9. If the first digit is 3, the second digit must be 0 or 1.
So, for example, the following dates must be recognized by the regular expression:
20230428
15210813
99991231
However, the following dates should be rejected:
00000000
(there is no month or day 0)20230432
(there is no day 32)19981315
(there is no month 13)How would you explain the Entscheidungsproblem to a smart tenyearold child?
You have the following state diagram for a Turing machine \(M\):
Remember that, formally, \(M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)\). For the Turing machine above:
What is the difference between an ordinary Turing machine (TM) and a universal Turing machine (UTM)?
Give two examples of languages used in the software industry. The first language should be Turingcomplete, the second should be nonTuringcomplete. Justify your answer.