C++ Part 2: Data Structures and Algorithms



Overview

Algorithms are a set of instructions that operate in sequence to fulfil an action. Everyday actions we take in the digital world, whether that be a Google search, looking up the fastest route to our destination via a SatNav, or scrolling through the recommended content that appears on our social media feeds, are all fulfilled by carefully developed and continuously evolving algorithms.

This course introduces students to a range of algorithms that can be used to fulfil operations (such as insertion of data, deletion of data, searching through data, sorting data etc) on different stores of data (data structures such as arrays, vectors, hash tables, stacks, queues, linked lists, trees and graphs). Students will discover that the performance of algorithms will vary according to which data structure is implemented, the size of the data set, the number of statements in the algorithm, whether the data is sorted and also the system architecture (processing power). This course will teach students how to analyse, compare, evaluate different approaches to the same problem via asymptotic notation (mainly 'Big O').

It is strongly recommended that students have an introductory level understanding of C++ (or a related Object-Oriented language: C#, Java or Python) before taking this course. Ideally, students should first complete 'An Introduction to Object-Orientated Programming Using C++' (or Java) course which provides a strong foundation of C++ syntax and the OOP paradigm before undertaking this course on data structures and algorithms.

Whilst these concepts taught in this course are not exclusive to the C++ programming language, we will utilise C++ to make use of pointers for memory efficiency. Despite the wealth of existing libraries available, there is educational value in learning the construction of such data structures and algorithms and how to analyse their performance. These topics are commonly examined in interviews by Big Tech companies ('FANG': Facebook (now Meta), Amazon, Netflix, Google, in addition to Apple and Microsoft), and hence this course can help students prepare to apply for software development and software engineering roles.

Programme details

Courses starts: 16 Apr 2024

Week 0: Course orientation

Week 1: Introduction to the course and C++ Fundamentals

Week 2: Asymptotic complexity (Big O notation), Search and Sort Algorithms

Week 3: Arrays, Vectors and Hash Tables

Week 4: Linked Lists

Week 5: Stacks and Queues

Week 6: Trees

Week 7: Graphs 

Week 8: Graph Path Finding

Week 9: Dynamic Programming

Week 10: Revision and Assignment Workshop

Digital Certification

To complete the course and receive a certificate, you will be required to attend and participate in at least 80% of the live sessions on the course and pass your final assignment. Upon successful completion, you will receive a link to download a University of Oxford digital certificate. Information on how to access this digital certificate will be emailed to you after the end of the course. The certificate will show your name, the course title and the dates of the course you attended. You will be able to download your certificate or share it on social media if you choose to do so.

Fees

Description Costs
Course Fee £280.00
Take this course for CATS points £10.00

Funding

If you are in receipt of a UK state benefit, you are a full-time student in the UK or a student on a low income, you may be eligible for a reduction of 50% of tuition fees. Please see the below link for full details:

Concessionary fees for short courses

Tutor

Dr Nick Day

Dr Nicholas Day teaches computer programming in C#, C++, Java and Python at both Buckinghamshire New University and Oxford University. Nicholas started his career as an Associate Lecturer at Buckinghamshire New University in late 2014, progressing to become a Graduate Teaching Associate in February 2020 and is now a Lecturer at the same institution, since August 2021. He completed the PGCert in Teaching and Learning in 2015 and also acquired fellowship of AdvanceHE (previously Higher Education Academy). Between 2016 and 2019, Nicholas assisted Dr Vasos Pavlika with the delivery of introductory programming courses in C++ and Java for the Department for Continuing Education at Oxford University. He was empanelled as a Department Tutor in 2019 and started delivered an Introduction to Object-Oriented Programming Using Java, later adapting the course for online delivery in 2022. He has also started researching and teaching Artificial Intelligence and Data Science material.

Nick’s scholarly interests are Computer Science Education (CSEd), Computing Education Research (CER), and online pedagogy. He completed his PhD in March 2020, which investigated the learning and teaching of computer science education, specialising in delivery of computer programming modules. Post-PhD completion, Nicholas is involved with Knowledge Transfer Partnership (KTP) applications and in discussion with data-driven companies regarding research projects and consultancy work. Nicholas also now supervises current PhD students in fields associated with Data Science and Virtual Reality, in addition to mentoring departmental colleagues who are undertaking PhD research. During the COVID-19 pandemic, Nicholas began teaching online and recording videos to increase access and engagement with educational material. He passionate about pedagogy and utilises his research findings to inform curriculum design.

Course aims

C++ will be used to introduce data structures and algorithms. The course will cover data structures such as vectors, arrays, hash tables, linked lists, trees and graphs, and in will, in addition, evaluate and implement different algorithms which will sort, search through, insert and delete data in different structures.

Course Objectives:

  • To implement data structures such as hash tables, arrays, vectors, linked lists, hash tables, trees, and graphs.
  • To evaluate different algorithms for search, sort, insert and delete operations.
  • To analyse the performance of algorithms on data structures with asymptotic complexity.

Teaching methods

Pre-recorded lectures will be released weekly. Students are then expected to attempt the accompanying tutorial exercises and bring their solutions to the weekly live online sessions for review and discussion. Students are also encouraged to attempt the formative (unassessed) quizzes to review their understanding of the concepts and principles taught in the weekly lectures.

Learning outcomes

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

  • understand how to implement hash tables, arrays, vectors, linked lists, trees and graphs;
  • understand how code search, sort, insert and delete algorithms;
  • understand how to calculate and evaluate the performance of algorithms.

After attending this course, students will know:

  • how to implement a variety of data structures in C++;
  • how to insert, delete, search and sort through data stored in such applications;
  • how to analyse and compare the algorithms to make optimal and efficient choices for their applications.

Assessment methods

One piece of coursework will be set, which on successful completion, will count towards the award of 10 CATS points. The assessment will require students to design and implement an application (problem scenario of their choice) that utilises the optimal data structures and algorithms to fulfil the requirements of their chosen scenario.

Students must submit a completed Declaration of Authorship form at the end of term when submitting your final piece of work. CATS points cannot be awarded without the aforementioned form - Declaration of Authorship form

Application

We will close for enrolments 7 days prior to the start date to allow us to complete the course set up. We will email you at that time (7 days before the course begins) with further information and joining instructions. As always, students will want to check spam and junk folders during this period to ensure that these emails are received.

To earn credit (CATS points) for your course you will need to register and pay an additional £10 fee per course. You can do this by ticking the relevant box at the bottom of the enrolment form or when enrolling online.

Please use the 'Book' or 'Apply' button on this page. Alternatively, please complete an enrolment form (Word) or enrolment form (Pdf).

Level and demands

Before attending this course, prospective students will have:

  • ideally completed the 'C++ Part 1: Introduction to Object-Oriented Programming' (or Java counterpart) here at OUDCE, or will have completed an equivalent introductory Object-Oriented programming course, or have experience writing Object-Oriented applications in C++;
  • a good understanding of mathematics, logic, and abstract reasoning skills will be beneficial for solving unfamiliar computational problems and the analysis of the performance of algorithms;
  • previous experience of implementing data structures and search and sort algorithms will be advantageous, but not a requirement.

Students who register for CATS points will receive a Record of CATS points on successful completion of their course assessment.

To earn credit (CATS points) you will need to register and pay an additional £10 fee per course. You can do this by ticking the relevant box at the bottom of the enrolment form or when enrolling online.

Coursework is an integral part of all weekly classes and everyone enrolled will be expected to do coursework in order to benefit fully from the course. Only those who have registered for credit will be awarded CATS points for completing work at the required standard.

Students who do not register for CATS points during the enrolment process can either register for CATS points prior to the start of their course or retrospectively from the January 1st after the current full academic year has been completed. If you are enrolled on the Certificate of Higher Education you need to indicate this on the enrolment form but there is no additional registration fee.

Most of the Department's weekly classes have 10 or 20 CATS points assigned to them. 10 CATS points at FHEQ Level 4 usually consist of ten 2-hour sessions. 20 CATS points at FHEQ Level 4 usually consist of twenty 2-hour sessions. It is expected that, for every 2 hours of tuition you are given, you will engage in eight hours of private study.

Credit Accumulation and Transfer Scheme (CATS)

Terms & conditions for applicants and students

Information on financial support