[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:

Today:

The abstract data type (ADT) ``List''

Many useful functions on Lists, e.g.:

It is much easier to reason formally about ADTs and (abstract) algorithms than about C structures and programs...

[*] inductive step.

ADT 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.
[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:


because [_________________________]
©
L
.
A
l
l
i
s
o
n

Propositional Logic

    p & (q or r)      =       (p & q) or (p & r)

                                      or
         and                         .  .
        .   .        --->           .    and
       .     .                |----.-----| .
      .      or               |   .         .
     .       . .              |  and         .
    .       .   .             | .    .        .
   .       .     .            |.      .        .
.---.   .---.   .---.        .---.   .---.   .---.
| p |   | q |   | r |        | p |   | q |   | r |
.---.   .---.   .---.        .---.   .---.   .---.

Example

Lists and Trees:   Summary:

We covered:
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).