Algorithms & Data Structures 2 COMPSCI2007

  • Academic Session: 2018-19
  • School: School of Computing Science
  • Credits: 10
  • Level: Level 2 (SCQF level 8)
  • Typically Offered: Semester 2
  • Available to Visiting Students: Yes
  • Available to Erasmus Students: Yes

Short Description

To familiarise students with fundamental data types and data structures used in programming, with the design and analysis of algorithms for the manipulation of such structures, and to provide practice in the implementation and use of these structures and algorithms in a Java context.

Timetable

Two 1-hour lectures per week, one 1-hour laboratory every week.

Requirements of Entry

Entry to Level 2 Computing Science is guaranteed to students who achieve a GPA of B3 or better in their level 1 courses at the first sitting. All others would be at the discretion of the School.

 

All grades for Computing Science courses must be at D3 or better at either attempt.

Excluded Courses

None

Co-requisites

Java Programming 2

Object Oriented Software Engineering 2

Assessment

1.5 hour examination (80%), coursework (20%).

Main Assessment In: April/May

Are reassessment opportunities available for all summative assessments? No

Reassessments are normally available for all courses, except those which contribute to the Honours classification. For non Honours courses, students are offered reassessment in all or any of the components of assessment if the satisfactory (threshold) grade for the overall course is not achieved at the first attempt. This is normally grade D3 for undergraduate students and grade C3 for postgraduate students. Exceptionally it may not be possible to offer reassessment of some coursework items, in which case the mark achieved at the first attempt will be counted towards the final course grade. Any such exceptions for this course are described below. 

 

The coursework cannot be redone because the feedback provided to the students after the original coursework would give any student redoing the coursework an unfair advantage.

Course Aims

To familiarise students with fundamental data types and data structures used in programming, with the design and analysis of algorithms for the manipulation of such structures, and to provide practice in the implementation and use of these structures and algorithms in a Java context.

Intended Learning Outcomes of Course

By the end of the course students will be able to:

1. Use an abstract data type (ADT) and its role in program design;

2. Use stacks, queues, lists, sets and maps, and recognise typical contexts where their use is appropriate;

3. Represent ADTs as Java interfaces;

4. Explain the use of basic data structures; such as arrays; linked lists; binary trees; and hash tables;

5. Implement basic data structures in Java;

6. Represent standard ADTs by means of appropriate data structures;

7. Use recursion as an algorithm design technique in appropriate contexts;

8. Carry out the analysis of a range of algorithms in terms of algorithm analysis and express algorithm complexity using the O notation;

9. Implement standard searching and sorting algorithms; including binary search; mergesort and quicksort; and their complexities;

10. Use a collection in Java; and related concepts such as comparators and iterators;

11. Make use of particular Java collections List; Set; Queue and Map; and their various realisations.

Minimum Requirement for Award of Credits

Attendance at the degree exam, submission of at least one of the two assignments, and attendance at three or more lab sessions.