^CSE2304^
[2006]
Progress of the [plan] "Learning Objectives", for CSE2304,
as of week 10, 9th May, 2006
Introduction
- The subject is about problem-solving with computers:
algorithms and data structures.
- The subject is not about English,
it just happens to use English for notes, tutes, pracs etc.
However, it is necessary that you be(come) expert in
the language . . . English.
- The subject is not (mainly) about programming in C.
- The subject just happens to use
C
as the programming language that prac work etc. is done in.
However, it is necessary that you be(come) expert in
the specified programming language . . . C.
- Algorithms will be presented in English, pseudo-code,
C or even other programming language(s) as convenient.
Top Level
The subject aims to cover:
- (i) General problem-solving strategies and techniques, e.g.
- useful paradigms, e.g.
- analysis of algorithms and data structures, e.g.
- abstract data types
[L1]
[L2],
- program proof / correctness
[L2]
[L3]
[L4]
[L4'] ... etc.
[L15],
- analysis and estimation of space and time complexity
[L6]
[L9] etc.,
- etc.
- (ii) A selection of important computational problems, e.g.
- (iii) A selection of important algorithms and data structures
e.g.
[L5]
[L10]
[L12]
[L17]
[L19]
etc.,
- as a "tool kit" for the working programmer,
- as example solutions to problems (ii),
- as examples of solved problems, to gain insight into (i).
More Detail
On completing the subject you should be able to apply these
general problem-solving strategies or algorithmic paradigms
- Divide and conquer
[L6]
[L8]
- Dynamic Programming
[L7]
[L8]
[L15]
[L16],
- Greedy strategy
[L15]
[L16]
[L17],
- Recursion, linear, binary, n-ary, mutual,
[L2]
[L6]
[L10]
[L22],
to new problems that you have not seen before,
problems that you cannot find solutions to in books and other sources.
For a given algorithm you should be able to:
- Prove its correctness using logic and
pre- & post-conditions, assertions, loop invariants as appropriate
[L2]
[L3]
[L4]
[L4']
[L5]
[L6]
... etc.
[L15]
[L16]
[L17]
Prove termination
[L3]
[L8]
[L20].
- Analyse its best-, average- and worst-case
time- and space-complexity where possible, or give estimates otherwise
[L6]
[L8]
[L10]
[L13]
[L17]
[L24]
etc..
- Demonstrate its operation on simple examples
using diagrams etc.
[L10]
[L11]
[L16]
[L17]
- Code the algorithm
in the programming language of the subject.
- Modify it to solve a new problem.
For a given abstract data type (ADT) you should be able to:
- Specify its properties by giving rules/ equations that
its constructors and/or operators must obey
[L1]
[L2] etc..
- Manipulate expressions,
e.g. to show that different expressions are equivalent in value
[L2].
- Code its data representation and operators
in the programming language of the subject.
- Modify it to solve a new problem.
You should be familiar with
these important problems and their solutions (alphabetic order):
- connectedness in graphs
[L15]
- minimum spanning trees
[L16]
[L17]
- numerical problems - e.g. solving f(x)=0 and integration
[L20]
- ordering problems in directed acyclic graphs (DAGs)
[L18]
- searching (retrieval, dictionary tables, index structures)
[L9]
[L10]
[L11]
[L12]
- shortest paths in graphs
[L15]
- sorting
[L4]
[L5]
[L6]
[L18]
- string searching / matching, exact and approximate
[L7]
[L8]
[L11]
[L13]
[L19]
- traversal of various data structures
[L9]
[L14]
[L14']
[L17]
[L18]
© L. Allison 2006,
Faculty of Information Technology (Clayton School),
Monash University, Australia 3800,
was
School of Computer Science and Software Engineering,
Monash University.
Created with "vi (Linux + Irix)", charset=iso-8859-1