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

COMP26120 Algorithms and Data Structures syllabus 2020-2021

COMP26120 materials

COMP26120 Algorithms and Data Structures

Level 2
Credits: 20
Enrolled students: 266

Course leader: Giles Reger


Additional staff: view all staff

Additional requirements

  • Alternative equivalent knowledge of Java accepted.

Assessment methods

  • 50% Written exam
  • 50% Practical skills assessment
Timetable
SemesterEventLocationDayTimeGroup
Sem 1 w2-12 ONLINE Lecture Thu 14:00 - 15:00 -
Sem 1 w3-12 ONLINE LabORATORY Mon 12:00 - 13:00 G
Sem 1 w3-12 ONLINE LabORATORY Mon 13:00 - 14:00 G
Sem 1 w3-12 ONLINE LabORATORY Mon 14:00 - 15:00 H
Sem 1 w3-12 ONLINE LabORATORY Mon 15:00 - 16:00 H
Sem 1 w3-12 ONLINE LabORATORY Thu 16:00 - 17:00 F
Sem 1 w3-12 ONLINE LabORATORY Thu 17:00 - 18:00 F
Sem 2 ONLINE LabORATORY GO2+IT407 Thu 09:00 - 11:00 G
Sem 2 w20-26,29-33 ONLINE Lecture Mon 11:00 - 12:00 -
Sem 2 ONLINE LabORATORY GO2+IT407 Mon 14:00 - 16:00 F
Sem 2 ONLINE LabORATORY GO2+IT407 Tue 16:00 - 18:00 H
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.

This course unit detail provides the framework for delivery in 20/21 and may be subject to change due to any additional Covid-19 impact.  Please see Blackboard / course unit related emails for any further updates.

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.

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.

Teaching methods

Lectures

22 in total, 1 per week

Laboratories

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

Lectures are brief with examinable content also being introduced in lab exercises
 
Three Blackboard quizzes each semester provide early feedback on examinable concepts
 
An online tool is used in lab exercises, allowing students to generate automatic feedback on their programming solutions
 

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

On successful completion of this unit, a student will be able to:

  • ILO 1 Analyse problems to identify and implement the most appropriate algorithmic solution
  • ILO 2 Define standard notions of asymptotic complexity and use these to reason about the complexity of algorithms
  • ILO 3 Use pseudocode to represent algorithms and informally reason about their correctness 
  • ILO 4 Recall the definitions and representations of basic data structures and the complexity of the operations on them
  • ILO 5 Explain, using examples of real-world applications, standard algorithmic problems coming from sorting and searching on different data structures, operations on graphs, and number theory
  • ILO 6 Identify 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 
  • ILO 7 Explain the algorithmic techniques such as divide-and-conquer, dynamic programming, greedy algorithms, and linear programming, discuss when they are appropriate, and apply them to solve problems
  • ILO 8 Recall and explain the notions of tractability and NP-completeness, with a particular focus on classical NP-complete problems, and apply these to demonstrate NP-completeness of new problems
 

Reading list

TitleAuthorISBNPublisherYear
Algorithm design and applications Goodrich, Michael T., author.9781118335918John Wiley Inc2015
Introduction to algorithms [electronic resource] null9780262270830 (electronic bk.); 0262270838 (electronic bk.); 9781628709131 (electronic bk.); 1628709138 (electronic bk.)MIT Pressc2009.
Introduction to Algorithms, Third EditionCormen, Thomas H ; Leiserson, Charles E ; Rivest, Ronald L ; Stein, Clifford9780262533058MIT Press2009
Algorithmics : the spirit of computing Harel, David, 1950-0321117840Addison-Wesley2004.
The art of computer programming. Vol.3 , Sorting and searching. Knuth, Donald E. (Donald Ervin), 1938-0201896850Addison-Wesley1998.
The art of computer programming. Vol.2, Seminumerical algorithms. Knuth, Donald E. (Donald Ervin), 1938-0201896842Addison-Wesleyc1998.
The art of computer programming. Vol.1 , Fundamental algorithms. Knuth, Donald E. (Donald Ervin), 1938-0201896834Addison-Wesley1997.
Algorithms in C Sedgewick, Robert, 1946-0201314525Addison-Wesleyc1998.
Algorithms in C Sedgewick, Robert, 1946-0201314525Addison-Wesleyc1998.
Algorithms in Java Sedgewick, Robert, 1946-0201361205Addison-Wesleyc2003.
Algorithms in Java Sedgewick, Robert, 1946-0201361213Addison-Wesley2004.
Algorithms in C++. Part 5, Graph algorithms Sedgewick, Robert, 1946-9780201361186Addison-Wesley2002.
Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, Third Edition: Fundamentals, Data Structures, Sorting, Searching Pts. 1-4Robert Sedgewick0201350882Addison-Wesley Professional; 3 edition13 July 1998
Data structures & problem solving using Java Weiss, Mark Allen.9780321541406Addison-Wesley2009.

Additional notes

Course unit materials

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