F28PB - Software Development B

Course leader(s):

Aims

This course is linked to F28PA Software Development A. The aim of this course is to introduce more programming techniques in a high-level language such as text processing, advanced error handling, and recursion. The course also covers abstract data types and fundamental data structures commonly used in programs such as stacks, queues, linked lists, search trees and heaps. The course also introduces unit testing in practice to familiarise students with software testing and debugging at the code level.

Syllabus

1. Introduction to Data Structures and ADTs (1.1 Abstract Data Types, Complexity)

2. Dynamic Structures 1: Stacks (2.1 Stacks and its Operations, Stack ADT)

3. Dynamic Structures 2: Queues (3.1 Queues and its Operations, Queue ADT)

4. Recursion (4.1 Concept of Recursion, Recursive Structure in ADTs)

5. Linked Data Structures (5.1 Linked Lists and its Operations, Doubly Linked Lists)

6. Algorithm I: Sorting Algorithms (6.1 Insertion, Bubble, Merge, and Quicksort)

7. Algorithm II: Searching Algorithms (7.1 Linear Search, Binary Search)

8. Tree Data Structures (8.1 Binary Search Trees, Tree Traversals)

9. Advanced Structures (9.1 Priority Queues, Tries)

10. Unit Testing (10.1 Unit Testing, Software Refactoring)

Learning outcomes

By the end of the course, students should be able to do the following:

demonstrate knowledge of the properties of algorithms for fundamental data structures, recursive programming techniques, and their applications in solving practical problems.

apply static structures, dynamic structures (stacks, queues, priority queues, min and max heaps), and linked data structures (single and double) without utilising built-in packages.

apply a test-driven development approach to validate data structure, searching, and sorting algorithm implementations.

apply simple sorting algorithms (insertion, bubble, and selection) and efficient divide-and-conquer sorting algorithms (merge-sort and quick-sort).

implement linear and recursive search algorithms to solve diverse programming challenges.

demonstrate knowledge of algorithm analysis to find the worst-case running time for sorting, searching, and the various data structure operations.

analyse the applicability of data structures and code design choices to relevant problems and their implications in terms of efficiency of solution.

discuss the importance of the design, maintenance of code, a unit testing framework, and usage of version control in software development.