----- NEEDS JAVASCRIPT ON. -----
[Subject home ],
[FAQ ],
[progress ],
Bib' ,
Alg's ,
C ,
Java
- L.A. ,
Sunday, 28-Nov-2021 04:15:49 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.
Lists and Trees: Introduction
Reminder:
Subject is about
problem solving [e.g. ],
i.e. abstract algorithms and data structures
not programming (in C) as such
Today:
List
(more) Trees
Parse Trees and parsing
Manipulating Trees
The abstract data type (ADT)
``List ''
A (linked) list is either
the empty list or ( | )
cons tructed (cons) from an element and a list
List t = nil | cons t (List t)
operator: null: List t -> Boolean
(aka isEmpty etc)
operator: hd: List t -> t
(aka head, first, etc)
operator: tl: List t -> List t
(aka tail, next, rest etc)
the operators obey the rules :
null ( nil ) = true
null ( cons e l ) = false
hd ( cons e l ) = e
tl ( cons e l ) = l
Many useful functions on Lists, e.g.:
append: List t × List t -> List t
e.g. append [1, 2] [3, 4, 5] = [1, 2, 3, 4, 5]
Definition:
append nil L_{2} = L_{2}
append (cons e L_{1} ) L_{2} = cons e (append L_{1} L_{2} )
can be implemented
[in C ]
of course.
It is much easier to reason formally about ADTs
and (abstract) algorithms than about C structures and programs...
Theorem:
append L_{1} (append L_{2} L_{3} )
= append (append L_{1} L_{2} ) L_{3}
proof part (a) , the base case, if L_{1} = nil
append nil (append L_{2} L_{3} )
= append L_{2} L_{3}
= append (append nil L_{2} ) L_{3}
= append (append L_{1} L_{2} ) L_{3}
proof part (b) , the general case,
if L_{1} = cons h t
append (cons h t) (append L_{2} L_{3} )
= cons h (append t (append L_{2} L_{3} ) )
= cons h (append (append t L_{2} ) L_{3} )
--[*]
= append (cons h (append t L_{2} )) L_{3}
= append (append (cons h t) L_{2} ) L_{3}
= append (append L_{1} L_{2} ) L_{3}
[*] inductive step.
ADT Tree
A (binary) Tree
(of some Element type) is either
the empty tree or
a fork made of
an element `E',
a left sub-tree `L' and
a right sub-tree `R'.
Tree t = Empty_Tree | Fork t (Tree t) (Tree t)
[See Ops.c
in .../C/Tree/ ]
possible representation in C:
#include "TreeElement.h"
struct node
{ TreeElementType elt;
struct node *left, *right;
};
typedef struct node Node;
typedef Node *Tree;
/* Tree Type. */
Many useful functions on
Trees , e.g.
NB. We say that
f(n) is
O( g(n))
iff there are constants k & m
such that f(n) <= k * g(n)
for all n >= m .
flatten: Tree t -> List t
Definition
flatten Empty_Tree = nil
flatten (Fork e L R)
= append (flatten L) (cons e (flatten R))
This Defn takes
O( n^{2} ) -time ,
because [___________________]
[lecturer: Draw some diagrams; class: take notes!]
and there is a proof that the slow and fast methods are equivalent
[here ].
. . . by the way, this `flatten' is faster, O(n)-time:
flatten T = flatten2 T nil
where
flatten2 Empty_Tree Ans = Ans
flatten2 ( Fork e L R ) Ans
= flatten2 L ( cons e ( flatten2 R Ans ) )
because [_________________________]
Propositional Logic
Already discussed
parser
and arithmetic expressions
Can "easily" change it to parse
propositional logic
~ Boolean expressions:
`+' ---> `or'
`*' ---> `and'
unary `- ' ---> `not'
p & (q or r) = (p & q) or (p & r)
or
and . .
. . ---> . and
. . |----.-----| .
. or | . .
. . . | and .
. . . | . . .
. . . |. . .
.---. .---. .---. .---. .---. .---.
| p | | q | | r | | p | | q | | r |
.---. .---. .---. .---. .---. .---.
useful for
DNF
(disjunctive normal form)
Example
This html
FORM
can prove theorems in
propositional logic
may be useful later in `Formal Methods'.
[lecturer: e.g. do the `or' over `and' pointer manipulation;
class: take notes]
Lists and Trees: Summary:
We covered:
Abstract data type (ADT) ``List''
reasoning about algorithms and ADTs
ADT ``Tree''
Manipulating Trees
Also read about Lists and Trees,
e.g. from text book(s), and
prepare: algorithm analysis, proof, correctness, logic.
© L.Allison ,
Sunday, 28-Nov-2021 04:15:49 AEDT
users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/02parsetrees.shtml
Computer Science,
Software Engineering,
Science (Computer Science).