20. Real‑World DSA Projects

Introduction

In modern software engineering, selecting the right data structure can make the difference between a sluggish prototype and a responsive, scalable application. This chapter guides you through building a Student‑Course Management System (SCMS) that combines three classic structures: a hash map for instant student record retrieval, an AVL (self‑balancing binary search tree) for ordered listings, and a graph to power peer‑recommendation features. Each structure is introduced with its theoretical foundations, followed by concrete implementation details, code snippets, and performance analyses.

System Overview

The SCMS must support the following core operations:

• Add, remove, and retrieve a student by unique ID.
• List all students sorted alphabetically by name or by GPA.
• Enroll a student in a course and track grades.
• Generate a list of peers who share similar course interests for a given student.

To meet these requirements we decompose the problem into three data‑model components and three algorithmic components:

1. Data Model: Student, Course, Enrollment entities.
2. Hash Map: ID → Student for O(1) look‑ups.
3. AVL Tree: Maintains two separate trees—one keyed by name, another by GPA.
4. Graph: Bipartite graph (Students ↔ Courses) used to compute similarity and recommend peers.

Data Model

Student Entity

A student_id="A student record contains:

• ID – a unique integer (primary key).
• Name – string.
• Grades – list of (CourseID, grade points, credit hours) tuples.

The GPA is derived from the grades:

GPA = (Σ (grade_point_i × credit_i)) / Σ credit_i

Where grade_point_i is the numeric value of the letter grade (e.g., A=4.0, B=3.0) and credit_i is the course’s credit weight.

Course Entity

Each course is identified by:

• CourseID – unique string (e.g., "CS101").
• Title – descriptive name.
• Credits – integer credit hours.

Enrollment Entity

An enrollment links a student to a course and stores the achieved grade:

• StudentID
• CourseID
• Grade – letter grade or numeric score.

Hash Map for Student Lookup

Design Choices

We need constant‑time access to a student record given the ID. A hash map (also called a hash table or dictionary) provides average‑case O(1) insert, delete, and search. The key is the student ID; the value is the full Student object.

Hash Function

A simple yet effective hash for integer IDs is:

hash(id) = id mod table_size

Where table_size is a prime number close to the expected capacity (e.g., 1009 for up to 1000 students). Using a prime reduces clustering.

Collision Handling

We adopt separate chaining: each bucket holds a linked list of entries that hash to the same index. Insertion proceeds as:

1. Compute index = hash(ID).
2. Traverse the bucket list; if an entry with the same ID exists, replace it; otherwise append a new node.

Deletion follows a similar traversal and unlinking.

Code Example (Python‑like pseudocode)

class HashMap: def __init__(self, size=1009): self.size = size self.table = [[] for _ in range(size)] def _hash(self, key): return key % self.size def put(self, student_id, student): idx = self._hash(student_id) for pair in self.table[idx]: if pair[0] == student_id: pair[1] = student return self.table[idx].append([student_id, student]) def get(self, student_id): idx = self._hash(student_id) for pair in self.table[idx]: if pair[0] == student_id: return pair[1] return None def remove(self, student_id): idx = self._hash(student_id) for i, pair in enumerate(self.table[idx]): if pair[0] == student_id: del self.table[idx][i] return True return False

Complexity Summary

AVL Tree for Ordered Listings

Why AVL?

While a hash map excels at direct look‑ups, it offers no ordering. For generating sorted lists (by name or GPA) we need a structure that maintains order with efficient insertions, deletions, and traversals. An AVL tree guarantees O(log n) height, ensuring O(log n) search, insert, and delete, and O(n) in‑order traversal.

Node Structure

Each node stores:

• Key – either the student name (string) or GPA (float).
• Value – reference to the Student object.
• Height – integer for balancing.
• Left, Right – child pointers.

Rotations

Balance factor (BF) = height(left) – height(right). After insertion/deletion, if |BF| > 1 we rotate:

• Right Rotation (LL case):

y x / \ Right Rotate(y) / \ x T3 – – – – – – – → T1 y / \ / \ T1 T2 T2 T3

• Left Rotation (RR case) – symmetric.
• Left‑Right (LR) and Right‑Left (RL)** are double rotations.

Insertion Pseudocode

function insert(node, key, student): if node is None: return new Node(key, student) if key < node.key: node.left = insert(node.left, key, student) else if key > node.key: node.right = insert(node.right, key, student) else: node.value = student # duplicate key → update return node node.height = 1 + max(height(node.left), height(node.right)) balance = get_balance(node) # LL if balance > 1 and key < node.left.key: return right_rotate(node) # RR if balance < -1 and key > node.right.key: return left_rotate(node) # LR if balance > 1 and key > node.left.key: node.left = left_rotate(node.left) return right_rotate(node) # RL if balance < -1 and key < node.right.key: node.right = right_rotate(node.right) return left_rotate(node) return node

Example: Ordering by GPA

Suppose we insert the following (ID, GPA) pairs: (101, 3.2), (102, 3.8), (103, 2.9). The AVL tree will keep the root near the median GPA (3.2) and maintain balance after each insertion. An in‑order traversal yields the sorted sequence: 2.9, 3.2, 3.8.

Complexity Summary

Graph Model for Recommendations

Bipartite Representation

The SCMS treats students and courses as two disjoint sets. An edge connects a student to a course if the student is enrolled (or has expressed interest). This bipartite graph enables similarity calculations based on shared courses.

Adjacency List Structure

For memory efficiency we store:

• student_adj[StudentID] → list of CourseIDs.
• course_adj[CourseID] → list of StudentIDs.

Both structures are hash maps (ID → list) for O(1) access to a vertex’s neighbors.

Similarity Metrics

To recommend peers we compute similarity between two students, u and v, based on the courses they share.

• Jaccard Index: J(u,v) = |C(u) ∩ C(v)| / |C(u) ∪ C(v)|
• Cosine Similarity** (using binary vectors): cos(u,v) = |C(u) ∩ C(v)| / (√|C(u)| × √|C(v)|)

Where C(x) denotes the set of courses linked to student x.

Recommendation Algorithm

For a target student t:

1. Retrieve C(t) from the student adjacency list.
2. For each course c ∈ C(t), iterate over course_adj[c] to collect candidate peers.
3. Accumulate a similarity score for each candidate using Jaccard or cosine.
4. Return the top‑k peers with highest scores.

Code Snippet (Python‑like)

def recommend_peers(student_id, k=5, metric='jaccard'): target_courses = set(student_adj.get(student_id, [])) scores = defaultdict(float) for course in target_courses: for peer in course_adj.get(course, []): if peer == student_id: continue peer_courses = set(student_adj.get(peer, [])) if metric == 'jaccard': inter = len(target_courses & peer_courses) union = len(target_courses | peer_courses) score = inter / union if union != 0 else 0 else: # cosine inter = len(target_courses & peer_courses) score = inter / (math.sqrt(len(target_courses)) * math.sqrt(len(peer_courses))) if len(target_courses) and len(peer_courses) else 0 scores[peer] += score # aggregate over shared courses # sort and return top‑k return sorted(scores.items(), key=lambda x: x[1], reverse=True)[:k]

Complexity Summary

Putting It All Together

Architecture Overview

The system comprises three loosely coupled modules:

Typical Workflow

1. Enroll a student:
   – Insert the Student object into the hash map (O(1)).
   – Insert the same object into both AVL trees (O(log n) each).
   – For each course, add an edge in the bipartite graph (O(1) per edge).
2. Update GPA after a grade change:
   – Locate the student via hash map (O(1)).
   – Re‑compute GPA (formula above).
   – Remove and re‑insert the node in the GPA‑AVL tree (2 × O(log n)).
3. Generate recommendations:
   – Retrieve the student’s course list from the hash map (O(1)).
   – Run the recommendation algorithm (see section 3.3).

Sample Pseudo‑UI Interaction

# Enroll system.add_student(2001, "Ada Lovelace", []) system.enroll(2001, "CS101", grade='A') # → descending GPA = system.gpa_tree(): print(node).name}: {node().gpa}") # Recommend peers = system.recommend_peers(2001, k=3) print("Peers like Ada:", peers)

Testing and Validation

Unit Tests

• Hash map: insert, retrieve, delete, collision handling.
• AVL tree: rotations after insert/delete, in‑order traversal yields sorted order.
• Graph: adjacency list updates, similarity computation matches brute‑force for small datasets.

Integration Scenario

Create a dataset of 500 students, each enrolled in 3‑5 random courses from a catalog of 50. Verify:

• Lookup time remains ~ constant as size grows.
• Listing operations scale logarithmically.
• Recommendation results contain at least one shared course for each returned peer (precision check).

Performance Analysis

The following table summarizes empirical measurements (average over 10 runs) for a system with 10 000 students and 2 000 courses.

Extensions and Future Work

• Persistency: Swap hash maps and AVL trees for disk‑based B‑trees or LSM‑trees to handle millions of records.
• Advanced Recommendations: Incorporate weighted grades, course difficulty, or apply matrix factorization for collaborative filtering.
• Concurrency: Use read‑write locks or lock‑free structures to support simultaneous enrollments and queries.
• Analytics Dashboard: Pre‑compute histograms of GPA distribution using segment trees for fast range queries.

Conclusion

By integrating a hash map, AVL trees, and a bipartite graph, the Student‑Course Management System showcases how fundamental data structures solve real‑world problems: rapid look‑ups, ordered reporting, and intelligent recommendations. The modular design lets learners replace any component with a more specialized alternative (e.g., a trie for prefix‑based name search) while preserving the overall architecture. Completing this chapter equips you with the practical intuition needed to select and combine data structures effectively in any software project.