CS2AO17-Algorithms and Operating Systems

Module Provider: Computer Science
Number of credits: 20 [10 ECTS credits]
Level:5
Terms in which taught: Autumn / Spring / Summer module
Pre-requisites: CS1FC16 Fundamentals of Computer Science and CS1PR16 Programming
Non-modular pre-requisites:
Co-requisites:
Modules excluded:
Current from: 2019/0

Module Convenor: Prof Xia Hong

Email: x.hong@reading.ac.uk

Type of module:

Summary module description:

Algorithms and Operating Systems are fundamental concepts in Computer Science discipline. The module gives an introduction to fundamental algorithm design strategies that are common to many concrete applications. It also explores the features underlying the concepts of Operating Systems and provides experience of practical aspects related to core concepts in the area.

Aims:

The module consists two parts. The first part, Algorithms, is one of the cornerstones of computer science and the aim of this part is to provide an appreciation of the concepts involved in the design and analysis of algorithms. The second part, Operating Systems, aims to provide an insight into the underlying theory and practical aspects that make up the cornerstone of computer science from the point view of machine operations.

This module also encourages students to develop a set of professional, skills such as problem solving, logic thinking, creativity and numeracy.

Assessable learning outcomes:

On completion of the module a student should be able to:

• Identify the fundamental strategies in algorithmic design;


• Distinguish which strategy is appropriate to solve a given problem;


• Classify different algorithmic strategies;


• Analyze a given algorithm and assess its efficiency;


• Apply techniques of proof by induction to verify certain properties of algorithms;


• Describe various virtualisation abstractions underlying operating systems;


• Identify the fundamental structures of an operating system and the notion of universality that arises in several resource management contexts;


• Demonstrate insights into notions of concurrency and their practical realisation;


• Analyze the performance of design alternatives arising in virtualisations using relevant criteria;


• Apply techniques of virtualisation in the concrete design of operating systems and application layers.

Additional outcomes:
Students will have seen a number of useful case studies illustrating the techniques which can be transported to other areas of the course. Through practical work students will gain deeper insights into concurrent and multi-threading implementations of programs.

Outline content:

• Additional Data structures (Heaps, Graphs);

• Divide and Conquer (General method, Analysis, examples - Sorting, Convex Hull, Matrix Multiplication);

• The Greedy method (General method, Analysis, examples - Shortest Paths, Spanning Trees);

• Dynamic Programming (General method, Analysis, Travelling salesperson, Transitive Closure);

• Consolidation (revisit examples using alternative methods);

• Operating System Structure (Virtualisation, System Calls, notion of Universality);

• Concurrency (Processes, Threads);

• File System (File Management, Disk Arm Scheduling, Case Study);

• Inter-process Communication (shared vs. message passing, Mutual exclusion, locking algorithms);

• Scheduling (Scheduler classes, Scheduling algorithms, Case study);

• Memory Management (Segmentation, Paging, limits of multi-programming);

• Security and Protection (Protection domain, Authentication, Multi-level Security).

Brief description of teaching and learning methods:

Lectures and practicals.

Contact hours:

	Autumn	Spring	Summer
Lectures	20	20
Tutorials			2
Practicals classes and workshops		6
Guided independent study:	79	73
Total hours by term	99	99	2
Total hours for module	200

Summative Assessment Methods:

Method	Percentage
Written exam	70
Set exercise	30

Summative assessment- Examinations:

One 3 hour examination paper in May/June.

Summative assessment- Coursework and in-class tests:

Formative assessment methods:

Penalties for late submission:
The Module Convener will apply the following penalties for work submitted late:

where the piece of work is submitted after the original deadline (or any formally agreed extension to the deadline): 10% of the total marks available for that piece of work will be deducted from the mark for each working day[1] (or part thereof) following the deadline up to a total of five working days;

where the piece of work is submitted more than five working days after the original deadline (or any formally agreed extension to the deadline): a mark of zero will be recorded.

The University policy statement on penalties for late submission can be found at: http://www.reading.ac.uk/web/FILES/qualitysupport/penaltiesforlatesubmission.pdf
You are strongly advised to ensure that coursework is submitted by the relevant deadline. You should note that it is advisable to submit work in an unfinished state rather than to fail to submit any work.

Assessment requirements for a pass:

A mark of 40% overall.

Reassessment arrangements:

One examination paper of 3 hours duration in August/September - the resit module mark will be the higher of the exam mark (100% exam) and the exam mark plus previous coursework marks (70% exam, 30% coursework).

Additional Costs (specified where applicable):
1) Required text books:
2) Specialist equipment or materials:
3) Specialist clothing, footwear or headgear:
4) Printing and binding:
5) Computers and devices with a particular specification:
6) Travel, accommodation and subsistence:

Last updated: 8 April 2019