COMP9024 Data Structures and Algorithms 2018S2

ALL CODES SHOULD BE APPROPRIATELY REFERENCED, COPYING MAY RESULT IN PLAGIARISM

Lecturer: Michael Thielscher

Main Contents

1. Abstract data types : Stack, queue, string array, creating ADTs...
2. Dynamic data structures : Memory allocation, memory leak, pointer and reference, stack & linked list implementation.
3. Analysis of algorithms : Time complexity, space complexity, Big-Oh notation.
4. Graph data structures : Array of edges, adjacency matrix, adjacency list, DFS & BFS in graph path search.
5. Graph algorithms I : Hamiltonian paths/circuits, Euler paths/circuits, directed graphs, transitive closure, PageRank...
6. Graph algorithms II : Weighted graphs, minimum spanning tree algorithms (Kruskal, Prim), shortest path algorithms (Dijkstra, Floyd), flow network algorithms (Edmonds-Karp maxflow algorithm)
7. Search tree algorithms I : Binary search tree (BST) data structure, tree insertion, deletion, rotation, partition...
8. Search tree algorithms II : Self-adjusting trees (AVL, splay, 2-3-4, red-black tree)
9. String algorithms : Pattern matching algorithms (Boyer-Moore, KMP), tries, text compression (Huffman code)
10. Approximation and randomised algorithms : Approximation, randomised quicksort, Karger's algorithm, Simulation.

Assessment Details

1. Assignment 1 : Linked list implementation and manipulation. Mark:8.5/10.
2. Assignment 2 : Stack implementation, graph path search, DFS. Mark:14/15.

Disclaimer

1. No responsibility will be taken if some mistakes influence your mark. It is better to check before referencing.
2. No responsibility will be taken if copying codes results in detected plagiarism.