🔄 Josephus Problem: Design & Analysis

📌 Project Overview

This project provides a comprehensive solution to the Josephus Problem, a classic algorithmic puzzle where $n$ people stand in a circle and every $k$-th person is eliminated until only one remains. The solution focuses on finding the "safe position" using an optimized mathematical approach.

🧮 Mathematical Model

The algorithm is based on a recursive model that effectively calculates the last person's position:

• Base Case: When only one person remains, they are in the safe position: $$P(1, k) = 0$$
• Recursive Step: For $n > 1$, the position is determined by the formula: $$P(n, k) = (P(n-1, k) + k) \mod n$$

🚀 Algorithm Design

The project implements the Decrease-and-Conquer technique. This strategy reduces the problem size by one in each step, systematically narrowing down the circle to the final survivor.

• Implementation: Developed in C++ using both recursive and iterative logic for efficiency.
• Indexing: The code computes results in 0-based indexing and converts the final output to 1-based indexing for better user clarity.

📊 Analysis & Performance

• Time Complexity: $O(n)$ — Each of the $n$ individuals is processed exactly once.
• Space Complexity: $O(1)$ — The algorithm uses a constant number of variables, requiring no additional memory beyond the input.
• Runtime Analysis: Empirical testing shows a linear increase in execution time relative to input size, validating the theoretical complexity.

📁 Repository Structure

• CodeDAA.cpp: The core C++ implementation of the algorithm.
• DAA_Project_Report.pdf: A detailed academic report covering the mathematical proof, complexity analysis, and runtime results.

👥 The Team

Developed by Computer Science students at King Faisal University:

• Atekah Hussain Aljafar
• Maryam Alshabib
• Kawthar Alyaseen
• Amal Marshad
• Supervised by: Dr. Howayda Said Ahmed Ali

---

Part of the Design and Analysis of Algorithms Course (CS 311) - KFU (October 2024).

Connect with me on LinkedIn for more projects! https://www.linkedin.com/in/ateka-hussain/