Community Library DVD Management System

IFQ664 Assignment 1A/1B - Advanced Algorithms
Student: Dylan Park QUT Master of IT (Computer Science)

---

Overview

Console-based DVD library management system implementing custom data structures and efficient algorithms as required by IFQ664 assignment specifications.

---

Key Features

Custom Data Structures

• Hashtable with Separate Chaining: O(1) average-case operations

  • Prime capacity (1019) and base (37) for optimal distribution
  • Polynomial rolling hash function
  • Load factor α < 1 for minimal collisions

• Top-3 Selection Algorithm: O(n) min-heap approach

  • Single-pass iteration through collection
  • Fixed-size heap (k=3) for memory efficiency
  • 10× faster than full sort for top-k selection

Functionality

Staff Menu:

1. Add new movie DVDs
2. Add copies to existing movies
3. Remove DVD copies (auto-deletes when last copy removed)
4. Register new members
5. Remove members
6. Find member phone by name
7. Find who's renting a specific movie

Member Menu:

1. Browse all movies (alphabetical)
2. Display movie information
3. Borrow DVD (max 5, no duplicates)
4. Return DVD
5. List current borrowings
6. Display top 3 most borrowed movies

---

Technical Implementation

Collections

• MovieCollection: Custom hashtable (no built-in Dictionary/Hashtable)
• MemberCollection: Array-based (capacity 100)
• Member.borrowedTitles: HashSet for O(1) duplicate checking

Algorithm Highlights

• Top-3 Algorithm: O(n) time, O(1) space using min-heap
• Hash Function: O(k) where k = title length
• Collision Resolution: Separate chaining with LinkedList per bucket

Validation & Error Handling

• Duplicate prevention (movies, members, borrowed titles)
• Boundary checking (5-movie limit, zero copies, last-copy deletion)
• Input validation (4-digit passwords, positive durations)

---

Running the Application

Prerequisites

• .NET 6.0 or higher
• Visual Studio 2022 / VS Code

Execution

dotnet run

Login Credentials

Staff: username=staff, password=today123
Test Member: first=Alice, last=Johnson, password=1234

---

Project Structure

├── Program.cs              # Main menu and navigation
├── Movie.cs                # Movie entity with copy tracking
├── MovieCollection.cs      # Custom hashtable + top-3 algorithm
├── Member.cs               # Member entity with borrow logic
└── MemberCollection.cs     # Array-based member storage

---

Algorithmic Complexity

Operation	Time Complexity	Space Complexity
Add/Search/Remove Movie	O(1) average	O(n)
Top-3 Most Borrowed	O(n)	O(1)
Hash Function	O(k)	O(1)
Member Operations	O(n) worst	O(1)

---

Design Decisions

Why min-heap over full sort?
For k=3 and n≤1000, O(n) provides theoretical optimality while maintaining code clarity. The fixed-size heap approach balances algorithmic efficiency with practical implementation.

Why separate chaining over open addressing?

• No tombstone markers needed for deletions
• Graceful performance degradation as α→1
• True O(1) average deletion without rehashing

---