Back to Module List

CMPC2M11 - DATA STRUCTURES AND ALGORITHMS

Module Code:
CMPC2M11
Department:
Computing Sciences
Credit Value:
20
Level:
2
Organiser:
Dr. Tony Bagnall
This is a compulsory module for all computing students and provides the necessary foundation in data and storage structures for all computing streams. In addition, the module emphasises systematic algorithm design and discusses algorithm analysis. At the same time, the module provides the student with the opportunity to reinforce and enhance the programming skills developed in the first year.

Lectures will be given using a combination of data monitor and overhead projection. Lecture notes, exercise sheets and other relevant material will be available via Blackboard.


Module texts (and further reading)

The main text for the module is:

  • Goodrich,M. T. and Tamassia, R.  Data Structures & Algorithms in Java Wiley

Either of the following texts is also suitable accompaniment to the unit:

  • Weiss,M. A.,  Data Structures and Algorithms Analysis in Java, Pearson
  • Sahni,S.,  Data Structures, Algorithms and Applications in Java , McGraw-Hill

Submission:

Written coursework should be submitted by following the standard CMP practice. Students are advised to refer to the Guidelines and Hints on Written Work in CMP.

Deadlines:

If coursework is handed in after the deadline day or an agreed extension:
 

 

Work submitted Marks deducted
After 15:00 on the due date and before 15:00 on the day following the due date 10 marks
After 15:00 on the second day after the due date and before 15:00 on the third day after the due date 20 marks
After 15:00 on the third day after the due date and before 15:00 on the 20th day after the due date.  All the marks the work merits if submitted on time (ie no marks awarded) 
After 20 working days Work will not be marked and a mark of zero will be entered


Saturdays and Sundays will NOT be taken into account for the purposes of calculation of marks deducted.

All extension requests will be managed through the LTS Hub. A request for an extension to a deadline for the submission of work for assessment should be submitted by the student to the appropriate Learning and Teaching Service Hub, prior to the deadline, on a University Extension Request Form accompanied by appropriate evidence. Extension requests will be considered by the appropriate Learning and Teaching Service Manager in those instances where (a) acceptable extenuating circumstances exist and (b) the request is submitted before the deadline. All other cases will be considered by a Coursework Coordinator in CMP.

For more details, including how to apply for an extension due to extenuating circumstances download Submission for Work Assessment (PDF, 39KB)
 

Plagiarism:

Plagiarism is the copying or close paraphrasing of published or unpublished work, including    the work of another student; without due acknowledgement. Plagiarism is regarded a serious offence by the University, and all cases will be investigated. Possible consequences of plagiarism include deduction of marks and disciplinary action, as detailed by UEA's Policy on Plagiarism and Collusion.


Module specific: 
 

  • To discuss the process of algorithm design.
  • To introduce techniquess for analysing the performance of algorithms in terms of time and space complexity.
  • To discuss the distinction between an abstract data type and a concrete data structure.
  • To review data structures introduced in Year 1 and use them to implement a number of algorithms.
  • To introduce a variety of tree-based data structures and algorithms for their efficient manipulation.
  • To introduce the concept of an order relation and to investigate the complexity of a number of common sorting algorithms.
  • To discuss hashing techniques.

Transferable skills:

  • To gain further experience in a broad range of IT skills.
  • To appreciate the need for the mathematical analysis of algorithms and gain some limited experience in this respect.
  • To learn that the efficiency of a programme depends on the choice of data structures used to implement the underlying algorithm.

On completion of this module students should be able to:

  • Design algorithms for a wide range of problems.
  • Use data structures to implement these algorithms in Java.
  • Compare the space and time efficiency of different algorithms for solving a given problem.
  • Understand the implementations of standard abstract data types.
  • Understand the principles underlying all of the standard sorting algorithms and be aware of their complexity.
  • Distinguish between data structures for internal and external storage.

This module is delivered as a programme of 30 lectures, supported by workshops. Exercise sheets are set every fortnight throughout the course. Each workshop group has 10 workshops during the semester. Students are expected to attend all workshops.

Total hours: 40

Lectures: 30 lectures (with provisional weekly schedule)

  1. Basic Data Structures: linked lists. Stacks and queues
  2. Algorithm Analysis: time and space complexity functions; big O
     notation
  3. Searching and Sorting: binary search, simple sorting algorithms;
     mergesort; quicksort
  4. Binary trees
  5. Binary Search Trees
  6. Reading week
  7. Heaps
  8. Hashing and Tries
  9. Huffman Coding and B-Trees
  10. Graph Algorithms

Laboratory work: 0 hours

Workshops: 10 hours

Exercise sheets as previous weeks' lecture


Examination with Coursework or Project