CS2AO17NU-Algorithms and Operating Systems

Module Provider: Computer Science
Number of credits: 20 [10 ECTS credits]
Level:5
Semesters in which taught: Semester 1 / 2 module
Pre-requisites: CS1FC16NU Fundamentals of Computer Science and CS1PC20NU Programming in C/C++
Non-modular pre-requisites:
Co-requisites:
Modules excluded:
Current from: 2023/4

Module Convenor: Prof Xia Hong
Email: x.hong@reading.ac.uk

NUIST Module Lead: Chuande Liu
Email: liuchuande@nuist.edu.cn

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 provides a general understanding of the structure and the main functionalities of modern operating systems.

Ìý

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 .overview of operating systems which include: a brief history of operating systems and their development. Furthermore, it covers the main functionalities and components and their associated algorithms.Ìý

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;


• Analyse a given algorithm and assess its efficiency;


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


• Describe the general structure and purpose of an operating system;


• Explain the concepts of process, address space, and file;


• Compare and contrast various CPU scheduling algorithms;


• Understand the differences between segmented and paged memories, and be able to describe the advantages and disadvantages of each;


• Compare and contrast polled, interrupt-driven and DMA-based access to I/O devices.

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:

Algorithms:

• 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).

Operating Systems:

• Introduction to operating systems StructureÌý


• Processes: process concepts, lifecycle, process management, inter-process communication.


• Scheduling : scheduling fundamentals, CPU-I/O interleaving, (non-)preemption, context switching. Scheduling algorithms: FCFS, SJF, SRTF, priority scheduling, round robin.


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


• File System(file management, Directory and storage,Ìý hierarchies, and access control));


• Input and Output: General structure, Application I/O interface: block and character devices, buffering, blocking versus non-blocking I/O.


• Security and Protection (Protection domain, Authentication).

Ìý

Brief description of teaching and learning methods:

Lectures supported by laboratory practicals and a number of assignments.

Contact hours:

Ìý	Semester 1	Semester 2
Lectures	29	29
Practicals classes and workshops	18	18
Guided independent study:	Ìý	Ìý
Ìý Ìý Wider reading (independent)	10	12
Ìý Ìý Exam revision/preparation	10	10
Ìý Ìý Advance preparation for classes	10	10
Ìý Ìý Preparation of practical report		20
Ìý Ìý Completion of formative assessment tasks	10
Ìý Ìý Revision and preparation	10
Ìý Ìý Reflection	2	2
Ìý	Ìý	Ìý
Total hours by term	99	101
Ìý	Ìý	Ìý
Total hours for module	200

Summative Assessment Methods:

Method	Percentage
Written exam	70
Set exercise	30

Summative assessment- Examinations:

One 3-hour examination paper at the end of Semester 2.

Summative assessment- Coursework and in-class tests:

15% of Algorithms (one timed online test)

15% of Operating systems (one piece of coursework)

Formative assessment methods:

Students will be provided with feedback throughout the practical exercises.

Penalties for late submission:

The Support Centres 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 (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: /cqsd/-/media/project/functions/cqsd/documents/cqsd-old-site-documents/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 3-hour examination paper in August/September.Ìý Note that the resit module mark will be the higher of (a) the mark from this resit exam and (b) an average of this resit exam mark and previous coursework marks, weighted as per the first attempt (70% exam, 30% coursework).

Additional Costs (specified where applicable):

Last updated: 17 April 2023