^CSE2304^
[2006]
Plan, "Learning Objectives", for CSE2304, 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.
- dynamic programming,
- divide and conquer,
- etc.
- analysis of algorithms and data structures, e.g.
- abstract data types,
- program proof / correctness,
- analysis and estimation of space and time complexity,
- etc.
- (ii) A selection of important computational problems, e.g.
- sorting,
- retrieval/searching,
- etc.
- (iii) A selection of important algorithms and data structures,
- 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
- Dynamic Programming
- Greedy strategy
- Recursion, linear, binary, n-ary, mutual
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.
Prove termination.
- Analyse its best-, average- and worst-case
time- and space-complexity where possible, or give estimates otherwise.
- Demonstrate its operation on simple examples
using diagrams etc.
- 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.
- Manipulate expressions,
e.g. to show that different expressions are equivalent in value.
- 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
- minimum spanning trees
- numerical problems - e.g. solving f(x)=0 and integration
- ordering problems in directed acyclic graphs (DAGs)
- searching (retrieval, dictionary tables, index structures)
- shortest paths in graphs
- sorting
- string searching / matching, exact and approximate
- traversal of various data structures
Bottom Level
The following topics will be covered, not in this order:
- Algorithmic problem-solving, correctness, complexity
- Correctness, termination, logic, assertions, loop invariants,
pre- and post-conditions
- Complexity, time and space complexity,
best average and worst case, O( ), recurrence relations,
estimation of complexity
- Abstract Data Types (ADTs),
e.g. Boolean, Integer, Stack, Queue, List, Tree
- Recursion, e.g. Fibonacci, Towers of Hanoi, permutations, partition
- Trees, parse trees, tree traversals
- Dynamic programming strategy, e.g. edit distance on strings
- Divide and conquer strategy,
e.g. Hirschberg, multiplication, merge sort, etc.
- Lookup Table (dictionary table) ADT
- Hashing revised, string searching algorithms
- Table by balanced tree, search, insertion, deletion, eg. AVL-tree
- Other tree structures,
e.g. PATRICIA, Trie, 2-3-Tree, 2-3-4-Tree, B-Tree, Suffix tree
- Graphs, directed/undirected and weighted/unweighted
- Directed Graphs
- Shortest paths, connectivity
- Undirected Graphs
- minimum spanning tree, Prim's alg., Kruskal's alg.
- Numerical computing, limited accuracy,
solving f(x)=0,
integration, rectangle, trapezoidal rule, Simpson's rule
Some specific problems, algorithms and data structures
(alphabetic order):
- Graphs (directed), shortest paths, Dijkstra's algorithm,
Floyd's algorithm, connectedness, Warshall's algorithm,
topological sort, critical path analysis etc.
- Graphs (undirected), minimum spanning tree,
Prim's algorithm, Kruskal's algorithm
- Linked Lists, ADT properties,
cons, nil, null (empty), hd (head, first), tl (tail, rest, next), append
- Priority Queue e.g. by Heap data structure,
upHeap and downHeap
- Partition data structure (aka union-find, disjoint set)
- Queue, empty, pushq, popq, ADT properties
- Searching, lookup tables, ADT properties,
search, insertion, deletion
- Sorting,
bubble sort, selection sort, insertion sort, merge sort,
quick sort, heap sort, complexity, correctness, stability
- Stack, empty, push, pop, ADT properties
- String searching, naive, Rabin, Boyer-Moore
- Traversal of linked lists, trees, graphs,
depth-first, breadth-first, other
- Trees, binary, sorted, balanced, n-ary (various), un-rooted
You should be able to analyse a new problem and
draw upon these techniques, strategies, and
standard algorithms & data-structures,
and apply them, possibly with modification, to the problem.
© 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