Practical Projects

Chapter 20: Practical Projects

Introduction

This final chapter brings together everything you've learned by building real-world projects. Each project applies multiple data structures and algorithms to solve practical problems. These projects demonstrate how theoretical concepts translate into working applications and provide portfolio pieces for job applications.

Why This Matters

Building projects is essential:

  • Job applications: Portfolio demonstrates skills
  • Understanding: Building solidifies learning
  • Experience: Encounter real-world challenges
  • Problem-solving: Apply multiple concepts together
  • Debugging: Practice finding and fixing bugs
  • Design: Make architectural decisions

How to Use This Chapter

  1. Choose a project - Start with one that interests you
  2. Plan before coding - Design data structures and algorithms
  3. Implement incrementally - Build feature by feature
  4. Test thoroughly - Edge cases and normal cases
  5. Optimize - Profile and improve performance
  6. Document - Explain your design decisions

Project 1: Task Scheduler

Description

Build a task scheduling system that manages tasks with priorities, dependencies, and deadlines.

Features

  • Add tasks with priority, deadline, dependencies
  • Schedule tasks respecting dependencies
  • Find critical path
  • Detect circular dependencies
  • Sort tasks by priority and deadline

Data Structures

  • Priority Queue: Task scheduling by priority
  • Graph: Task dependencies
  • Hash Table: Fast task lookup
  • Topological Sort: Dependency resolution

Implementation

#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Task {
    string id;
    string description;
    int priority;
    int deadline;
    int duration;
    vector<string> dependencies;

    Task(string id, string desc, int pri, int dead, int dur)
        : id(id), description(desc), priority(pri), deadline(dead), duration(dur) {}
};

class TaskScheduler {
private:
    unordered_map<string, Task> tasks;
    unordered_map<string, vector<string>> dependencyGraph;
    unordered_map<string, int> inDegree;

public:
    void addTask(const Task& task) {
        tasks[task.id] = task;
        dependencyGraph[task.id] = task.dependencies;

        // Update in-degrees
        if (inDegree.find(task.id) == inDegree.end()) {
            inDegree[task.id] = 0;
        }

        for (const string& dep : task.dependencies) {
            inDegree[task.id]++;
            if (tasks.find(dep) == tasks.end()) {
                cout << "Warning: Dependency " << dep << " not found!" << endl;
            }
        }
    }

    vector<string> topologicalSort() {
        vector<string> result;
        unordered_map<string, int> tempInDegree = inDegree;
        queue<string> q;

        // Find all tasks with no dependencies
        for (auto& pair : tempInDegree) {
            if (pair.second == 0) {
                q.push(pair.first);
            }
        }

        while (!q.empty()) {
            string taskId = q.front();
            q.pop();
            result.push_back(taskId);

            // Reduce in-degree for dependent tasks
            for (auto& pair : dependencyGraph) {
                for (const string& dep : pair.second) {
                    if (dep == taskId) {
                        tempInDegree[pair.first]--;
                        if (tempInDegree[pair.first] == 0) {
                            q.push(pair.first);
                        }
                    }
                }
            }
        }

        if (result.size() != tasks.size()) {
            cout << "Error: Circular dependency detected!" << endl;
            return {};
        }

        return result;
    }

    vector<Task> scheduleByPriority() {
        vector<Task> scheduled;

        for (auto& pair : tasks) {
            scheduled.push_back(pair.second);
        }

        // Sort by priority (higher first) then deadline (earlier first)
        sort(scheduled.begin(), scheduled.end(), [](const Task& a, const Task& b) {
            if (a.priority != b.priority) {
                return a.priority > b.priority;
            }
            return a.deadline < b.deadline;
        });

        return scheduled;
    }

    void printSchedule(const vector<string>& order) {
        cout << "\n=== Task Schedule ===" << endl;
        int currentTime = 0;

        for (const string& taskId : order) {
            Task& task = tasks[taskId];
            cout << "Time " << currentTime << "-" << (currentTime + task.duration)
                 << ": " << task.id << " - " << task.description
                 << " (Priority: " << task.priority
                 << ", Deadline: " << task.deadline << ")" << endl;
            currentTime += task.duration;
        }
    }

    int criticalPath() {
        vector<string> order = topologicalSort();
        if (order.empty()) return -1;

        unordered_map<string, int> earliestStart;

        for (const string& taskId : order) {
            Task& task = tasks[taskId];
            int start = 0;

            // Find maximum finish time of dependencies
            for (const string& dep : task.dependencies) {
                if (earliestStart.find(dep) != earliestStart.end()) {
                    start = max(start, earliestStart[dep] + tasks[dep].duration);
                }
            }

            earliestStart[taskId] = start;
        }

        // Find maximum finish time
        int maxFinish = 0;
        for (const string& taskId : order) {
            maxFinish = max(maxFinish, earliestStart[taskId] + tasks[taskId].duration);
        }

        return maxFinish;
    }
};

int main() {
    TaskScheduler scheduler;

    // Add tasks
    scheduler.addTask(Task("A", "Design UI", 5, 10, 3));
    scheduler.addTask(Task("B", "Setup Database", 5, 8, 2));
    scheduler.addTask(Task("C", "Implement Backend", 4, 15, 5));
    scheduler.addTask(Task("D", "Connect Frontend", 3, 18, 4));
    scheduler.addTask(Task("E", "Testing", 5, 20, 2));

    // Add dependencies
    scheduler.addTask(Task("C", "Implement Backend", 4, 15, 5));
    auto& taskC = scheduler;
    Task taskWithDeps("C", "Implement Backend", 4, 15, 5);
    taskWithDeps.dependencies = {"B"};
    scheduler.addTask(taskWithDeps);

    Task taskD("D", "Connect Frontend", 3, 18, 4);
    taskD.dependencies = {"A", "C"};
    scheduler.addTask(taskD);

    Task taskE("E", "Testing", 5, 20, 2);
    taskE.dependencies = {"D"};
    scheduler.addTask(taskE);

    // Get topological order
    vector<string> order = scheduler.topologicalSort();

    if (!order.empty()) {
        scheduler.printSchedule(order);

        cout << "\n=== Priority Schedule ===" << endl;
        vector<Task> priorityOrder = scheduler.scheduleByPriority();
        for (const Task& task : priorityOrder) {
            cout << task.id << " - " << task.description
                 << " (Priority: " << task.priority << ")" << endl;
        }

        int criticalTime = scheduler.criticalPath();
        cout << "\nCritical Path Duration: " << criticalTime << " time units" << endl;
    }

    return 0;
}

Enhancements

  1. Persistent storage (file or database)
  2. Recurring tasks
  3. Resource constraints
  4. Gantt chart visualization
  5. Task completion tracking

Project 2: Text Search Engine

Description

Build a simple search engine that indexes documents and supports fast text search.

Features

  • Index multiple documents
  • Search for keywords
  • Rank results by relevance
  • Support phrase search
  • Autocomplete suggestions

Data Structures

  • Trie: Autocomplete
  • Inverted Index: Fast keyword search
  • Hash Table: Document storage
  • Heap: Top-K results

Implementation

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <algorithm>
#include <cctype>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    int frequency;

    TrieNode() : isEndOfWord(false), frequency(0) {}
};

class Trie {
private:
    TrieNode* root;

    void collectWords(TrieNode* node, string prefix, vector<pair<string, int>>& results) {
        if (node->isEndOfWord) {
            results.push_back({prefix, node->frequency});
        }

        for (auto& pair : node->children) {
            collectWords(pair.second, prefix + pair.first, results);
        }
    }

public:
    Trie() : root(new TrieNode()) {}

    void insert(const string& word) {
        TrieNode* curr = root;

        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                curr->children[ch] = new TrieNode();
            }
            curr = curr->children[ch];
        }

        curr->isEndOfWord = true;
        curr->frequency++;
    }

    vector<pair<string, int>> autocomplete(const string& prefix) {
        TrieNode* curr = root;

        for (char ch : prefix) {
            if (curr->children.find(ch) == curr->children.end()) {
                return {};
            }
            curr = curr->children[ch];
        }

        vector<pair<string, int>> results;
        collectWords(curr, prefix, results);

        // Sort by frequency
        sort(results.begin(), results.end(),
             [](const pair<string, int>& a, const pair<string, int>& b) {
                 return a.second > b.second;
             });

        return results;
    }
};

class SearchEngine {
private:
    struct Document {
        int id;
        string title;
        string content;
    };

    vector<Document> documents;
    unordered_map<string, vector<int>> invertedIndex;  // word -> document IDs
    Trie autocomplete;

    string toLowerCase(const string& str) {
        string result = str;
        transform(result.begin(), result.end(), result.begin(), ::tolower);
        return result;
    }

    vector<string> tokenize(const string& text) {
        vector<string> tokens;
        stringstream ss(toLowerCase(text));
        string word;

        while (ss >> word) {
            // Remove punctuation
            word.erase(remove_if(word.begin(), word.end(), ::ispunct), word.end());
            if (!word.empty()) {
                tokens.push_back(word);
            }
        }

        return tokens;
    }

public:
    void addDocument(int id, const string& title, const string& content) {
        documents.push_back({id, title, content});

        vector<string> words = tokenize(title + " " + content);

        for (const string& word : words) {
            invertedIndex[word].push_back(id);
            autocomplete.insert(word);
        }
    }

    vector<pair<int, int>> search(const string& query) {
        vector<string> queryWords = tokenize(query);
        unordered_map<int, int> docScores;

        for (const string& word : queryWords) {
            if (invertedIndex.find(word) != invertedIndex.end()) {
                for (int docId : invertedIndex[word]) {
                    docScores[docId]++;
                }
            }
        }

        // Convert to vector and sort by score
        vector<pair<int, int>> results;
        for (auto& pair : docScores) {
            results.push_back({pair.first, pair.second});
        }

        sort(results.begin(), results.end(),
             [](const pair<int, int>& a, const pair<int, int>& b) {
                 return a.second > b.second;
             });

        return results;
    }

    void printResults(const vector<pair<int, int>>& results) {
        cout << "\n=== Search Results ===" << endl;

        if (results.empty()) {
            cout << "No results found." << endl;
            return;
        }

        for (const auto& result : results) {
            int docId = result.first;
            int score = result.second;

            for (const Document& doc : documents) {
                if (doc.id == docId) {
                    cout << "Doc " << docId << " (Score: " << score << ")" << endl;
                    cout << "Title: " << doc.title << endl;
                    cout << "Content: " << doc.content.substr(0, 100) << "..." << endl;
                    cout << endl;
                }
            }
        }
    }

    void printAutocomplete(const string& prefix) {
        vector<pair<string, int>> suggestions = autocomplete.autocomplete(prefix);

        cout << "\n=== Autocomplete for '" << prefix << "' ===" << endl;

        if (suggestions.empty()) {
            cout << "No suggestions found." << endl;
            return;
        }

        for (int i = 0; i < min(5, (int)suggestions.size()); i++) {
            cout << suggestions[i].first << " (" << suggestions[i].second << ")" << endl;
        }
    }
};

int main() {
    SearchEngine engine;

    // Add documents
    engine.addDocument(1, "Introduction to Algorithms",
        "Algorithms are step-by-step procedures for solving problems. "
        "This book covers sorting, searching, and graph algorithms.");

    engine.addDocument(2, "Data Structures Fundamentals",
        "Data structures organize and store data efficiently. "
        "Common structures include arrays, linked lists, trees, and graphs.");

    engine.addDocument(3, "Advanced Sorting Techniques",
        "This guide explores advanced sorting algorithms like quicksort, "
        "mergesort, and heapsort with complexity analysis.");

    // Search
    vector<pair<int, int>> results = engine.search("algorithms sorting");
    engine.printResults(results);

    // Autocomplete
    engine.printAutocomplete("algo");
    engine.printAutocomplete("sort");

    return 0;
}

Enhancements

  1. TF-IDF ranking
  2. Boolean queries (AND, OR, NOT)
  3. Fuzzy search (edit distance)
  4. Phrase search
  5. Document clustering

Project 3: LRU Cache

Description

Implement a Least Recently Used (LRU) cache with O(1) operations.

Data Structures

  • Hash Table: O(1) lookup
  • Doubly Linked List: O(1) insertion/deletion

Implementation

#include <iostream>
#include <unordered_map>
using namespace std;

class LRUCache {
private:
    struct Node {
        int key, value;
        Node *prev, *next;

        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    int capacity;
    unordered_map<int, Node*> cache;
    Node *head, *tail;

    void addToFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToFront(Node* node) {
        removeNode(node);
        addToFront(node);
    }

public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }

        Node* node = cache[key];
        moveToFront(node);
        return node->value;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            Node* node = cache[key];
            node->value = value;
            moveToFront(node);
        } else {
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addToFront(newNode);

            if (cache.size() > capacity) {
                Node* lru = tail->prev;
                removeNode(lru);
                cache.erase(lru->key);
                delete lru;
            }
        }
    }

    void display() {
        cout << "Cache (MRU -> LRU): ";
        Node* curr = head->next;
        while (curr != tail) {
            cout << "(" << curr->key << ":" << curr->value << ") ";
            curr = curr->next;
        }
        cout << endl;
    }
};

int main() {
    LRUCache cache(3);

    cache.put(1, 10);
    cache.display();

    cache.put(2, 20);
    cache.display();

    cache.put(3, 30);
    cache.display();

    cout << "Get(2): " << cache.get(2) << endl;
    cache.display();

    cache.put(4, 40);  // Evicts key 1
    cache.display();

    cout << "Get(1): " << cache.get(1) << endl;  // Returns -1
    cout << "Get(3): " << cache.get(3) << endl;

    return 0;
}

Project 4: Social Network Graph

Description

Model a social network with friend relationships and implement network analysis features.

Features

  • Add users and friendships
  • Find mutual friends
  • Suggest friends (friends of friends)
  • Find shortest path between users
  • Detect communities

Data Structures

  • Graph (Adjacency List): Friend relationships
  • BFS: Shortest path
  • Union-Find: Community detection

Project Ideas (Additional)

Easy

  1. Phone Book: Hash table with contact management
  2. Music Playlist: Doubly linked list with shuffle
  3. Browser History: Stack for back/forward navigation
  4. Expression Evaluator: Stack for postfix evaluation
  5. File System Simulator: Tree structure

Medium

  1. Route Planner: Dijkstra's algorithm for GPS navigation
  2. Spell Checker: Trie with edit distance
  3. Memory Allocator: Free list management
  4. Database Index: B-tree implementation
  5. Compression Tool: Huffman coding

Hard

  1. Git-like Version Control: Directed acyclic graph
  2. Map Reduce Framework: Distributed hash table
  3. Chess Engine: Minimax with alpha-beta pruning
  4. Compiler: Parser using tree structures
  5. NoSQL Database: LSM-tree or B+ tree

Best Practices

  1. Plan before coding: Design data structures first
  2. Start simple: MVP then add features
  3. Test incrementally: Test each feature as you build
  4. Handle edge cases: Empty inputs, null pointers, overflow
  5. Document code: Explain design decisions
  6. Version control: Use Git from the start
  7. Measure performance: Profile and optimize hotspots

Common Mistakes

  1. Skipping design phase - Code without planning
  2. Over-engineering - Too complex for requirements
  3. Not testing edge cases - Bugs in production
  4. Premature optimization - Optimize before profiling
  5. Poor code organization - Spaghetti code
  6. No error handling - Crashes on invalid input
  7. Ignoring memory management - Memory leaks

Debugging Tips

  1. Use debugger - Step through code
  2. Add logging - Track program flow
  3. Test components separately - Unit tests
  4. Simplify test cases - Minimal reproducible example
  5. Check assumptions - Assertions
  6. Review recent changes - Git diff
  7. Ask for code review - Fresh perspective

Portfolio Tips

  1. README: Explain project, features, how to run
  2. Clean code: Follow style guidelines
  3. Tests: Demonstrate correctness
  4. Documentation: API docs, design docs
  5. Screenshots/Demo: Show what it does
  6. Performance analysis: Benchmarks
  7. License: Choose appropriate license

Review Questions

  1. Which data structure is best for implementing an LRU cache?
  2. How would you model a social network graph?
  3. What's the difference between BFS and DFS for pathfinding?
  4. How does an inverted index enable fast text search?
  5. Why is topological sort useful for task scheduling?

Reference Checklist

By the end of this chapter, you should have:

  • Built at least one complete project
  • Applied multiple data structures together
  • Implemented efficient algorithms
  • Tested edge cases thoroughly
  • Profiled and optimized code
  • Documented your design
  • Created portfolio-ready code

Conclusion

Congratulations on completing this Data Structures and Algorithms course! You've learned:

  • Foundations: Complexity analysis, Big O notation
  • Data Structures: Arrays, linked lists, stacks, queues, trees, graphs, hash tables
  • Algorithms: Searching, sorting, graph traversals, dynamic programming
  • Advanced Topics: Cryptography, compression, encoding
  • Practical Skills: Debugging, optimization, project building

Next Steps

  1. Practice: Solve problems on LeetCode, HackerRank, Codeforces
  2. Read: "Introduction to Algorithms" (CLRS), "Algorithm Design Manual"
  3. Build: Create more projects, contribute to open source
  4. Learn: Advanced topics like computational geometry, string algorithms
  5. Interview Prep: Practice coding interviews
  6. Specialize: Machine learning, databases, compilers, graphics

Final Thoughts

Data structures and algorithms are the foundation of computer science. Mastery comes from practice—solve problems, build projects, and never stop learning. The patterns you've learned apply across all domains of software engineering.

Good luck on your journey!

Key Takeaway: Building projects solidifies learning by applying multiple concepts together. Start simple, test thoroughly, and iterate. Document your work for your portfolio. The skills you've gained—problem-solving, algorithmic thinking, and systematic debugging—will serve you throughout your career in software engineering.

PreviousReturn to Syllabus