Reference no: EM133933054 , Length: Word Count:2000

Data Structures and Algorithms

Computing and Mathematical Sciences

Title: Critical Care Optimisation: Data Structures and Algorithms for Hospital Efficiency

Introduction
Modern hospitals coordinate patients, staff, equipment, and space in real time. Algorithmic solutions can improve emergency response, reduce delays, and increase reliability.

In this assignment, you will design and implement a modular hospital resource management system using core data structures and algorithms. The system should demonstrate:
Efficient storage and retrieval of patient information.
Fast and reliable pathfinding between hospital departments.
Priority-based scheduling of emergency cases.
Sorting and reporting of patient records at the end of the day.
The assignment consists of four modules (Graph, Hash Table, Heap, Sorting). Each module builds upon the others to simulate hospital operations end-to-end, where:
Graph (Module 1): Provides travel time data between hospital units.
Hash Table (Module 2): Stores patient details and urgency levels for fast retrieval. Heap (Module 3): Combines urgency (from Module 2) and time factors (from Module 1 or input data) to decide who gets treated next. Get top-notch online assignment help.
Sorting (Module 4): Takes all scheduled treatment records and organises them into sorted lists for efficiency analysis and reporting.

Learning Objectives
By completing this assignment, students will be able to:
Implement and analyse adjacency-list graphs, BFS, DFS, and a shortest path algorithm.
Design and evaluate a hash table with collision handling, suitable for 20+ records.
Implement a heap to schedule tasks by a computed priority metric and trace heap operations.
Implement merge sort and quick sort; benchmark and analyse performance under varying inputs.
Integrate multiple data structures into a coherent, testable system.

Module 1: Graph-Based Hospital Navigation
Problem Description
The hospital comprises departments such as Emergency, ICU, Pharmacy, Radiology, Laboratories, Operating Theatres, Wards, and Outpatient Units. Efficient navigation is essential for patient transfers and equipment movement.

Model the floor plan as a weighted, undirected graph:
Nodes represent departments.
Edges represent corridors/pathways between departments.
Weights are walking times (minutes).
Tasks
Graph Construction
Implement a Graph class using an adjacency list.
Support dynamic insertion of departments (nodes) and corridors (weighted edges).
Ensure undirected symmetry (u↔v with same weight).

Algorithms to Implement (no built-in graph libraries):
Breadth-First Search (BFS): Input = source department; Output = reachable departments grouped by level (hops).
Depth-First Search (DFS): Input = source; Output = whether cycles exist and, if found, nodes involved.
Shortest Path Algorithm: Implement A* Algorithm from a source; report path and total cost. Cite the algorithm source and implement from first principles without built-in shortest-path functions.

Test Case Setup
At least 8 departments (nodes).
10-12 weighted corridors (edges).
Include at least one cycle and one isolated department.

Expected Output
Textual/visual graph structure.
BFS results with levels (Level 0, Level 1, ...).
DFS cycle detection (and cycle members if present).
Shortest path and total walking time from the source department to a destination department.

Module 2: Hash-Based Patient Lookup
Problem Description
Clinicians require rapid access to patient records in emergencies. Implement a hash table to store and retrieve patient data efficiently, supporting at least 20 active records without significant performance degradation. Get top-notch online assignment help.
Tasks
Hash Table Design and Implementation (no built-in dict/Map for core logic):
Use either chaining (linked lists) or open addressing (linear probing). Justify the choice in the report.
Implement a simple modulo-based hash function; explain parameter choices (table size, prime selection).
Define a Patient record with fields: PatientID, Name, Age, Department, UrgencyLevel (1-5), TreatmentStatus.

Core Operations:
insert(record): O(1) expected; handle duplicates (update or reject with message).
search(patientID): O(1) expected; return the full patient record or a not-found message.
delete(patientID): O(1) expected; confirm deletion and handle missing keys gracefully.

Collision Handling and Load Management:
Demonstrate at least one collision scenario and show how it is resolved (probe sequence or chain state).
Discuss and (optionally) implement resizing/rehashing when load factor exceeds a threshold (e.g., 0.7).
Explain worst-case behaviors.

Validation and Error Handling:
Validate inputs (e.g., urgency 1-5 only; non-empty names; IDs unique/integer).
Ensure robustness against out-of-range indices and null references.

Testing Requirements:
Insert at least 20 patient records (include diverse urgency levels and departments).

Demonstrate successful searches (hits) and misses; demonstrate deletions and their effect on subsequent searches.
Provide timing snapshots or operation counts to support O(1) expected behaviour claims.

Expected Output:
Log of inserts, searches, and deletes (concise, readable format).
Explicit collision example(s) with intermediate states (e.g., probe indices or chain contents).
Summary of complexity, load factor behaviour, and any resizing.
Deliverables for Module 2
Source code for hash table (with comments and clear function headers).
Test driver demonstrating inserts, searches, deletes, and collision handling.
Short written justification of hash strategy, table size, and hash function.

Module 3: Heap-Based Emergency Scheduling
Problem Description
Emergency cases must be prioritised by urgency level and expected treatment time. Implement a scheduler using a heap that always returns the next highest- priority case.
Priority Metric
Priority = (6 - U) + 1000 / T
U = UrgencyLevel (1 = highest priority, 5 = lowest).
T = Expected treatment time in minutes.
Higher priority values should be treated first (Max Heap recommended).
Tasks
Heap Implementation (array-based binary heap; no use of built-in priority queues):
Choose Max Heap (recommended) and justify; alternatively, use Min Heap with inverted keys.
Implement: insert(request), peek(), extract_priority().
Maintain heap invariants after each operation (percolate up/down).

Integration with Module 2 (Data Flow):
Each request references a PatientID; retrieve UrgencyLevel and TreatmentStatus from the hash table.
Use T (expected time) provided by scenario or by shortest-path estimates

from Module 1 where applicable.
Compute the numeric priority for every request inserted.

Updates, and Edge Cases:

Support updates (e.g., urgency level change) by re-inserting or providing a decrease/increase-key strategy (documented).
Handle invalid PatientID, zero/negative treatment time, or inactive status gracefully.

Tracing and Observability:
Print the heap array after each insert and each extract_priority.
Log the computed priority and the inputs used (U and T) for each request.
Demonstrate at least 10 inserts and 5 extractions in a reproducible test run.

Expected Output
Sequence of heap states after operations (readable array/tree printout).
Log of priority computations for each request.
Evidence that higher-priority patients are consistently served first.
Deliverables for Module 3
Heap source code with comments.
Test driver producing the required logs and traces.
Brief written note on update strategy.

Module 4: Sorting Patient Records
Problem Description
At the end of the day, patient records must be sorted for reporting and analysis. You will implement two comparison-based sorting algorithms and compare their performance.
Tasks
Implementations
Merge Sort (top-down or bottom-up; justify choice).
Quick Sort (choose pivot strategy; justify and discuss its effect). Restrictions: Do not call language-provided sort utilities for core sorting logic.
Sort by treatment duration (minutes).

Dataset Sizes and Input Conditions:

Generate and sort datasets of size 100, 500, and 1000.
For each size, test three conditions: random, nearly sorted (≤10% elements
displaced), and reversed.
Use deterministic random seeds for reproducibility.

Analysis and Visualisation:
Present a table summarising times (and operation counts if collected).
Provide a brief analysis: where does each algorithm excel or degrade and why (pivot choice, recursion depth, cache effects).

Expected Output
Correctly sorted lists
Timing table (and, if available, plots) comparing merge sort and quick sort across input sizes and conditions.
Short written reflection on algorithm choice under different scenarios.
Deliverables for Module 4
Source code for merge sort and quick sort.
Benchmark script and results (tables and optional plots).
Brief write-up on stability and pivot strategy.