CSU22011 – Algorithms and Data Structures I

Module CodeCSU22011
Module NameAlgorithms and Data Structures I
ECTS Weighting[1]5 ECTS
Semester taughtSemester 1
Module Coordinator/s  Vasileios Koutavas

Module Learning Outcomes

On successful completion of this module, students will be able to:

  • LO1: Have gained significant knowledge on algorithms and data structures, and the mathematical theory and techniques to evaluate their efficiency and effectiveness.
  • LO2: Have the ability to evaluate algorithms in terms of their running time and memory space requirements and classify those algorithms in the major complexity classes using appropriate performance models.
  • LO3: Be able to efficiently implement the operations of the main data structures used in most programming.
  • LO4: Have gained experience through experiments in implementing effective new and existing algorithms.
  • LO5: Be able to identify the most suitable data structures and algorithms for each programming problem based on the parameters of the problem, the advantages and limitations of each data structure and algorithm, the resources available, the desired performance criteria etc.
  • LO6: Be able to design and implement robust, effective and well-structured Java programs using industry standards such as Abstract Data Types and the approaches of unit testing and test coverage.

Module Content

Theory:

  • Asymptotic growth functions and analysis of source code to derive running time and space requirements
  • Amortised running time analysis of algorithms
  • Recursion vs iteration

Algorithms and Data structures:

  • Array and linked list implementations of stacks and queues.
  • Doubly linked lists
  • Union-find
  • Binary trees, binary search trees, balanced search trees, B-trees
  • Hash tables
  • Special topics

Programming:

  • Java generics
  • Iterators
  • JUnit testing

Teaching and learning Methods

3 hours of lectures, 1 hour of laboratories per week. Individual coursework assignments. In-class quizzes and tests.

Assessment Details

Content

Assessment ComponentBrief DescriptionLearning Outcomes Addressed% of totalWeek setWeek Due
Take-home exam, time-limited2 hour take-home examination (available for a 5hr period)LO1 – LO665%n/an/a
mid-term test1 hour test (available for a 3hr period)LO1 – LO623%W8W8
Assignment 1IntroductoryL04 – L062%W2W3
Assignment 2Linked ListsL01 – L065%W3W6
Assignment 3Binary TreesL01 – L065%W8W11
Bonus Assignment*Various topicsL01 – L06W2W12

(*) The bonus assignment can compensate up to 10% of lost coursework marks.

Reassessment Details

Examination 100%; 2 hour take-home examination (available for a 5hr period)

Contact Hours and Indicative Student Workload

Contact Hours (scheduled hours per student over full module), broken down by:44 hours
Lecture
33 hours
Laboratory11 hours
Tutorial or seminar0 hours
Other0 hours
Independent study (outside scheduled contact hours), broken down by:70 hours
Preparation for classes and review of material (including preparation for examination, if applicable40 hours
completion of assessments (including examination, if applicable)30 hours
Total Hours114 hours

Recommended Reading List

Algorithms (4th Edition)
Robert Sedgewick and Kevin Wayne
http://algs4.cs.princeton.edu/home/
Pearson Education 2011

Module Pre-requisites

Prerequisite modules: NA

Other/alternative non-module prerequisites:

The module assumes students have previous knowledge of standard programming in Java. This includes Java syntax including data types, commands, loops, conditionals and other common programming structures, and the Java Object-Oriented model including classes, fields, methods, inheritance and interfaces. Students with working knowledge of another programming language such as C/C++ should be able to acquire the required knowledge in Java from online tutorials.

Module Co-requisites

None

Module Website

Blackboard

Recordings of lectures during week 1:

  • Lecture 1 (Mon): link
  • Lecture 2 (Tue): link
  • Lecture 3 (Wed): link

Live lecture links during week 2: