Skip to navigation | Skip to main content | Skip to footer
Menu
Menu

COMP26912: Algorithms and Imperative Programming (2010-2011)

This is an archived syllabus from 2010-2011

Algorithms and Imperative Programming
Level: 2
Credit rating: 10
Pre-requisites: COMP10081 (or equivalent)
Co-requisites: none
Duration: 11 weeks in second semester
Lectures: 11 in total, 1 per week
Examples classes: none
Labs: 22 hours in total, 11 2-hour sessions, 1 per week
Lecturers: Pete Jinks, Joshua Knowles, Milan Mihajlovic, David Rydeheard
Course lecturers: Pete Jinks

Joshua Knowles

Milan Mihajlovic

David Rydeheard

Additional staff: view all staff
Timetable
SemesterEventLocationDayTimeGroup
Sem 2 Lecture LF17 Fri 15:00 - 16:00 E
Sem 2 w2+ Lab UNIX Mon 10:00 - 12:00 E
Assessment Breakdown
Exam: 50%
Coursework: 0%
Lab: 50%

Introduction

This is a one-semester practical introduction to algorithms and data structures, concentrating on devising and using algorithms, including algorithm design and performance issues as well as `algorithmic literacy' - knowing what algorithms are available and how and when to use them.

To reflect the emphasis on practical issues, there are two practical (laboratory) hours to each lectured hour. Lectures serve to motivate the subject, orient students, reflect on practical exercises and impart some basic information. A range of practical applications of algorithms will also be presented in the lectures. Other information resources will be important, including a set textbook, which will provide essential support.

Aims

To make best use of available learning time by encouraging active learning and by transmitting information in the most effective ways.
To make students aware of the importance of algorithmic concerns in real-life Computer Science situations.
To emphasise practical concerns, rather than mathematical analysis.
To become confident with a range of data structures and algorithms and able to apply them in realistic tasks.

Programme outcomeUnit learning outcomesAssessment
A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Able to reason about performance and algorithmic complexity.
  • Examination
  • Lab assessment
A2 A3 A4 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Able to informally reason about algorithmic correctness.
  • Examination
  • Lab assessment
A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Able to use a range of basic data structures: arrays, lists, trees, and graphs.
  • Examination
  • Lab assessment
A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Experience of a range of basic algorithms including searching and sorting, tree traversal and manipulation, and some basic graph algorithms.
  • Lab assessment
  • Examination
A2 A3 A4 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Practical experience in `algorithmic literacy' - knowing how to use the extensive literature on the subject, recognising what algorithms to use in applications and assessing their utility.
  • Lab assessment
  • Examination
A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Able to program in C.
  • Lab assessment

Syllabus

Algorithms - what they are and how to express them (in pseudocode and selected programming languages: Java and C).

Practical experience in devising, assessing and using algorithms:
-- considerable practice in algorithmic problem solving for realistic problems
-- examples from a wide range of application areas
-- finding appropriate algorithms and data-structures
-- inventing appropriate algorithms and data-structures

Practical experience in `algorithmic literacy' - knowing how to use the extensive literature on the subject, recognising what algorithms to use in applications and assessing their utility.

A range of basic data structures: arrays, lists, trees (including ordered and balanced trees and heaps), and various kinds of graphs. Representations of basic data structures in programming languages.

A range of basic algorithms: searching and sorting algorithms, tree traversal and manipulation algorithms, some basic graph algorithms. Other algorithmic areas will be explored through practical examples.

An introduction to algorithmic performance: space and time requirements, worst-case, average-case and best case estimates. Practical experience and techniques for measuring and predicting performance: Counting operations.
Scaling and some common rates of growth.

Reasoning about algorithms - experience in informally reasoning about algorithms to establish correctness.

Reading List

All students are urged to get hold of a copy of the core text and read it. Practical exercises, course material and examinations will be based on the core text. Lectures will not normally supply the required content, but we may supplement the book where additional material is required.

There are many books published on "Algorithms and Data structures", many are of low quality and not recommended. Some high quality textbooks are listed below as "Supplementary". In particular, you are urged to consult some of the classic texts in the area. The chief of these is by Donald Knuth in his classic series of books which set the foundations for the subject.

Core Text
Title: Algorithm design and applications
Author: Goodrich, Michael T. and Roberto Tamassia
ISBN: 9781118335918
Publisher: Wiley
Edition:
Year: 2014
This is a fairly comprehensive book, at the right level for the course-unit, and covers almost all the required material.


Supplementary Text
Title: Algorithms in Java (3rd edition): parts 1-4: fundamentals, data structures, sorting, searching
Author: Sedgewick, Robert (with Schidlowsky, Michael)
ISBN: 0201361205
Publisher: Addison Wesley
Edition: 3rd
Year: 2003
Part 5 (graph algorithms) is separate volume: ISBN 0201361213


Supplementary Text
Title: Algorithms in Java (3rd edition): part 5: graph algorithms
Author: Sedgewick, Robert (with Schidlowsky, Michael)
ISBN: 0201361213
Publisher: Addison Wesley
Edition: 3rd
Year: 2004
Parts 1-4 (fundamentals, data structures, sorting, searching) are one separate volume: ISBN 0201361205


Supplementary Text
Title: Data structures and problem solving using Java (4th edition)
Author: Weiss, Mark Allen
ISBN: 9780321546227
Publisher: Pearson
Edition: 4th
Year: 2008
This is a good quality book at the right level for the course unit.


Supplementary Text
Title: Art of computer programming: volume 3 -sorting and searching (2nd edition)
Author: Knuth, Donald E.
ISBN: 0201896850
Publisher: Addison Wesley
Edition: 2nd
Year: 1997
Previous editions published under the title "Fundamentals of Computing". A classic series of books which set the foundations for the subject.


Supplementary Text
Title: Algorithms in C++ (3rd edition): part 5: graph algorithms
Author: Sedgewick, Robert (with van Wyk, Christopher J.)
ISBN: 0201361183
Publisher: Addison Wesley
Edition: 3rd
Year: 2002
Parts 1-4 (fundamentals, data structures, sorting, searching) are one separate volume: ISBN 0201350882


Supplementary Text
Title: Algorithms in C++ (3rd edition): parts 1-4: fundamentals, data structures, sorting, searching
Author: Sedgewick, Robert (with van Wyk, Christopher J.)
ISBN: 0201350882
Publisher: Addison Wesley
Edition: 3rd
Year: 1998
Part 5 (graph algorithms) is separate volume: ISBN 0201361183


Supplementary Text
Title: Algorithmics: the spirit of computing (3rd edition)
Author: Harel, David (with Yishai Feldman)
ISBN: 9780321117847
Publisher: Addison Wesley
Edition: 3rd
Year: 2004
A good informal and very readable non-technical introduction to the subject


Supplementary Text
Title: Art of computer programming: volume 1 - fundamental algorithms (3rd edition)
Author: Knuth, Donald E.
ISBN: 0201896834
Publisher: Addison Wesley
Edition: 3rd
Year: 1997
Previous editions published under the title "Fundamentals of Computing". A classic series of books which set the foundations for the subject.


Supplementary Text
Title: Algorithms in C (3rd edition): parts 1-4: fundamentals, data structures, sorting, searching
Author: Sedgewick, Robert
ISBN: 0201314525
Publisher: Addison Wesley
Edition: 3rd
Year: 1998
Part 5 (graph algorithms) is separate volume: ISBN 0201316633


Supplementary Text
Title: Algorithms in C (3rd edition): part 5: graph algorithms
Author: Sedgewick, Robert
ISBN: 0201316633
Publisher: Addison Wesley
Edition: 3rd
Year: 2002
Parts 1-4 (fundamentals, data structures, sorting, searching) are one separate volume: ISBN 0201314525


Supplementary Text
Title: Introduction to algorithms (3rd edition)
Author: Cormen, Thomas L. et al.
ISBN: 9780262533058
Publisher: MIT Press
Edition: 3rd
Year: 2009
This is an encyclopaedic reference, well written and extremely thorough


Supplementary Text
Title: Art of computer programming: volume 2 -seminumerical algorithms (3rd edition)
Author: Knuth, Donald E.
ISBN: 0201896842
Publisher: Addison Wesley
Edition: 3rd
Year: 1997
Previous editions published under the title "Fundamentals of Computing". A classic series of books which set the foundations for the subject.