Undergraduate - UnitFIT2004 - Algorithms and data structures

At the completion of this unit students will have:

• understanding of a formal specification;
• ability to create a formal specification for an informal problem;
• knowledge and understanding of algorithmic properties such as correctness, termination and complexity;
• ability to, given a non-trivial algorithm, formally prove certain properties, such as correctness and termination;
• ability, given a non-trivial algorithm, to determine its best, average and worst-case, time and space-complexity;
• knowledge and understanding of reasonably complex data structures such as minimum spanning trees, and Directed and Undirected, Weighted and Unweighted Graphs;
• ability to design and implement new non-trivial algorithms using complex data structures;
• knowledge of and ability to use algorithmic paradigms such as divide and conquer, greedy, dynamic programming and so on;
• ability to identify these paradigms in diverse algorithms;
• knowledge and understanding of the issues involved in implementing a non-trivial algorithm efficiently.

Developed attitudes that enable them to:

• carefully design and/or analyse the algorithms they are using in order to verify important properties such as correctness, termination, and complexity;
• identify the key features of a brief informal problem description and abstract the underlying formal problem.

Developed the skills to:

• create their own data structures.
• create a new algorithm to solve a new problem.
• make a formal argument about desirable properties of the solution.
• adapt an existing algorithm and/or data-structure where that is possible and appropriate.
• implement a non-trivial algorithm efficiently.

Demonstrated the communication skills necessary to:

• make a formal argument that an algorithm and/or data-structure has a given property, such as correctness, termination or complexity.