SSST - Introduction to Algorithms L5

Introduction to Algorithms L5

Programme(s) where module is offered

BSc Computer Science with Electrical Engineering;
BSc Computer Science with Economics;
BSc Computer Science with Management;
BSc Computer Science with International Relations;
BSc Computer Science with Political Science;

Status (core, option, free choice)

Core

FHEQ Level

Unit Value

8 ECTS

Term taught

Spring

Pre-Requisite Modules or Qualifications

MATH180, CS250

Module Code

CS330

Module coordinator

Dzejla Medjedovic

Applicable From

2016

Educational Aims of the Module

This module introduces students to analysis and design of computer algorithms.
Once students have taken this module, they will be able to analyze the asymptotic performance of algorithms, apply important algorithmic paradigms to problems at hand, and use algorithms in real-life engineering situations.
The module introduces students to basic problem-solving paradigms and teaches about flavors of problems solved by a particular paradigm.
The module emphasizes design over implementation of algorithms and focuses on asymptotically efficient solutions to given problems.
Throughout the module, important real-life examples are given of problems solved using particular paradigms.

Module Outline/Syllabus

Introduction to Algorithms
Asymptotic Notation, Recurrences, Master Method
Divide-and-Conquer: Strassen, Fibonacci
Quicksort, Merge sort
Skip Lists
Extending classes with inheritance
Order Statistics, Median
Hashing
Linear-time Sorting
Greedy Algorithms
Minimum Spanning Trees
Shortest Paths
Dynamic Programming
Exhaustive search and Backtracking
Introduction to NP-completeness
Reductions

Student Engagement Hours

Type	Number per Term	Duration	Total Time
Lectures	30	2 hours	60 hours
Laboratory sessions	15	2 hours	30 hours
Total Guided/Independent Learning Hours			110
Total Contact Hours			90
Total Engagement Hours			200

Assessment Method Summary

Type	Number Required	Duration / Length	Weighting	Timing / Submission Deadline
Assignment + Quiz	3	30 minutes	8*4=32%	Weeks 3, 6, 11, 14
Mid-term exam	1	90 minutes	18%	Week 9
Final exam	1	3 hours	50%	End of semester

Module Outcomes

Intended Learning Outcomes:

Understand different problem solving techniques.
Be able to use the knowledge of problem-solving paradigms practically.
Analyze worst-case runtimes of algorithms.
Argue the correctness of programs using proofs.
Understand the significance of efficient algorithms.

Teaching and Learning Strategy:

The planned lectures provide an overview of the technical material, and guide the acquisition of material available in the text. Tutorials, discussions and laboratory time are used to work through formal exercises and problems.
Tutors provide regular presentations of solutions with feedback and discussion with students. (ILO:1-5)

Assessment Strategy:

Final exam (ILO:1-5)
Mid-term exam (ILO:1, 2, 3)
Quizzes and written assignments (ILO:1-5)

Practical Skills:

Apply and/or adapt the proof techniques learned in the module to coding
Be able to recognize the appropriate problem-solving techniques for a given problem
Describe and theoretically apply in practice the divide and conquer strategy

Teaching and Learning Strategy:

Laboratory sessions with tutor-lead support (PS 1-3)
Use of quizzes to test student subject knowledge (PS:1-3)
Lectures (PS:1-3)

Assessment Strategy:

Mid-term exam (PS: 2,3)
Final exam (PS:1-3)
Assignment + Quiz (PS 1-3)

Transferable Skills:

Problem-solving skills
Rigorous mathematical thinking skills
Presentation skills
Ability to work as part of a team

Teaching and Learning Strategy:

Laboratory sessions (TS:1-2)
Assignment + Quiz (TS:1-2)
Lectures (TS:1-2)

Assessment Strategy:

Mid-term exam (TS: 1-2)
Final exam (TS:1-2)
Assignment + Quiz (TS: 1-2)

Key Texts and/or other learning materials

Set text

Cormen, T.,Leiserson,C., Rivest, R., Stein,C., (2009), Introduction to Algorithms, 3rd Edition. MIT Press

Supplementary Materials

Skiena, S., (2010). Algorithm Design Manual, 2nd edition, Springer
Dasqupta, S., Papadimitriou, C., Vazirani, U., (2006), Algorithms, McGraw-Hill
Kleinberg, J., Tardos, E., (2013), Algorithm Design, Pearson
Algorithms, (2015) Open Access Journal [online], http://www.mdpi.com/journal/algorithms (Accessed 6th June 2016)
Elsevier, (2016), Journal of Discrete Algorithms [online], http://www.journals.elsevier.com/journal-of-discrete-algorithms/open-archive (Accessed 6th June 2016)

Please note

This specification provides a concise summary of the main features of the module and the learning outcomes that a typical student might reasonably be expected to achieve and demonstrate if he/she takes full advantage of the learning opportunities that are provided.

More detailed information on the learning outcomes, content and teaching, learning and assessment methods of each module and programme can be found in the departmental or programme handbook.

The accuracy of the information contained in this document is reviewed annually by the University of Buckingham and may be checked by the Quality Assurance Agency.

Date of Production : Autumn 2016

Date approved by School Learning and Teaching Committee: 28th September 2016

Date approved by School Board of Study : 12th October 2016

Date approved by University Learning and Teaching Committee: 2nd November 2016

Date of Annual Review: December 2017

SSST Subjects

Introduction to Algorithms L5

Programme(s) where module is offered

Status (core, option, free choice)

FHEQ Level

Unit Value

Term taught

Pre-Requisite Modules or Qualifications

Module Code

Module coordinator

Applicable From

Educational Aims of the Module

Module Outline/Syllabus

Student Engagement Hours

Assessment Method Summary

Module Outcomes

Key Texts and/or other learning materials

Visit us

Contact us

Download brochure