Monash University

Leader: Associate Professor Maria Garcia De La Banda

Offered

Clayton First semester 2008 (Day)
Clayton Second semester 2008 (Day)

Synopsis

This unit introduces students to core problem-solving, analytical skills, and methodologies useful for developing flexible, robust, and maintainable software. In doing this it covers a range of conceptual levels, from high level algorithms and data-structures, down to abstract machine models and simple assembly language programming. Topics include data structures; algorithms; object-oriented design and programming; introductory topics from software engineering; computer systems; and abstract machines.

Objectives

At the completion of this unit, students will be able to:

1. Understand abstract data types and, in particular, data structures for stacks, queues, lists, and trees, as well as their associated algorithms for creating and manipulating them. Evaluate the appropriateness of different data structures for a given problem;
2. Understand basic searching and sorting algorithms and implement them. Understand the concept of algorithmic complexity. Analyse the complexity of these searching and sorting algorithms as well as other basic algorithms. Compare the complexity of different algorithms for solving a given problem;
3. Analyse different implementations of abstract data types and determine their implications regarding complexity, functionality, and memory usage;
4. Understand the uses of recursive algorithms and data structures, their advantages and disadvantages. Analyse the complexity of simple recursive algorithms, and their relationship with iteration. Understand basic recursive algorithms for lists and trees, and develop new ones;
5. Gain a deeper understanding of basic object-oriented (OO) concepts, and learn more advanced ones such as inheritance, polymorphism, information hiding and encapsulation;
6. Understand the design principles for building an object-oriented program, such as identify classes, and determine how and when to use inheritance;
7. Understand the software development life cycle. Analyse the advantages and disadvantages of different life cycle models;
8. Understand the basic concepts in testing, including verification, validation, and reliability models. Analyse different testing approaches such as modular, static, dynamic, and formal;
9. Understand software quality and the software quality assurance process;
10. Understand the relationship between high-level and low-level programming languages. Analyse the advantages and disadvantages of using each one for solving different problems;
11. Understand the fundamentals of computer data representation including integer, signed fractional, floating point and character. Understand the basics of boolean algebra and digital logic;
12. Identify the main components of a basic computer architecture and follow the main steps in the fetch-decode-execute cycle. Recognise the main types of assembler instructions;
13. Understand the concept of Abstract Machine. Learn the basic structure and design of a particular Abstract Machine simulator. Analyse the execution in this simulator of simple iterative algorithms learned before, thus gaining a deeper understanding of the connection between software and hardware, between an algorithm and its execution.

At the completion of this unit, students will have attitudes that make them:

1. Appreciate the need to conform to programming standards when writing software;
2. Understand the need to use good design principles when constructing systems;
3. Take a patient and thorough approach to testing;
4. Acknowledge any assistance they have received in writing a program;
5. Search for information in appropriate places when necessary.

At the completion of this unit, students will be able to:

1. Create their own data-structures. Design and implement Java programs using a variety of data structures and algorithms;
2. Implement an object-oriented program consisting of many interacting classes requiring not only basic but also advance object-oriented concepts;
3. Construct a test harness for testing an object-oriented program;
4. Debug and modify an existing program (written by somebody else);
5. Use the Java API classes as part of their programs;
6. Use the Java collection classes to store and retrieve data appropriately;
7. Use the Abstract Machine simulator for executing some of the simple iterative programs learned in this subject;
8. Determine the time and space requirements of simple algorithms and data structures.

At the completion of this unit, students will be able to:

1. Document a program correctly;
2. Produce appropriate documentation for designing and testing a program;
3. Explain how parts of a program work.

Assessment

Examination (3 hours) 60%; Compulsory assessed laboratory classes: 20%; Mid-semester tests: 20%

Contact hours

7 x contact hrs/week

Prerequisites

FIT1002

Prohibitions

CSE1303, CSC1030, FIT1007, FIT1008