FIT2004 Algorithms and Data Structures

^up^ >Java> >CSE2304: staff, planning, prereqs, courseware/2005>

FIT2004 Algorithms and Data Structures (6-pts) 2007+ (DRAFT)

Context

twiki
- units
  - FIT1002 Comp Prog
  - FIT1008 Comp Sci A and FIT1015 Comp Sci B ~ CSE1303
  - FIT2004 Alg + DS ~ CSE2304 A+DS
  - FIT2014 Theory of Comp ~ CSE2303 FM-I
  - FIT3104 Analysis + Design of Alg ~ CSE3305 FM-II

Questions (3 Oct, 10 Oct, 12 Oct, 20 Oct):

Will Unix be used? If so will this be the students' 1st time?

Can a "certain level" of common notation (and also some representative diversity!) be adopted across "replacements" for cse1303, cse2304, cse2303 & cse3??? for specifications, e.g.

0! = 1; n! = n*(n-1)!
and e.g.: emptyStack : stack t (stack of some element type t); pop (push s x) = s, for all stacks s and all x --side-effect-free version; top (push s x) = x, for all stacks s and all x; pop emptyStack = top emptyStack = error
and e.g.: list t = nil | cons t (list t) --a list is either the nil list or (|) is cons(tructed) from an element of type t and a list.; nil : list t; cons : t -> list t -> list t (with [a,b,c] as shorthand); null : list t -> Boolean; length nil = 0 --or possibly length [] = 0; length (cons x xs) = 1 + length xs
I.e. Including defn of functions "by cases", some "incidental" elementary(!) use of type and value constructors, and of curried functions (but no formal definition of polymorphic types and type inference!).
Can "list" be commonly used as in the ADT "list" & as shorthand for "linked list", and can something else be used for "sequence" -- perhaps sequence(!) as in a sequential access data-(structure|type)?
It would be very useful to have available on-line html(!) "cheat-sheets" of logic, Maths, recurrences,..., from 1st-year Maths and Comp-Sci-A/B.
I vote for .html v. .pdf (and .html or .pdf v. .doc) for all documents across all units -- where possible of course.

Propose:

2 x 1-hour lectures per week

1-hour tute, maybe every week, maybe every other week

every other week a tute is assessed

3-hour lab/prac every other week, or maybe 2-hour every week,

every other week some prac work is assessed.

The content strongly guides itself towards the following which can be taught in some reasonable depth and can be used fairly seriously in pracs and tutes. One or two extra substantial topics could of course be included in various ways (say in a 3rd lecture per week) but a substantial number of areas would then not be covered by "doing things for real" in pracs and/or tutes I would rather spend any further contact-hours on making more of this content covered by prac and tute.

week 1: Admin, introduction, prerequisite knowledge, notation, math, logic, specification v. implementation.; Lists and trees as ADTs. Prove some theorems on lists, trees and/or other ADTs (stack, Q, ...). Introduce a simple grammar and a parser (non-examinable) as a source of trees (e.g. for pracs).
week 2: Algorithm correctness & termination, and best-, average & worst-case time- & space-complexity analysis. Illustrate this with some simple familiar algorithms such as binary-search and simple sorts, say.; Continue algorithm analysis by examples on some more complex familiar algorithms, and some simpler unfamiliar algorithms, to...; [Prac-0]
week 3: ...some more complex unfamiliar algorithms and DS such as priority-queue and Heap-sort (and its relationship with selection-sort).; [Tute-0]
week 4: Good time to do the development of a "new" algorithm for a "new" problem and to show variations - algorithmic paradigms, algorithms and analyses therof.; E.g. dynamic programming paradigm and more than one algorithm for approximate string matching problems, say.; [Tute-1 (assessed)]
week 5: The lookup-table (dictionary) as an ADT, abstract properties, operations (clear, insert, delete, search), and their pre- and post-conditions. (Specification v. implementation, again!) Implementation by the simplest techniques -- unsorted and sorted arrays, analysis & complexity.; Lookup-table by hashing -- hash functions, collisons, linear probing, quadratic probing, chaining, analysis & complexity (as always).; [Prac-1 (assessed), very probably manipulation of a parse-tree produced by a given parser, see week-1 & connects to tree structures from FIT1008/1015 Comp.Sci.A|B]
week 6: Revise lookup-table by binary-search-tree (from 1st year?), including the 'delete' operation, complexity, problem of unbalanced BSTs; the cure is balanced trees such as AVL-tree and B-tree, importance of the latter for data-bases.; [Tute-2 (assessed)]
week 7: Some special structures for strings: Tries and similar, the classic string-search problem, naive, Rabin (hashed) & Boyer-Moore solutions, and analysis thereof.; (I have in the past shown a suffix-tree as an "impressive" advanced data-structure -- with "limited examinability".); [Prac-2 (assessed), very probably on a new, simple-to-state problem which has a "non-trivial" algorithmic solution, e.g. where complexity and/or correctness is a real issue.]
week 8: Graphs, revise definitions from 1st-year Math, examples, directed, undirected, weighted, unweighted.; Path problems -- shortest, single source, all pairs, transitive closure -- and algorithms.; [Tute-3 (assessed)]
week 9: Minimum-spanning-tree (MST), problem, examples. Prim's MST algorithm.; Kruskal's MST algorithm (connects with priority-Q).; [Prac-3 (assessed)]
week 10: Directed Acyclic graphs (DAGs), partial orders, depth-first traversal and how it can be instantiated to: topological-sort, and critical-path analysis (CPA).; [Tute-4 (assessed)]
week 11: Introduction to numerical computing, limited accuracy, danger of '=', including re termination. Problems and algorithms: solve f(x)=0, integrate f(x), other? (E.g. "adaptive" integration can re-illustrate recursion.); [Prac-4 (assessed)]
week 12: Combinatorial objects, generation/enumeration, "next" object, permutations, combinations, partitions, sequences with constraints & n-queens or similar, recursion, combinatorial search, relation to "puzzles" and "games".; Recursion summary, linear-, binary-, n-ary, with references back to previous lectures and applications.; [Tute-5 (assessed)]
week 13: Algorithm design and analysis summary, real-world examples, recap algorithm paradigms -- nested loops, iteration v. recursion, dynamic programming, divide and conquer -- with references back to previous lectures and applications.; [Prac-5 (assessed)]

Notes: I believe that the above content is "plenty", particularly given a strong emphasis on students "doing things for real", and "a high level of competence required for a pass". This must not be a unit just on "appreciation" of As+DSs.; The lecture ordering above is "heavy" early on in semester, lighter later. This is a good thing and allows pracs and tutes to build on more of the important lecture content.; NB. Easter (usually weeks 4 to 8) and Anzac Day (25 April) cause time-table "difficulties" esp. with pracs and tutes so that e.g. prac-1 has, in the past, been over weeks-3/4, and similar "disruption" to pracs-2 and pracs-3 common.; Running prac-2 & prac-3 as a sequence, and prac-4 & prac-5 ditto, has worked well.

Created with "vi (Linux & Solaris)", charset=iso-8859-1