Monash University Handbook 2010 Undergraduate - Unit

Level	Undergraduate
Faculty	Faculty of Information Technology
Offered	Clayton First semester 2010 (Day) Clayton Second semester 2010 (Day)
Coordinator(s)	Dr Peter Tischer

Synopsis

Algorithms are recipes for solving a problem. They are fundamental to computer science and software engineering. Algorithms are the formal foundation of computer programming but also exist independently of computers as systematic problem-solving procedures. This unit introduces algorithmics, the study of algorithms. It is not about programming and coding but rather about understanding and analysing algorithms and about algorithmic problem-solving, i.e. the design of systematic problem-solving procedures. The unit is very hands-on and students will develop algorithms to solve a wide variety of different problems, working individually as well as together in groups and as a class.

The unit will not require any knowledge of a programming language. The initial instruction will be performed independently of any programming language and only use simple pseudo-code that will be developed from scratch in the unit. Various means of visualising algorithm execution (manipulating sets of tangible physical object, using turtle graphics, using algorithm visualisations) will be employed to enable the students to trace the execution of algorithms and to complement their formal understanding with an intuitive understanding. Later stages of the unit will make use of the coding knowledge developed in FIT1002 to demonstrate how pseudo-code algorithms can be mapped to concrete programs.

Topics include: What is a computational problem and what is an algorithm; Basic control structures; basic data structures; Modular Algorithm Structure; Recursion; Problem-solving strategies for algorithm development; Arguing correctness of an algorithm; Arguing termination of an algorithm; Understanding the efficiency of an algorithm; and Limitations of algorithms.

Objectives

At the completion of this unit students will have -
A knowledge and understanding of:

• the difference between algorithms and processes;
• basic ways to structure algorithms: basic data structures (simple variables, collections structure, specifically vectors, lists, sets, and tables); basic control structures (sequence, choice, iteration);
• recursion;
• modular algorithm structures;
• the equivalence of recursion and iteration;
• problem solving strategies suitable for algorithm development including top-down design and bottom-up design;
• simple standard patterns for algorithms (eg traversal, search);
• what makes a good algorithm
• limitations of algorithms (high level).

Developed the skills to:

• develop simple iterative and recursive algorithms
• argue the correctness of simple algorithms
• judge the efficiency of simple algorithms, and

Developed attitudes that enable them to:

• value clear specification of problems;
• understand the relation between algorithms and programs;
• appreciate the value of designing abstract algorithms before starting to code a program;
• have confidence that they can develop algorithms to solve computational problems;
• appreciate that seemingly difficult problems can have very simple elegant algorithmic solutions (and vice versa);
• value correctness arguments for algorithms; and
• value the importance of simplicity and efficiency.

Demonstrated the communication skills necessary to:

• solve a problem by discussing possible approaches and solutions as a team; and
• clearly communicate (the specification of) a computational problem, its algorithmic solution and arguments for correctness and efficiency.

Assessment

Examination (3 hours): 60%; In-semester assessment: 40%

Chief examiner(s)

Dr David Albrecht

Contact hours

2 hrs lectures/wk, 2 hrs tutorials/wk

Prerequisites

Only for students in the Bachelor of Computer Science and Bachelor of Software Engineering, associated Double Degrees and major/minor sequences. Exceptions can be approved by the unit leader after assessment of mathematical background knowledge.

Co-requisites

FIT1002

Additional information on this unit is available from the faculty at:

http://www.infotech.monash.edu/units/fit1029/