DATA STRUCTURES AND ALGORITHMS - 2023/4
Module code: COM1029
Module Overview
Appropriate choices of data structures can expedite algorithm efficiency and also aid clear thinking when designing algorithms. It is thus natural for data structures to be studied with algorithms. An algorithm is a sequence of steps for performing some process. A computer program is not an algorithm but a representation of an algorithm. There is a need to be able to create effective algorithms, quantify their efficiency and classify them independently of any computing system or language.
Module provider
Computer Science and Electronic Eng
Module Leader
CHOCKLER Gregory (CS & EE)
Number of Credits: 15
ECTS Credits: 7.5
Framework: FHEQ Level 4
Module cap (Maximum number of students): N/A
Overall student workload
Independent Learning Hours: 74
Lecture Hours: 22
Tutorial Hours: 4
Laboratory Hours: 18
Guided Learning: 10
Captured Content: 22
Module Availability
Semester 2
Prerequisites / Co-requisites
None.
Module content
This module considers various data structures such as lists, stacks, queues, trees and graphs and the abstract data types on which they are based. The module also discusses algorithms. It defines a scheme for quantifying algorithm efficiency, devoid of any computing system or language. Several approaches for algorithm design are studied such as recursion, divide and conquer, brute force and greedy strategies. Towards the end of the module the classification of algorithms and the problems they solve is explored. The module finally concludes by asking how future technological developments could change the way we perceive algorithms.
Main topics
Abstract data types: discussed in general.
Basic data Structures: lists, linked-lists, stacks, queues, implementation/applications of these.
Trees: general trees ordered trees, multiway trees, implementations of trees, tree traversal, path lengths.
Binary trees: internal and external nodes, binary tree depth, logs.
Binary tree applications: expression trees, binary search trees, heaps, Huffman data compression.
Graphs: undirected/directed, connected, weakly/strongly connected, complete), adjacency matrix/list, topological ordering, weighted graphs/networks, path lengths, Dijkstra’s Algorithm, depth/breadth-first, traversals, minimum spanning trees, Prim’s Algorithm, Kruskal’s Algorithm.
Algorithm Efficiency: Big ‘Oh’, common time complexities, log time, binary search v linear search Recursion: why use it, the ground rules, Merge Sort in detail, Towers of Hanoi in detail.
Sorting: Bubble-, Selection-, Insertion-, Shell-, Bucket-, Radix-, Heap-, Quick-, external sorting.
Hashing: searching, hash function & table, collisions, separate chaining and open addressing.
Algorithm design strategies: brute force, greedy, divide and conquer, dynamic programming, incremental, probabilistic.
Algorithm and problem classification: polynomial and exponential time, reasonable and unreasonable algorithms, tractable and intractable problems, the future.
- You should be clear that the Algorithms material in the module is NOT intended to be a review of a comprehensive range of specific algorithms. Nevertheless, a limited number of specific algorithms within the areas of searching and sorting will be examined
Assessment pattern
Assessment type | Unit of assessment | Weighting |
---|---|---|
School-timetabled exam/test | Invigilated Test (2hrs) | 20 |
Examination | Invigilated Exam (2hrs) | 80 |
Alternative Assessment
N/A
Assessment Strategy
Thus, the summative assessment for this module consists of:
Computer-based test in week 6
A 2-hour examination testing all learning outcomes
Formative assessment and feedback
The use of electronic voting handsets offers formative feedback opportunities throughout the module. Verbal feedback is also given in lab sessions as the students attempt the lab exercises. Feedback will also be provided on the in-semester test.
Module aims
- Discover and examine various abstract data types (ADT).
- Explore data structures based on those ADTs, including implementation and applications of such data structures.
- Explore algorithms as abstractions - independent of any computing facility.
- Examine what is involved in creating algorithms and quantifying their efficiency.
- Examine the importance of algorithm efficiency.
- Examine the action of a small number of specific algorithms particularly in the areas sorting and searching.
- Explore various strategies for algorithm design and argue about their correctness.
- Classify algorithms.
Learning outcomes
Attributes Developed | ||
001 | Choose the appropriate data structure for a particular application. | CP |
002 | Be familiar with the big Oh measure of algorithm efficiency. | K |
003 | Know what is meant by recursive and non-recursive algorithms. | K |
004 | Describe a number of searching strategies and trace any of the taught hashing schemes. | KC |
005 | Use any of the taught sorting methods. | KCP |
006 | Understand recursion and polymorphism and be able to use them in simple algorithm design. | CP |
007 | Distinguish between different algorithm design strategies. | CP |
008 | Discuss the classification of algorithms and problems. | KC |
Attributes Developed
C - Cognitive/analytical
K - Subject knowledge
T - Transferable skills
P - Professional/Practical skills
Methods of Teaching / Learning
The learning and teaching strategy is designed to provide students with the knowledge, skills and practical experience covering the module aims and learning outcomes.
The learning and teaching methods include:
Weekly lectures
Weekly lab session, including one lab session for the in-semester test
The lab sessions will put into practice the theoretical concepts covered in the lectures.
A test will be used during the course to ensure the student has assimilated the material during the course.
- Students will be expected to spend a minimum of 2 hours a week on self-study
Indicated Lecture Hours (which may also include seminars, tutorials, workshops and other contact time) are approximate and may include in-class tests where one or more of these are an assessment on the module. In-class tests are scheduled/organised separately to taught content and will be published on to student personal timetables, where they apply to taken modules, as soon as they are finalised by central administration. This will usually be after the initial publication of the teaching timetable for the relevant semester.
Reading list
https://readinglists.surrey.ac.uk
Upon accessing the reading list, please search for the module using the module code: COM1029
Other information
Digital Capabilities
This foundational computer science module teaches students to work with a range of complex data structures such as trees and graphs and classic algorithms such as sorting. These data structures and algorithms form the basic building blocks of computer programmes, providing students with the skills to choose the right data structure for a problem and apply it to the problem.
Employability
This module provides foundational maths, and computer science skills that are the first steps to applying algorithmic techniques to solving real life problems. Students are taught about how different data structures function and algorithms that work well with these data structures. This is foundational to programming and development and is highly valued by employers.
Global and Cultural Skills
Computer Science is a global language and the tools and languages used on this module can be used internationally. This module allows students to learn about and with data structures and algorithms that are truly global concepts. It will allow them to reason about and develop applications with global reach and collaborate with their peers around the world.
Resourcefulness and Resilience
This module provides knowledge of complex data structures and classical algorithms. By applying these techniques, students gain new insight into how to reason about and develop an efficient solution for new unseen problems.
Programmes this module appears in
Programme | Semester | Classification | Qualifying conditions |
---|---|---|---|
Computing and Information Technology BSc (Hons) | 2 | Compulsory | A weighted aggregate mark of 40% is required to pass the module |
Computer Science BSc (Hons) | 2 | Compulsory | A weighted aggregate mark of 40% is required to pass the module |
Computer Science MEng | 2 | Compulsory | A weighted aggregate mark of 40% is required to pass the module |
Please note that the information detailed within this record is accurate at the time of publishing and may be subject to change. This record contains information for the most up to date version of the programme / module for the 2023/4 academic year.