- Lloyd Allison,

- Available times: Check office door or
[www],

- Exam (70%), pracs (marked, 30%), both hurdles,
i.e. fail either => max' mark is 44%N, ,

- tutes

- Easter and Anzac Day complicate time-tables - check yours!

- Check 2nd year notice board OFTEN . . .

- Online:
- CSE2304 home page
- Some general computer science research resources
*(not CSE2304-specific)*:- C
- bibliography
- algorithms web site

- Instructions
- There are many hyper-links in these lecture notes; some are for the lecturers, some for revision.
- The most important links are in [square brackets];
usually following them to a
*depth of one*, or rarely two, is sufficient for the "class". - You need to take extra notes, draw diagrams and
[follow instructions; do this!] .

- [
**NB. Email**about the subject MUST contain `**CSE2304**' in the**Subject**line.]

- Subject is NOT (mainly) about programming.

- It is not about English; it
*uses*English.

- It is not about C; it
*uses*C (and pseudo-code and Maths and Logicand . . . ) .

- Subject is about
*problem solving*[e.g.],

& about algorithms & data structures (that is solved problems)

- which are abstract:
- Abstract Data Types
- Mathematics
- Logic
- Grammar . . .

- which computer + program
*approximates*

- e.g. You should already know the ADT ``Boolean''

- true, false, and, or, =>, not

**rule**: p and (q or r) = (p and q) or (p and r)

**rule**: false and p = false

**rule**: p and q = q and p, etc. . .

- so: p and false = false,
but not always on a
computer . . .

- e.g. (1 / n > 1) && n > 0,
. . . can crash if n=0 (divide by zero)

- true, false, and, or, =>, not

- e.g. You should already know the
ADT ``Integer''

- constants 0, 1, 2, ...

- operators +, -, *, /, mod, ...

- + : Integer
**×**Integer**->**Integer, . . . i.e. type of +, etc.

**--rules**

- rule: m + n = n + m

- rule: p * ( q + r ) = p * q + p * r

- rule: i + ( j + k ) = ( i + j ) + k,
but not always on a
computer . . .

- e.g. 1 + (maxint - maxint) = 1, but . . .

- . . . (1 + maxint) - maxint,

- constants 0, 1, 2, ...

You must revise prefix, infix, postfix and breadth-first tree [traversal] from 1st year. |

- constant: empty_Tree
(a.k.a. nil, empty, null, null_Tree etc.)

- constructor, fork: E × Tree × Tree -> Tree

- contents: Tree -> E
- left, right: Tree -> Tree
- isEmpty: Tree -> Boolean

**--rules**

- rule: isEmpty( empty_Tree ) = true
- rule: isEmpty( fork e L R ) = false
- rule: left( fork e L R) = L
- . . . etc.

You must revise the
[Stack]
and
[Queue]
from the ADT point of view. |

If and when you get stuck on notation, remember the
[glossary]. |

- S, T, U, ..., used for sets of values

- T = cons
_{1}e_{1}| cons_{2}e_{2}| ...`--`

define T as this `or' that `or' etc.. The namescons _{i}are*cons*tructors.

- { x | P(x) },
i.e. the set of things that satisfy property P

- S
**×**T = {<s, t> | s in S and t in T}

- i.e. set of (ordered) pairs from S and T resp'

- S
^{2}= S**×**S`--`

i.e. set of pairs from S

- S
**->**T`--`

i.e. set of functions from S to T

© L . A l l i s o n |

- <Exp> ::= <Exp> + <Term>
**|**<Exp> - <Term> **|**<Term>

- <Term> ::= <Term> * <Factor>
**|**<Term> / <Factor> **|**<Factor>

- <Factor> ::= x | y | ...
**|**( <Exp> ) **|**- <Factor>

Notation . . .

- . . . notation: In general,
a
*context free grammar*(CFG) consists of:

- Terminal symbols,
i.e. characters and words, e.g. +, -, *, /, (, ), x, y, . . .

- Non-terminal symbols, i.e.
*names for language parts*,

e.g. <Exp>, <Term>, etc.

- Production rules, e.g.
<Term> ::= <Term> * <Factor> | . . .

**NB.**read "::=" as "is", and read "|" as "or"

- Terminal symbols,
- Called CFG because [_________________________].

e.g. x + y * z

Exp(+) . . . . -- Parse Tree . . . Term(*) . . . . . . . . . x y z

See a small [Parser in C]. Must understand (left | right)- associativity.

- There is another (JavaScript) program in /Wff/ which

- parses
propositional logic
(~ Boolean expressions)

- and analyses it

- [lecturer: use and discuss, if in time]

**NB.**It may be useful later in `Formal Methods'.

- Administrivia, and
can I see the student rep'(s) plsz

- Assessment

**N.B.***abstract*algorithms and data structures,

- subject is not about programming as such

- the parser