[CSE2304] [progress]

## CSE2304, Plan 2000

• The course is not (mainly) about programming in C.
• The course is about problem solving with computers and algorithms & data structures.
• The course just happens to use C as the programming language that prac' work etc. is done in. It is necessary that you be(come) expert in the specified programming language ...C.
• Algorithms will be presented in pseudo-code, C or other programming language(s) as convenient.

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.Allison
• 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
• 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
• Trees, binary, sorted, balanced, n-ary

Some general algorithmic strategies or paradigms:

• Divide and conquer
• Dynamic Programming
• Greedy
• 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.
• Give 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.