COMP26120 Algorithms and Imperative Programming syllabus 2014-2015
This is a two-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.
The course-unit starts with a 5-week primer on the C programming language, enabling students to become competent programmers in this language as well as in Java (and, possibly, in other languages). This teaching is supported by an on-line C course and extensive laboratory exercises.
There is a follow-up course unit on Advanced Algorithms in the Third Year. This presents the foundational areas of the subject, including (1) measures of algorithmic performance and the classification of computational tasks by the performance of algorithms, (2) formulating and presenting correctness arguments, as well as (3) a range of advanced algorithms, their structure and applications.
To make best use of available learning time by encouraging active learning and by transmitting information in the most effective ways.
To give students a genuine experience of C.
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.
C for Java programmers (up to reading week)
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.
22 in total, 1 per week
44 hours in total, 22 2-hour sessions, 1 per week
Feedback methodsFeedback is via a variety of methods. Immediate feedback is provided in weekly laboratory sessions. There are tutorial sessions based on work in this course unit, with feedback on the exercises. Exam feedback is provided both on a website and on individual scripts.
- Assessment written exam (4 hours)
- Lectures (24 hours)
- Practical classes & workshops (48 hours)
- Analytical skills
- Oral communication
- Problem solving
|Programme outcome||Unit learning outcomes||Assessment|
|A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6||Able to program in C.|
|A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6||Able to reason about performance and algorithmic complexity.|
|A2 A3 A4 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6||Able to informally reason about algorithmic correctness.|
|A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6||Able to use a range of basic data structures: arrays, lists, trees, and graphs.|
|A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6||Experience of a range of basic algorithms including searching and sorting, tree traversal and manipulation, and some basic graph algorithms.|
|A2 A3 A4 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6||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.|
|Algorithm design and applications||Goodrich, Michael T. and Roberto Tamassia||9781118335918||Wiley||2014||✔|
|Algorithms in Java (3rd edition): part 5: graph algorithms||Sedgewick, Robert (with Schidlowsky, Michael)||0201361213||Addison Wesley||2004||✖|
|Art of computer programming: volume 3 -sorting and searching (2nd edition)||Knuth, Donald E.||0201896850||Addison Wesley||1997||✖|
|Algorithms in C++ (3rd edition): parts 1-4: fundamentals, data structures, sorting, searching||Sedgewick, Robert (with van Wyk, Christopher J.)||0201350882||Addison Wesley||1998||✖|
|Expert C programming: deep C secrets||van der Linden, Peter||0131774298||Prentice Hall||1994||✖|
|C programming language (2nd edition)||Kernighan, Brian W. and Dennis M. Ritchie||9780131103627||Prentice Hall||1988||✖|
|Art of computer programming: volume 2 -seminumerical algorithms (3rd edition)||Knuth, Donald E.||0201896842||Addison Wesley||1997||✖|
|Algorithms in C (3rd edition): part 5: graph algorithms||Sedgewick, Robert||0201316633||Addison Wesley||2002||✖|
|Algorithms in Java (3rd edition): parts 1-4: fundamentals, data structures, sorting, searching||Sedgewick, Robert (with Schidlowsky, Michael)||0201361205||Addison Wesley||2003||✖|
|Art of computer programming: volume 1 - fundamental algorithms (3rd edition)||Knuth, Donald E.||0201896834||Addison Wesley||1997||✖|
|Algorithms in C++ (3rd edition): part 5: graph algorithms||Sedgewick, Robert (with van Wyk, Christopher J.)||0201361183||Addison Wesley||2002||✖|
|Introduction to algorithms (3rd edition)||Cormen, Thomas L. et al.||9780262533058||MIT Press||2009||✖|
|C: a reference manual (5th edition)||Harbison, Samuel P. and Guy L. Steele Jr.||013089592X||Prentice Hall||2002||✖|
|Algorithmics: the spirit of computing (3rd edition)||Harel, David (with Yishai Feldman)||9780321117847||Addison Wesley||2004||✖|
|Algorithms in C (3rd edition): parts 1-4: fundamentals, data structures, sorting, searching||Sedgewick, Robert||0201314525||Addison Wesley||1998||✖|
|Data structures and problem solving using Java (4th edition)||Weiss, Mark Allen||9780321546227||Pearson||2008||✖|
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.