Embedded Files
Overview
Overview
This project page highlights work from my 'Algorithmic Problem Solving' module at Teesside University (Year 1, 2025), a stand-out course focusing primarily on algorithmic thinking, formal proofs, and core data structures. The main assessment involved applying these concepts to mathematical problem-solving and practical implementations, supported by Java exercises reinforcing data structure concepts.
Key Concepts
Key Concepts
Formal Methods & Problem Solving
Formal Methods & Problem Solving
This section of the ICA focused on applying mathematical and logical rigor to analyse algorithms and verify code correctness:
Combinatorics: Analysed problems like the 'Torch Problem', applying combinatorial principles and logical deduction to calculate possible transitions (deriving the formula n(n + 1)/2 for n people) and determine optimal strategies under specific constraints (e.g. limited torch battery life). This required breaking down the problem and applying appropriate mathematical principles.
State Transition Diagrams: Employed counting rules to calculate the number of paths between nodes.
Invariants: Developed and utilised a linear invariant (-6r + 4t = -24) to solve a state-change problem (for a recruitment scenario). This involved identifying an expression whose value remained constant under the given rules and using it with the final conditions to deduce the final state.
Program Verification (Hoare's Triples & Induction): Formally verified an iterative code loop via mathematical induction. This involved establishing a base case, forming an induction hypothesis, and using Hoare Logic rules (specifically applying the Assignment Rule) to demonstrate the inductive step, rigorously proving the code met its postcondition.
Data Structures
Data Structures
Linked Lists: Explored the differences between singly, doubly, and circular linked lists, focusing on the traversal directions and end conditions. We also looked at the algorithms for node deletion and insertion in different types of lists. We also implemented our own versions of these lists, with many core operations in Java to prove this. This knowledge greatly aided me in my Game Software Engineering module, where I implemented my own linked list in C++, for the classic game of snake.
Stacks & Queues: Analysed Last-In, First-Out (LIFO) behaviour for Stacks, and First-In, First-Out (FIFO) behaviour for Queues by tracing complete sequences of operations (push/pop and enqueue, dequeue).
Time Complexity: Took a brief look at time complexity using Big O Notation, developing our understanding of algorithmic efficiency.
Supporting Java Implementation
Supporting Java Implementation
These ungraded Java exercises were completed alongside the module's theoretical content to reinforce the practical application of core data structure concepts:
Linked Lists: Implemented a standard Singly Linked List with all core operations (adding, deletion, insertion, insertion, and searching). This provided a crucial look into memory management and the importance of handling edge cases.
Doubly: Adapted the singly linked list by adding a backwards facing reference (previous pointer). This design provides a much more efficient method for bidirectional traversal and node deletion, at the cost of slightly larger memory requirements per node.
Circular: Through once again adapting the singly linked list to where the last node points to the head, I implemented a Circular Linked List. This structure simplifies adding nodes to the tail, as well as allowing for continuous, non-terminating traversal.
Stacks & Queues: Implemented both array-based and list-based implementations for both stacks and queues. This helped me visualise and better understand the differences of structure (FIFO/LIFO). Comparing the array-based versus the list-based versions highlighted the trade-offs in dynamic sizing and memory management.
Arrays: This served as my first delve into Java. It was a foundational task, implementing a simple Array Abstract Data Type (ADT) with basic functionalities (addition, deletion, and querying) to understand the concept of wrapping a data structure with a clear interface.
Technical Breakdown
Technical Breakdown
Languages: Java, Mathematical Notation
Core Concepts: Algorithmic Analysis, Formal Verification (Induction and Hoare's Triples), Invariants, Data Structures (Linked Lists, Stacks, Queues and, Arrays), Time Complexity (Big O)
IDE: NetBeans
Tools: GitHub
Challenges & Lessons Learned
Challenges & Lessons Learned
This module presented a unique and valuable learning experience by requiring rigorous application of mathematical logic and programming concepts.
Formal Verification: Program Verification, using Hoare's Triples and Mathematical Induction, proved to be the most challenging area. It required a complete understanding of the formal, step-by-step mathematical proof to guarantee code correctness. Whilst this was difficult, solving it proved to be immensely rewarding.
Adapting to Java: Working with Java for the first time was a foundational challenge. Beyond learning the new syntax and IDE (NetBeans), implementing the data structures required adapting my C++ understanding to a new environment. This reinforced core language-agnostic programming principles.
Data Structure Logic: Implementing the core logic for the various linked lists was challenging. Debugging complex pointer logic and ensuring proper handling of edge cases provided a crucial-hands on experience with dynamic data structure manipulation.
Formal Understanding: There was a brief misunderstanding with an invariant problem centred around even numbers, this highlighted the importance of understanding the mathematical notations before tackling the questions.
Grade
Grade
Module Grade: 97%
Page updated
Google Sites
Report abuse