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

COMP26120 Algorithms and Imperative Programming syllabus 2018-2019

COMP26120 materials

COMP26120 Algorithms and Imperative Programming

Level 2
Credits: 20
Enrolled students: 227

Course leader: Giles Reger


Additional staff: view all staff

Requisites

  • Pre-Requisite (Compulsory): COMP16121
  • Pre-Requisite (Compulsory): COMP16212

Additional requirements

  • Students who are not from the School of Computer Science must have permission from both Computer Science and their home School to enrol.

    Alternative equivalent knowledge of Java accepted.

Assessment methods

  • 50% Written exam
  • 50% Practical skills assessment
Timetable
SemesterEventLocationDayTimeGroup
Sem 1 Lecture Roscoe TH B Mon 14:00 - 15:00 -
Sem 1 w2+ Lab G23 Thu 11:00 - 13:00 H
Sem 1 w2+ Lab Toot (0 + 1) Tue 14:00 - 16:00 F
Sem 1 w2+ Lab G23 Thu 16:00 - 18:00 G
Sem 2 Lab G23 Tue 09:00 - 11:00 R
Sem 2 Lab G23 Wed 10:00 - 12:00 Q
Sem 2 Lab G23 Fri 15:00 - 17:00 S
Sem 2 Lecture 1.1 Fri 11:00 - 12:00 -
Themes to which this unit belongs
  • Programming and Algorithms
  • Computer Languages

Overview

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.

Aims

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.

Syllabus

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.

Teaching methods

Lectures

22 in total, 1 per week

Laboratories

44 hours in total, 22 2-hour sessions, 1 per week

Feedback methods

Feedback 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.

Study hours

  • Assessment written exam (4 hours)
  • Lectures (24 hours)
  • Practical classes & workshops (48 hours)

Employability skills

  • Analytical skills
  • Innovation/creativity
  • Oral communication
  • Problem solving

Learning outcomes

Programme outcomeUnit learning outcomesAssessment
A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Write C programs making use of standard constructs and memory management operations
  • Lab assessment
A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Define standard notions of asymptotic complexity and use these to reason about the complexity of algorithms
  • Lab assessment
  • Examination
A2 A3 A4 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Use pseudocode to represent algorithms and informally reason about their correctness
  • Examination
  • Lab assessment
A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Recall the definitions and representations of basic data structures and the complexity of the operations on them
  • Examination
  • Lab assessment
A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Explain, using examples of real-world applications, standard algorithmic problems coming from sorting and searching on different data structures, operations on graphs, and number theory
  • Lab assessment
  • Examination
A2 A3 A4 B1 B2 B3 C4 C5 C6 D2 D4 D5 D6Identify from a set of taught algorithms, which algorithm should apply in a given situation, explain how it should be applied, and compare the solution to possible alternatives
  • Examination
  • Lab assessment
A2 A3 B1 B2 B3 C4 C5 C6 D2 D4 D6Explain the concepts of divide-and-conquer, dynamic programming, and greedy algorithms, discuss when they are appropriate, and apply them to solve problems
A1Recall and explain the notions of tractability and NP-completeness with a particular focus on classical NP-complete problems
  • Examination
  • Lab assessment

Reading list

TitleAuthorISBNPublisherYearCore
Algorithm design and applicationsGoodrich, Michael T. and Roberto Tamassia9781118335918Wiley2014
C: a reference manual (5th edition)Harbison, Samuel P. and Guy L. Steele Jr.013089592XPrentice Hall2002
Algorithms in C (3rd edition): parts 1-4: fundamentals, data structures, sorting, searchingSedgewick, Robert0201314525Addison Wesley1998
Art of computer programming: volume 3 -sorting and searching (2nd edition)Knuth, Donald E.0201896850Addison Wesley1997
Algorithms in C++ (3rd edition): part 5: graph algorithmsSedgewick, Robert (with van Wyk, Christopher J.)0201361183Addison Wesley2002
Algorithms in Java (3rd edition): parts 1-4: fundamentals, data structures, sorting, searchingSedgewick, Robert (with Schidlowsky, Michael)0201361205Addison Wesley2003
Expert C programming: deep C secretsvan der Linden, Peter0131774298Prentice Hall1994
Algorithmics: the spirit of computing (3rd edition)Harel, David (with Yishai Feldman)9780321117847Addison Wesley2004
Art of computer programming: volume 2 -seminumerical algorithms (3rd edition)Knuth, Donald E.0201896842Addison Wesley1997
C programming language (2nd edition)Kernighan, Brian W. and Dennis M. Ritchie9780131103627Prentice Hall1988
Algorithms in C (3rd edition): part 5: graph algorithmsSedgewick, Robert 0201316633Addison Wesley2002
Art of computer programming: volume 1 - fundamental algorithms (3rd edition)Knuth, Donald E.0201896834Addison Wesley1997
Algorithms in C++ (3rd edition): parts 1-4: fundamentals, data structures, sorting, searchingSedgewick, Robert (with van Wyk, Christopher J.)0201350882Addison Wesley1998
Algorithms in Java (3rd edition): part 5: graph algorithmsSedgewick, Robert (with Schidlowsky, Michael)0201361213Addison Wesley2004
Data structures and problem solving using Java (4th edition)Weiss, Mark Allen9780321546227Pearson2008

Additional notes

Course unit materials

Links to course unit teaching materials can be found on the School of Computer Science website for current students.