CSCI 162 Final Exam Reference Sheet

Boolean logic identities

Inversion:      0' = 1
                1' = 0
Involution:     X'' = X
Dominance:      X+1 = 1
                X*0 = 0
Identity:       X+0 = X
                X*1 = X
Idempotence:    X+X = X
                X*X = X
Compliment:     X+X' = 1
                X*X' = 0
Commutativity:  X+Y = Y+X
                X*Y = Y*X
Associativity:  X+(Y+Z) = (X+Y)+Z
                X*(Y*Z) = (X*Y)*Z
Distributivity: X+(Y*Z) = (X+Y)*(X+Z)
                X*(Y+Z) = (X*Y)+(X*Z)
Absorption:     X*(X+Y) = X
                X+(X*Y) = X
DeMorgans:      X+Y = (X'*Y')'
                X*Y = (X'+Y')'

Powers of 2

  hex decimal octal
20 1 1 1
21 2 2 2
22 4 4 4
23 8 8 10
24 10 16 20
25 20 32 40
26 40 64 100
27 80 128 200
28 100 256 400
29 200 512 1000
210 400 1024 2000
211 800 2048 4000
212 1000 4096 10000
213 2000 8192 20000
214 4000 16384 40000
215 8000 32768 100000
216 10000 65536 200000

Hex: A=10, B=11, C=12, D=13, E=14, F=15

Marie instructions and machine code

hexinstructionmachine code
0 JnS X 0aaa
1 Load X 1aaa
2 Store X 2aaa
3 Add X 3aaa
4 Subt X 4aaa
5 Input 5000
6 Output 6000
7 Halt 7000
8 Skipcond X 8aaa
9 Jump X 9aaa
A Clear A000
B AddI X Baaa
C JumpI X Caaa
D LoadI X Daaa
E StoreI X Eaaa
F    
aaa indicates the value of X for skipcond,
  the address of X otherwise
Skipcond: 000 for <, 400 for =, 800 for >

IR: instruction register
PC: program counter
ACC: accumulator
MAR: memory address register
MBR: memory buffer register


Regular expressions

(pattern)?  matches 0 or 1 instances of the pattern

(pattern)+  matches 1 or more instances of the pattern

(pattern)*  matches 0 or more instances of the pattern

(pattern1 | pattern2) matches either pattern

[aeiou]     matches any one of a, e, i, o, or u

[^aeiou]    matches anything EXCEPT an a, e, i, o, or u

[A-Z0-9]    matches anything in either range, A-Z or 0-9

.           matches any single char

^           matches the start of a string

$           matches the end of a string

Lisp syntax
#! /usr/bin/gcl -f

(load "filename") ; load contents of a file

; variables/constants
(defvar x 3)
(defconstant pi 3.14)

; literal values
#\x     ;    character x
t       ;    true
nil     ; false, empty list, also written '()

; basic i/o
(setf x (read)) (format t "x is ~A~%" x)

; list syntax:
'(10 20 30)
(list 10 20 30)

; core list functions, also caar, cadr, caddr, etc
(car L) (cdr L) (cons e L) (length L) (null L)
(member e L) (nth i L) (remove e L) (append L1 L2)

; common type checking functions
(listp x) (numberp x)  (integerp x) (stringp x) (functionp x)

; logic operators
(and x y) (or x y) (not x)

; bitwise 2's complement operators
(lognot x) (logand x y) (logor x y)
(lognor x y) (logxor x y) (lognand x y)

; if syntax
(if (< x y)
    (format t "do this if true")
    (format t "do this if false))

; cond syntax
(cond
   ((not (listp L)) nil)
   ((null L) nil)
   (t (car L)))

; function definitions,
;    with an optional parameter y
;    and using let for local variables
(defun f (x &optional (y 0))
   "this is the optional documentation string for f"
   (let
      ; list of local variables, values
      ((a 1) (b 2))
      ; body of function
      (+ (* a x) (- y b))))

; higher order functions (passing functions as params)
(defun applyTo (f val1 val2)
   (if (functionp f)
       (funcall f val1 val2)
       (format t "That was not a function~%")))

; built in list loop
(dolist (x L)
   (format t "Do something with ~A~%" x))

; sample call
(applyTo '+ 3 4)

; higher order functions with effect of (f arg1 arg2 arg3)
(funcall f arg1 arg2 arg3)
(apply f '(arg1 arg2 arg3))
(eval '(f arg1 arg2 arg3))

; sample calls to other higher order functions
(mapcar 'sqrt '(9 4 16))  ; returns (3 2 4)
(sort L '<)
(map 'string 'char-upcase "Hello") ; returns "HELLO"

; regular expression matching
(si::string-match pattern textstring)
Prolog syntax
% variables begin with uppercase, atoms with lowercase

% input/output,
read(X), get(Char)
write(X), write_ln(X), nl, put(Char)
format("X is ~w, Y is ~w ~n", [X, Y])

% math comparisons, e.g. X < Y
%   <   =<   >=   >   =:=   =\=

% math operators, e.g. used in format  X is 3^Y
% + - * / // mod ^ max min

% common math functions
round(N, Result), abs(N, Result), sqrt(N, Result)
sin(N, Result), cos(N, Result) % etc

% characters literals: 0'x  0'z  etc
% common string functions:
string_upper(Str, Result)  string_length(Str, Length)

% string output: put char-by-char or format
% (write/write_ln display strings as a list of ascii values)

% basic rule syntax
positiveNum(N) :- number(N), N > 0.

% type checking
number(X), string(X), integer(X), is_list(X), atom(X)

% are variables instantiated (have a value already) or not
var(X), nonvar(X)

% equivalence and comparison between general terms
X == Y, X =\= Y,  X @< Y,  X @=< Y, X @> Y, X @>= Y

% instantiation (assigns value to uninstantiated var)
X is 3

% unification (sees if they are/can-be-made the same thing)
X = Y,  X \= Y

% lists, _ for "don't care"/ignore
[1,2,3,4] = [Head|Tail] ; Head is 1, Tail is [2,3,4]
[1,2,3,4] = [ _ | Tail] ; Tail is [2,3,4]

% some common list functions
reverse(L,Result) member(E,L) nth(Pos,L,E) length(L,Size)
append(L1,L2,Result) sort(L,Result)

% strings are lists of their character ascii values, e.g.
S = "foo"  % unifies S with list [102,111,111]

% fail causes a goal to fail, e.g.
nonNum(X) :- number(X), fail.
nonNum(X).

% cuts prevent backtracking
read(X), !, use(X)   % once it passes the cut (!)
   % it cannot backtrack if the use(X) fails

% boolean operators
%    , used for logical and
%    ; used for logical or
%    \+ used (with limitations) for logical not

% if-then-else: if X is true tries Y, otherwise tries Z
%    X -> Y ; Z

% bitwise operators for and  or  not  xor  bitshifts
%                        /\  \/   \   xor    <<  >>
% e.g. X is Y /\ Z

% repetition
%    keep doing everything to the right until true
repeat, f(X), g(Y), etc(Stuff).