[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 05:19:07 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

• 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:
• 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.]

## Algorithms and Data Structures:   Introduction

• 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 Logic and . . . ).

• Subject is about problem solving [e.g.],

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

• which are abstract:

## An Abstract Data Type (ADT) specifies ideal properties

• which computer + program approximates

• 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)

• 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, `   ` overflow, may crash

 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.
NB. These are rooted, binary trees.   There are also unrooted and other kinds of Trees (later).
 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 = cons1 e1 | cons2 e2 | ... `    --` define T as this `or' that `or' etc.. The names consi are constructors.

• { 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'

• S2 = S × S `    --` i.e. set of pairs from S

• S -> T `    --` i.e. set of functions from S to T

## Grammar for arithmetic expressions:

• <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> | . . .

This notation is known as Backus Naur Form (BNF). Also see the Formal Methods subject.

• Called CFG because [_________________________].
[lecturer: do examples; class: take notes!]
Grammars can be used for parsing

e.g. x + y * z

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

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

## Example

• 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'.

## Summary:

We covered:
• 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

## Prepare:

• the parser
© L.Allison, Sunday, 28-Nov-2021 05:19:07 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/01intro.shtml
Computer Science, Software Engineering, Science (Computer Science).