Unit information: Principles of Programming in 2011/12

Unit name	Principles of Programming
Unit code	COMS11600
Credit points	10
Level of study	C/4
Teaching block(s)	Teaching Block 1 (weeks 1 - 12)
Unit director	Dr. Reinhard
Open unit status	Not open
Pre-requisites	None
Co-requisites	EMAT10714 Discrete Mathematics for Computer Scientists I, COMS11300 Procedural Programming or COMS11800 Programming Project
School/department	Department of Computer Science
Faculty	Faculty of Engineering

Description including Unit Aims

The purpose of this unit is to introduce you to techniques necessary for reasoning about computer programmes in a language-independent manner. The unit introduces algorithmic techniques, time complexity analysis of algorithms, algorithm specifications and proofs of correctness, classical algorithms and data structures.

Aims:

The unit aims to introduce techniques necessary for reasoning about computer programs in a language-independent manner, particularly algorithmic techniques, time complexity analysis of algorithms, algorithm specifications and proofs of correctness, classical algorithms and data structures.

Intended Learning Outcomes

On completion of the unit you will have an in-depth understanding of:

• Data structures (binary tree, binary search tree, AVL tree, heap, hash table)

• Algorithms (Fibonacci, greedy algorithms, Huffman coding, insertion sort, merge sort, quick sort, radix sort, bucket sort, comparison-based sorting)

• Time complexity (big oh, big omega, big theta, recurrence relations, analysis of loops)

• Correctness (pre- and post-conditions, loop invariants, weak and strong induction)

Teaching Information

Lectures and supervised lab sessions.

Assessment Information

Assessment: CW1 (10%), CW2 (20%), Exam (70%)

Reading and References

Algorithm Design: Foundations, Analysis, and Internet Examples. M. T. Goodrich and M. Tammasia