Workload - Private Study - Assessment - Description - Aims - Learning Outcomes - Content - Teaching Materials - Recommended Books

Module Code | COM00007C |
---|---|

Lecturers | Mike Dodds, Lilian Blot, Steve King |

Taken By | CS 1, CS/Math 1, CS/Phil 1, CSESE 1, CSYS 1, MEng CS 1, MEng CS/Phil 1, MEng CSAI 1, MEng CSESE 1, MEng CSYS 1, MMath 1 |

Number of Credits | 20 |

Teaching | Autumn 2-5 & 7-10, Spring 2-4 & 7-10, Summer 1-4 |

Closed Assessments | [50%] Closed Lab Assessment, Summer 5, 3 hours |

[50%] Closed Exam Summer 5-7, 2.00 hours | |

Reassessment |
[100%]
Closed Lab Practical, August Resit Week, 3.0 hours, 3.00 hours |

- Lectures: 36 x 1hr
- Software Labs: 14 x 2hrs
- Problem Classes: 10 x 1hr
- Private Study: 94hrs
- Assessment: 1 x 2hrs
- Formative Assessment: 4 x 1hr
- Homework: 10 x 2hrs
- Lab Formative Assess: 2 x 1.5hrs
- Software Lab Assessm: 1 x 3hrs

Students are expected to spend private study time reading around the material from lectures, and working on practical material not completed during the laboratory sessions. The programming exercises provided during software labs are the minimum required to pass the module, however we strongly encourage beginners to do more programming than what was given during practicals, they should try to design and implement some small project of their own.

- Closed Lab Assessment, Summer 5, 3 hours
- Closed Exam Summer 5-7, 2.00 hours

The assessment is split into:

1 x 1 hour formative written exam to test theoretical concepts

2 x 1.5 hour formative exams (laboratory based)

1 x 2 hour closed summative written exam to test theoretical concepts

1 x 3 hour closed summative exam (laboratory based) to test practical programming skills

Feedback will be provided on an informal basis weekly during the practical laboratory sessions. In addition, the formative assessments in Autumn and Spring terms will provide written feedback to each student.

The module aims and learning outcomes have been designed in such a way that it should be possible to teach this module in a variety of languages. TPOP is designed as the foundation for the stage 2 programming-theme module.

This module is a combination of theory and practical work synchronised as much as possible. The practical work supports the development of the theory. The practical side of the course will allow you to implement aspects from the theory, allowing you to develop key skills of software design and develop the understanding of when and where to adopt various techniques, and show appropriate methods of design and testing.

Overall, the module is designed to allow you:

to gain an understanding of theoretical and practical aspects of algorithm and data structure design

to be familiar with theoretical tools for understanding algorithm and data structure complexity

to develop an understanding of the basic concepts of software engineering

to apply theoretical concepts in a practical setting

The aims of this module are to:

- to gain an understanding of theoretical and practical aspects of algorithm and data structure design

- to be familiar with theoretical tools for understanding algorithm and data structure complexity

- to develop an understanding of the basic concepts of software engineering

- to apply theoretical concepts in a practical setting

Students should be able to:

Demonstrate the ability to select and apply of a variety of algorithms and data structures suited to each given problem

Understand issues of complexity with respect to algorithms

Demonstrate competence in programming through the development of a significant application

Demonstrate the ability to extend and edit existing large programs

Demonstrate appropriate software testing strategies

Demonstrate effective use of support tools such as debugging, documentation tools and programming environments

Introduce the basics of the paradigm being taught, basic concepts such as storage, iteration, selection, functions (procedures), basic testing, coding standards/commenting. In addition, more advanced concepts are introduced later in the year, such as Object Oriented Programming (OOP) and used to implement data structures and algorithm seen in the theory section of the module. The List of such data structures and algorithm is given below.

Tools for algorithm analysis: Empirical algorithm analysis, Asymptotic analysis - introduce the mathematical tools of asymptotic analysis, big-oh notation, complexity theory, dominance.

Linear data structures

Intro to ADTs - concrete versus abstract, contiguous versus linked

Arrays

Dynamic arrays (+amortized analysis)

Linked list

Linear ADTs: stacks, queues, deques

Linear Dictionaries

Sorting

Quadratic sorters (selection/insertion)

Divide-and-conquer (merge sort)

Limits of comparison-based sorting

Dutch national flag

Programming linear data structures

Sorting continued

Quicksort and randomised analysis

Shellsort

Stable sorts

Selection

Trees

Intro to trees

Binary search tree

Implementing BST as array/linked structure

Search/insert/delete/in-order traversal

Min/max, predecessor/successor

AVL trees - rotation and rebalancing

Priority queues and heaps

Intro to priority queue ADT

Notions of priority - implementation using stacks/queues

Implementations using linear structures/binary search trees

Binary heap ADT/implementation using array

Build heap

Heapsort

Hash tables

Direct addressing

Hashing with chaining

Closed hashing

Analysis of simple uniform hashing

Linear/quadratic probing, double hashing, rehashing

Graphs

Intro to graphs/flavours of graphs

Adjacency matrix/adjacency list representations

Breadth/depth-first search

Minimum spanning trees

Generic solution

Prim/Kruskal's algorithms

Union-find data structure

Shortest paths

Negative edge weights

Edge relaxation

Topological sort/shortest paths on DAGs

Dijkstra's algorithm

Solving Algorithmic Problems -- Putting it all together

Rigorous problem specifications

Types of problems

Types of algorithms

Matching algorithm types to problems

Finding and applying known algorithms

Adapting known algorithms

Designing new algorithms

Choosing among alternative algorithms

Lots of examples

There is no text book for the Programming section of the module. There are however many books available in the library, in addition to free resources online. A Resource section with links to web resources is given in the module webpage.

Lecture notes, videos, exercises and their model answers, and past papers are available on the module webpage.

Rating | Author | Title | Publisher | Year |
---|---|---|---|---|

*** | Skiena, S | The Algorithm Design Manual | Springer | 2008 |

*** | Bradley N. Miller, David L. Ranum | Python Programming In Context, 2ed | Jones and Bartlett | 2013 |

** | Abelson, Sussman and Sussman | Structure and Interpretation of Computer Programs | MIT Press | 1996 |

** | Mehlhorn and Sanders | Algorithms and Data Structures: The basic tool box | Springer | 2008 |

** | Cormen et al. | Introduction to Algorithms | MIT Press | 2001 |

** | A. Levitin | Introduction to the Design and Analysis of Algorithms (2nd or 3rd ed) | Pearson | 2012 |

Last updated: 19^{th} September 2016