Data Structures & Algorithms (DSA) COM431
Throughout Data Structures and Algorithms (DSA) module, you develop a fundamental understanding of how data is organised, stored and processed within software applications. The module begins with basic data structures such as arrays and lists, allowing you to explore how data can be stored efficiently and the trade-offs involved in different storage approaches. You are encouraged to think critically about selecting the most appropriate structure for a given problem rather than assuming a single solution will suit every situation.
As the module progresses, you are introduced to more advanced data structures including linked lists, stacks, queues and hash tables. You learn how these structures overcome some of the limitations of arrays and how they support different types of operations more efficiently. Through practical implementation exercises, you gain experience of building these structures from scratch and understanding the advantages and disadvantages of each approach.
To support the implementation of these data structures, the module introduces object-oriented programming. You learn how classes, objects, attributes and methods can be used to model real-world entities and software components. This enables you to create reusable and organised code while developing your own implementations of core data structures.
The second half of the module focuses increasingly on algorithms and efficiency. You explore how algorithm performance can be measured using Big O notation and learn why some solutions scale more effectively than others as data volumes increase. Building on these concepts, you study searching and sorting algorithms including binary search, quicksort and merge sort, examining how improved algorithm design can significantly reduce processing time when working with large datasets.
The module then introduces hierarchical and network-based data structures through trees and graphs. You learn how recursion can be used to process tree structures efficiently and how trees can support searching and sorting operations. Graphs extend these ideas by representing complex networks of interconnected nodes, forming the basis for route-finding and navigation systems.
Finally, you investigate path-finding algorithms including Dijkstra’s Algorithm and A*. These techniques demonstrate how data structures and algorithms can be combined to solve real-world problems such as navigation, route optimisation and artificial intelligence. You explore how algorithm design influences efficiency and accuracy, and how heuristics can be used to improve performance when searching for optimal solutions.
Overall, the module equips you with the knowledge and practical skills needed to analyse problems, select suitable data structures, evaluate algorithm efficiency and implement effective software solutions. By the end of the module, you should be able to justify your technical decisions, understand the performance implications of different approaches and apply core data structures and algorithms to a range of computing problems.
DSA Module Summary
The DSA (Data Structures and Algorithms) module introduces the core data structures and algorithms used in software development, focusing on efficiency, problem-solving, and implementation in Python.
1. Introduction to Data Structures
Introduces the concept of data structures and why choosing the right structure matters. Covers:
- Arrays and indexing
- Memory layout and sequential storage
- Advantages of arrays (fast lookup)
- Limitations of arrays (fixed size)
- Python lists as a flexible alternative to arrays
2. Linked Lists
Examines linked lists as an alternative to arrays.
• Nodes connected by references rather than stored consecutively • Efficient insertion at the end • Slower indexed access than arrays • Trade-offs between flexibility and lookup performance
3. Introduction to Object-Oriented Programming
Provides the OOP foundations needed to build custom data structures.
• Classes and objects • Attributes and methods • Creating reusable blueprints for structures such as stacks and linked lists • Basic Python class design concepts
4. Linked List and Stack Implementation
Focuses on implementing data structures from scratch using OOP.
• Building linked-list nodes and list classes • Stack data structure • Push and pop operations • Last-In, First-Out (LIFO) behaviour • Practical coding exercises implementing these structures
5. Queues
Introduces queue-based processing.
• First-In, First-Out (FIFO) principle • Enqueue and dequeue operations • Applications such as task scheduling and breadth-first search • Comparison with stacks
6. Hash Tables
Explores fast key-based lookup systems.
• Keys and values • Hash functions • Hash codes and bucket arrays • Collision handling through: Separate chaining & Linear probing • Trade-offs between memory usage and lookup efficiency
7. Introduction to Algorithms
Introduces algorithm analysis.
• What algorithms are • Measuring efficiency using Big O notation • Comparing algorithm performance • Concepts such as linear and quadratic complexity • Foundations for later searching and sorting algorithms
8. Binary Search
Presents an efficient searching technique.
• Requires sorted data • Divide-and-conquer approach • Repeatedly halves the search space • Complexity of O(log n) • Significant improvement over linear search O(n)
9. Trees
Introduces hierarchical data structures.
• Tree terminology (root, parent, child, descendant) • Binary search trees • Tree traversal • Recursive algorithms • Use cases including file systems, HTML documents, and efficient searching
10. Further Sorting Algorithms
Covers more advanced sorting methods.
• Quicksort • Merge Sort • Recursion-based sorting • Partitioning strategies • Performance improvements over simpler O(n²) sorts • Typical complexity around O(n log n)
11. Graphs and Path Finding
Introduces graph structures and routing.
• Nodes and edges • Weighted graphs • Route optimisation • Dijkstra’s algorithm • Priority queues and heaps • Finding shortest paths in networks
12. Further Path Finding: A*
Builds upon Dijkstra.
• A* (A-Star) search algorithm • Heuristic-guided search • G, H and F scores • More efficient route finding toward specific destinations
Overall Learning Outcomes
By the end of the module, students should be able to:
• Understand the strengths and weaknesses of major data structures. • Implement custom data structures in Python. • Analyse algorithm efficiency using Big O notation. • Apply searching, sorting, and path-finding techniques. • Select appropriate data structures and algorithms for real-world problems.