----- NEEDS JAVASCRIPT ON. -----
[Subject home ],
[FAQ ],
[progress ],
Bib' ,
Alg's ,
C ,
Java
- L.A. ,
Friday, 03-May-2024 11:15:09 AEST
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.
CSE2304: Admin
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) :
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:
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)
e.g. You should already know the
ADT ``Integer''
constants 0, 1, 2, ...
operators +, -, *, /, mod, ...
+ : Integer × Integer -> Integer,
. . . i.e. type of +, etc.
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.
The ADT `Tree '.
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
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 ].
On ADT notation.
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 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'
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> | . . .
NB. read "::=" as "is", and read "|" as "or"
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:
© L.Allison ,
Friday, 03-May-2024 11:15:09 AEST
users.monash.edu/~lloyd/tilde/CSC2/CSE2304/Notes/01intro.shtml
Computer Science,
Software Engineering,
Science (Computer Science).