MEng Software Engineering
Year of entry: 2020
Course unit details:
Algorithms and Imperative Programming
|Unit level||Level 2|
|Teaching period(s)||Full year|
|Offered by||Department of Computer Science|
|Available as a free choice unit?||Yes|
|Unit title||Unit code||Requirement type||Description|
|Object Oriented Programming with Java 1||COMP16121||Pre-Requisite||Compulsory|
|Object Oriented Programming with Java 2||COMP16212||Pre-Requisite||Compulsory|
Alternative equivalent knowledge of Java accepted.
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.
Write C programs making use of standard constructs and memory management operations
Define standard notions of asymptotic complexity and use these to reason about the complexity of algorithms
Use pseudocode to represent algorithms and informally reason about their correctness
Recall the definitions and representations of basic data structures and the complexity of the operations on them
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
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
Explain the concepts of divide-and-conquer, dynamic programming, and greedy algorithms, discuss when they are appropriate, and apply them to solve problems
Recall and explain the notions of tractability and NP-completeness with a particular focus on classical NP-complete problems
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 and learning methods
22 in total, 1 per week
44 hours in total, 22 2-hour sessions, 1 per week
- Analytical skills
- Oral communication
- Problem solving
|Practical skills assessment||50%|
COMP26120 reading list can be found on the School of Computer Science website for current students.
|Scheduled activity hours|
|Assessment written exam||4|
|Practical classes & workshops||48|
|Independent study hours|
|Giles Reger||Unit coordinator|
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.