The descriptions are for modules currently being taught. They should be viewed as an example of the modules we provide. All modules are subject to change for later academic years.

Theory & Practice of Programming (TPOP) 2015/6

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

Workload

  • 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

Private Study

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.

Assessment

Closed Assessments

  • 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

Formative Feedback

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.

Description

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

Aims

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

Learning Outcomes

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

Content

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

Teaching Materials

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.

Recommended Books

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
Back to top

Last updated: 19th September 2016