Algorithmic Problem Solving

< - Projects

A demo video is not relevant for this section.

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. Data Structures foundation's provided by the course.

Key Concepts

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.

A state transition diagram from a combinatorics problem, showing a directed graph with a start node 'A' and an end node 'B'. The diagram illustrates the 'Sum Rule' method.

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.

A photograph of a mathematical proof verifying an iterative factorial code loop.

Data Structures

The second half of the module shifted focus from theoretical proofs to practical implementation in Java.

Linked Lists: Demonstrated an understanding of Linked Lists through explanations, diagrams as well as implementation. Adding functionality such as insertion, deletion, and searching nodes by value or index.

- Doubly-Linked List: Engineered specific logic for a Doubly-Linked List, ensuring correct management of next and previous pointers during traversal and modification.

- Circular-Linked List: Developed a Circular-Linked List where the tail node correctly points back to the head, creating a continuous loop.

A diagram of a Circular Linked List showing a sequence of data nodes connected by directional arrows. The final node in the chain has a pointer that loops back to connect with the starting head node, forming a continuous cycle.

Stacks & Queues: Implemented Stack (LIFO) and Queue (FIFO) abstract data types using both Array and list structures. Included push/pop and enqueue/dequeue functionality alongside size checks. For the Queue (Array), I utilised a Circular Buffer to save on potentially expensive computational tasks, moving the front pointer as needed, as opposed to shuffling the elements down as its dequeued.
Arrays: Created a custom Array ADT that handles dynamic addition, removal, retrieval, and capacity checks.

Technical Breakdown

Language: Java
Core Concepts: Formal Logic (Hoare Triples, Invariants), Mathematical Induction, Combinatorics, Program Verification, Abstract Data Types (Stacks, Queues, Arrays), Linked Lists (Singly, Doubly, Circular), Circular Buffers, Memory Management
IDE: NetBeans
Tools: GitHub

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

Module Grade: 97%

View the Project Report

View the Data Structure's Code on GitHub

< - Projects

Page updated

Google Sites

Report abuse