CSE2304, Plan 2004

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, prac's 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,
  • (a) as a "tool kit" for the working programmer,
  • (b) as example solutions to (ii),
  • (c) 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

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.

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.

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

  © L . A l l i s o n

• 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. Fib', 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, 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