Course Title: Algorithms and Analysis

Part A: Course Overview

Course Title: Algorithms and Analysis

Credit Points: 12

Course Code	Campus	Career	School	Learning Mode	Teaching Period(s)
COSC1285	City Campus	Postgraduate	140H Comp Sci & Info Technology	Face-to-Face	Sem 1 2006, Sem 2 2006, Summer2007, Sem 1 2007, Sem 2 2007, Summer2008, Sem 1 2008, Sem 2 2008
COSC2123	City Campus	Undergraduate	140H Comp Sci & Info Technology	Face-to-Face	Sem 1 2006, Sem 2 2006, Summer2007, Sem 1 2007, Sem 2 2007, Summer2008, Sem 1 2008, Sem 2 2008

Course Coordinator: Dr. Santha Sumanasekara

Course Coordinator Phone: +61 3 9925 9673

Course Coordinator Email:santha.sumanasekara@rmit.edu.au

Pre-requisite Courses and Assumed Knowledge and Capabilities

Extensive programming skills in C language, equivalent to Programming Techniques.

Course Description

This course builds on skills gained in preliminary programming courses in both Java and C programming languages and gives students an in-depth understanding of a wide range of fundamental algorithms and data structures used in developing structured, efficient, reusable, and practical software.

The objective of this course is to study a broad variety of important and useful algorithms and data structures. We shall deal with many different areas of applications, always concentrate on fundamental algorithms that are important to know and interesting to study. Students will spend a significant time on each algorithm to understand its essential characteristics and to respect its subtleties.

We also pay careful attention to performance characteristics of the algorithms, to help students develop improved versions, compare different algorithms for the same task, and predict or guarantee performance for large problems. Understanding how the algorithms perform require experimentation or mathematical analysis or both. In this course, we consider detailed analysis of many algorithms, developing analytic results directly when feasible, or calling on results from the research literature when necessary.

Most of the algorithms discussed in this course involve methods of organising the data involved in the computation. Therefore, the study and the analysis of the data structures is also an objective of this course. We consider basic methods of organisation and methods of manipulating data, work through a number of specific data structures, and discuss related issues such as storage management. Furthermore, we discuss abstract data types, where we separate the definitions of data types from implementations.

Objectives/Learning Outcomes/Capability Development

This course contributes to the development of the following capabilities:
Enabling Knowledge: the operation, implementation and performance of fundamental algorithms and data structures, and the relative merits and suitability of each for various applications.
Problem Solving: Ability to design and implement efficient software solutions for various application areas using appropriately selected algorithms and data structures.
Critical Analysis: Ability to analyse data structures and algorithms, to compare and evaluate them with respect to time and space requirements, in order to make the most appropriate design choices for various application areas.
Communication: Ability to motivate and explain efficient programming concepts, relevant alternatives and decision recommendations, in written form, to IT specialists
Responsibility: Ability to apply relevant standards and ethical considerations to the design and implementation of efficient software solutions.

On completion of this course you should have gained a good understanding of fundamental algorithms and data structures and be able to apply them in various software applications. Specifically, you should be able to:
 (a) Critically analyse data structures and Algorithms
1. Understand the fundamentals of Algorithm Analysis.
2. Use of mathematical analysis and empirical analysis to compare algorithms
3. Use of Big ‘O’ notation for the algorithmic complexity
4. Comparison of space and time complexity of algorithms – best-case, worst-case and average-case analysis.

(b) Skills in understanding of fundamental data structures and algorithms
1. Understand the concept of Abstract Data Types – separation of definitions of data types from implementations
2. Discuss basic ADTs such as stacks, queues, and trees
3. Discuss the recursion and tree traversal
4. Investigate Algorithm Design Techniques, including – greedy algorithms, divide-and-conquer algorithms, Dynamic programming, Randomised Algorithms and Back-tracking
5. Study of graph representations and algorithms, terminology, graph traversal, and graph applications
6. Further study of advanced tree data structures – including BSTs, root insertion, 2-3-4 trees, red-black trees, and splay trees
7. Analyse the space and time complexity of these data structures and their access algorithms
8. Study the Radix Search algorithms – digital search trees, tries, patricia tries, and multi-way search tries
9. Study of elementary sorting algorithms – Selection sort, Bubble sort, Insertion sort, and Shell sort. The performance characteristics of elementary sorting algorithms.
10. Study of advanced sorting algorithms – Quick sort, Merge sort, and Heap sort. The performance characteristics of advanced sorting algorithms
11. Study of radix sorting methods – Binary quick sort, MSD Radix sort, and LSD Radix sort
12. Discuss simple hashing schemes for searching. Performance analysis of simple hashing schemes.
13. Discuss string and pattern matching techniques – brute-force method, Knuth-Morris-Pratt method, and
14. Discuss the fundamentals of Data Compression, including Huffman coding and decoding algorithm.

(c) Skill development in implementation of data structures and algorithms
1. Implementation of fundamental algorithms for sorting and searching, developing benchmarking routines to profile and analyse the efficiency of the algorithms under different work loads.
2. Design and perform timing experiments on various data structures and algorithms, and learn to interpret the results obtained from the experiments.
3. Implementation of elementary and advanced data structures and the associated access algorithms
4. Application of the algorithms and data structures in various real-life software solutions. – comparison and analysis of different implementations of the same solution
5. Tweaking and fine tuning algorithms for improved performance.

Overview of Learning Activities

The learning activities included in this course are:

• key concepts will be explained in lectures, classes or online, where syllabus material will be presented and the subject matter will be illustrated with demonstrations and examples;
• tutorials and/or labs and/or group discussions (including online forums) focussed on projects and problem solving will provide practice in the application of theory and procedures, allow exploration of concepts with teaching staff and other students, and give feedback on your progress and understanding;
• assignments, as described in Overview of Assessment (below) and Assessment Tasks (part B course guide for this Teaching Period), requiring an integrated understanding of the subject matter; and
• private study, working through the course as presented in classes and learning materials, and gaining practice at solving conceptual and technical problems.

Overview of Learning Resources

You will make extensive use of computer laboratories and relevant software provided by the School. You will be able to access course information and learning materials through the Learning Hub (also known as online@RMIT) and may be provided with copies of additional materials in class or via email. Lists of relevant reference texts, resources in the library and freely accessible Internet sites will be provided.

Use the RMIT Bookshop’s textbook list search page to find any recommended textbook(s).

Overview of Assessment

See Assessment Tasks (part B course guide for this Teaching Period) for assessment details, including deadlines, weightings, and hurdle requirements.

For standard assessment information relating to Computer Science and IT courses see: http://www.rmit.edu.au/csit/cgi