Module COMP1081: Data Structures

Department: Computer Science

COMP1081: Data Structures

Type	Open	Level	1	Credits	20	Availability	Available in 2010/11	Module Cap	None.	Location	Durham

Prerequisites

• None

Corequisites

• Introduction to Programming (COMP1011)

Excluded Combination of Modules

• None

Aims

• To introduce the theory and practice of problem solving in computing through the development of algorithms for common computer science problems, and to use this in the wider context of problem solving and software development.

Content

• Motivation for implementing data structures.
• Data structures: Basic, Linear and non-linear.
• Tree structures and algorithms analysis.
• Operations on data structures.
• Solving problems through the construction of algorithms.
• Techniques for reasoning about and evaluating algorithms.
• Algorithmic mechanisms such as sequence, iteration, choice and recursion.
• Abstraction by specification and parameterisation.
• Strategies for problem solving such as divide and conquer.

Learning Outcomes

• Be familiar with the most common (non-trivial) data structures, their relative advantages/disadvantages, and how to implement and / or use them.
• Be able to explain the form of program specifications using pre and post conditions.
• Be able to describe mechanisms of program execution such as procedure call with pass-by-value parameters.
• Use of this knowledge in the wider context of problem solving and software development.

• Competence in dealing, both theoretically as well as practically, with some non-trivial data structures (e.g. search trees, hash tables), and knowledge about when to use which (type of) data structure.
• Producing algorithmic solutions to problems, using the algorithmic mechanisms of sequence, choice, iteration and recursion.
• Basic understanding of complexity issues (e.g. running time of important operations like insert, delete or lookup).
• Knowledge in issues regarding efficient implementation (also applicable outside of this course).
• Ability to select which data structures to use as they differ widely regarding many aspects (e.g. running time of various basic operations, or memory overhead).

• Combine theoretical analysis with application of the gained knowledge.
• Use problem solving strategies such as divide and conquer, drawing a diagram, trial and error.
• Develop problem solving skills through the identification of strategies used to solve problems.

Modes of Teaching, Learning and Assessment and how these contribute to the learning outcomes of the module

• Lectures provide the students with a focus for what is to be learned which is then supported by practical classes where the application of the theory is enabled. Summative assignments encourage and guide further independent study to be conducted. Summative examinations test the knowledge acquired and the students' ability to use this knowledge to solve complex problems.

Teaching Methods and Learning Hours

Activity	Number	Frequency	Duration	Total/Hours
Lectures	30	1 per week in term 1, 2 per week in term 2 and 3	1 hour	30
Practicals	20	Weekly	2 hours	40
Preparation and reading				130
Total				200

Summative Assessment

Practical work to consist of weekly exercises and written benchtests.

Component: Examination		Component Weighting: 60%
Element	Length / duration	Element Weighting	Resit Opportunity
Examination	2hrs	100%	Yes
Component: Coursework		Component Weighting: 40%
Element	Length / duration	Element Weighting	Resit Opportunity
Practical Work		100%	Yes

Formative Assessment:

Example exercises given through the course. In addition a collection paper for the module is sat during a student's first practical class of the 2nd term. Additional revision lectures may be arranged in the modules lecture slots in the 3rd term.

---

■ Attendance at all activities marked with this symbol will be monitored. Students who fail to attend these activities, or to complete the summative or formative assessment specified above, will be subject to the procedures defined in the University's General Regulation V, and may be required to leave the University