Starting from:
$45
COMP251 Final Programming Assignment Solution
General Information
1 Background
McGill recently received an influx of COMP 251 students complaining about not being able to make it to class on time. The students say that 10 minutes is not enough time to get from lower campus all the way to the Stewart Biology building!
Before you start tackling these challenges, it is important to be familiar with the system you will be working on, so the STM has included an on-boarding guide to help you get going.
2 Onboarding
• Under no circumstance are you allowed to use artificial intelligence, including LLMs (ChatGPT, Claude, etc.), to assist you with this project. If you have Copilot or any other LLM codeautocomplete system installed in your development environment, you must disable it while working on this assignment. We will be able to tell if you are using LLMs. It is painfully obvious which students have used them in the mini programming assignments.
2.2 Code review process
During the code review, it is expected that you will be able to
• Explain every part of your code and why you decided on your approaches, and
• Provide time complexities and reasoning for each algorithm you use.
All comments will be removed from your code during the code review; you should be able to understand and explain your implementation without them.
2.3 Setting up your development environment
2.4 Familiarize yourself with the codebase
2.4.1 McMetro:
This is the main class that houses all the software tools for the metro system. It contains the following fields:
• tracks: An array of tracks (type: Track Section 2.4.2) planned to be built
• buildingTable: A hashmap mapping BuildingIDs to Buildings (type: HashMap<BuildingID, Building> Section 2.4.3)
There are a 5 of methods you will implement in this class that we will discuss in Section 3.
2.4.2 Track:
Tracks represent the metro connections between buildings. They are comprised of the fields:
• id (TrackID): Unique identifier for the track.
• startBuilding (BuildingID): UID for the building at the start of the track
• endBuilding (BuildingID): UID for the building at the end of the track
• cost (int): The cost of constructing the track
• capacity (int): The maximum amount of passengers that can travel on the track at once.
2.4.3 Building:
Represents a location that can be connected by a Track. Has the fields:
• id (BuildingID): UID for the building
• occupants (int): Number of people in the building
2.4.4 Disjoint Set:
This is a naive implementation of a disjoint set data structure that will help you in your solutions. You must implement path compression and union-by-size or union-by-rank; otherwise, your code will be too slow for the STM to use.
2.5 Testing locally
There is a testing template file included with the project files. The intention is that you should test your code locally before submitting. To encourage you to do so, you are limited to 50 submissions on Ed. That is, if you submit 50 times, your 50th submission will be counted as your final code.
The example tests provided will help you make sure that your solution is handling the inputs and outputs correctly and give you an idea of how to write your own tests. As mentioned in Section 2.3, there will be a tutorial with extra information on testing.
3 Objectives
3.1 DisjointSet<T>
You are provided with a generic disjoint set class implemented naively. You must add path compression for the find method and union by size or union by rank for the union method. While this class will not be tested directly, you will need to use it in one or more of the subsequent tasks.
3.2 maxPassengers(BuildingID start, BuildingID end):
Given the IDs of two buildings, find the maximum number of people that can be transported from start to end for the given metro network. This is a method on the McMetro class, the buildingTable and tracks fields define the metro network. The number of people that can travel between two buildings is the minimum between the number of occupants in each of the buildings, and the capacity of the track connecting the two buildings (the numerator in Section 3.3). If there is no track connecting two buildings, no one can travel directly between the buildings. The graph is sparse; this should influence your data structure choice.
3.3 bestMetroSystem()
The STM wants to figure out the best metro system they can construct, now assuming that tracks move in both directions and can therefore be treated as undirected edges. They do not want to build more tracks than necessary. You must find a subset of TrackIDs in the tracks field on McMetro class such that
• There are no cycles within the returned tracks,
• Every building has at least one track associated with it,
• The subset maximizes the number of people that can be transported taking into account the cost of building each track.
You can assume the network is connected. The order in which the TrackIDs are returned does not matter. The “goodness” of a track can be calculated with the formula
min(start building, end building, track capacity) ⌊ ⌋ track cost
3.4 static addPassenger(String name) + static searchForPassengers(String firstLetters)
In this this task, you will implement a system to add passengers and search for passengers in McMetro’s system. The addPassenger method will add a new passenger to the search system and the searchForPassengers method will return all the passengers in the system whose names begin with firstLetters. You can assume that we are only storing first names in the system (no spaces) and that if multiple users with identical names exist in the system, we only return one of them. When searching for passengers, the letter case of the names and of firstLetters should not matter (Alex == aLeX), but when we return search results, the first letter of each name should be capitalized. Names should be returned in alphabetical order.
3.4.1 A note on the trie data structure
In order to achieve optimal time complexity for this task, you will need to implement a prefix tree, also known as a trie.
The idea is to start with a tree data structure where a path from the root node to an “end node” in the tree represents a word. When we add a word to the trie, the first letter of the word will be added as a child of the root node (call it c1), the second letter will be added as a child of c1 (call it c2). When we get to the last letter of the word, if the word is k letters long, we mark ck as an end node.
The metro system will be very expensive to build. In order to protect their ROI, McGill insists that there be some level of security to check that passengers riding the metro have bought tickets, so they have decided to hire ticket checkers. They received many qualified applicants for this role, and the applicants have each indicated the times they are free. It was decided that there does not always need to be someone checking tickets, and there never needs to be more than one person checking tickets.
The method returns the maximum number of workers we can hire with non overlapping schedules such that an applicant is hired over the entire interval that they provide.
4 Support
4.1 Ed
As always, we will be accessible on Ed for questions regarding the project. If your question contains information about your implementation or ideas, please make the post private, but if it is asking for clarification about the rules or guidelines, it can be made public.
4.2 Tutorials
5 Acknowledgements
This assignment was created by Joshua Dall’Acqua in collaboration with Will Zahary Henderson and Giulia Alberini.
This material belongs to the course staff of COMP 251. This document, along with all associated code, shall not be shared with anyone outside of the class.
Again, please don’t cheat (we will know), and have fun!
6 Edits
• (Dec 5, 6:16PM) Clarified some wording on the notion of “connectedness” in bestMetroSystem.
Clarified wording on signatures in DisjointSet.
• (Dec 6, 9:30AM) Added floor division to Section 3.3 to remove ambiguity
1 Background
McGill recently received an influx of COMP 251 students complaining about not being able to make it to class on time. The students say that 10 minutes is not enough time to get from lower campus all the way to the Stewart Biology building!
Before you start tackling these challenges, it is important to be familiar with the system you will be working on, so the STM has included an on-boarding guide to help you get going.
2 Onboarding
• Under no circumstance are you allowed to use artificial intelligence, including LLMs (ChatGPT, Claude, etc.), to assist you with this project. If you have Copilot or any other LLM codeautocomplete system installed in your development environment, you must disable it while working on this assignment. We will be able to tell if you are using LLMs. It is painfully obvious which students have used them in the mini programming assignments.
2.2 Code review process
During the code review, it is expected that you will be able to
• Explain every part of your code and why you decided on your approaches, and
• Provide time complexities and reasoning for each algorithm you use.
All comments will be removed from your code during the code review; you should be able to understand and explain your implementation without them.
2.3 Setting up your development environment
2.4 Familiarize yourself with the codebase
2.4.1 McMetro:
This is the main class that houses all the software tools for the metro system. It contains the following fields:
• tracks: An array of tracks (type: Track Section 2.4.2) planned to be built
• buildingTable: A hashmap mapping BuildingIDs to Buildings (type: HashMap<BuildingID, Building> Section 2.4.3)
There are a 5 of methods you will implement in this class that we will discuss in Section 3.
2.4.2 Track:
Tracks represent the metro connections between buildings. They are comprised of the fields:
• id (TrackID): Unique identifier for the track.
• startBuilding (BuildingID): UID for the building at the start of the track
• endBuilding (BuildingID): UID for the building at the end of the track
• cost (int): The cost of constructing the track
• capacity (int): The maximum amount of passengers that can travel on the track at once.
2.4.3 Building:
Represents a location that can be connected by a Track. Has the fields:
• id (BuildingID): UID for the building
• occupants (int): Number of people in the building
2.4.4 Disjoint Set:
This is a naive implementation of a disjoint set data structure that will help you in your solutions. You must implement path compression and union-by-size or union-by-rank; otherwise, your code will be too slow for the STM to use.
2.5 Testing locally
There is a testing template file included with the project files. The intention is that you should test your code locally before submitting. To encourage you to do so, you are limited to 50 submissions on Ed. That is, if you submit 50 times, your 50th submission will be counted as your final code.
The example tests provided will help you make sure that your solution is handling the inputs and outputs correctly and give you an idea of how to write your own tests. As mentioned in Section 2.3, there will be a tutorial with extra information on testing.
3 Objectives
3.1 DisjointSet<T>
You are provided with a generic disjoint set class implemented naively. You must add path compression for the find method and union by size or union by rank for the union method. While this class will not be tested directly, you will need to use it in one or more of the subsequent tasks.
3.2 maxPassengers(BuildingID start, BuildingID end):
Given the IDs of two buildings, find the maximum number of people that can be transported from start to end for the given metro network. This is a method on the McMetro class, the buildingTable and tracks fields define the metro network. The number of people that can travel between two buildings is the minimum between the number of occupants in each of the buildings, and the capacity of the track connecting the two buildings (the numerator in Section 3.3). If there is no track connecting two buildings, no one can travel directly between the buildings. The graph is sparse; this should influence your data structure choice.
3.3 bestMetroSystem()
The STM wants to figure out the best metro system they can construct, now assuming that tracks move in both directions and can therefore be treated as undirected edges. They do not want to build more tracks than necessary. You must find a subset of TrackIDs in the tracks field on McMetro class such that
• There are no cycles within the returned tracks,
• Every building has at least one track associated with it,
• The subset maximizes the number of people that can be transported taking into account the cost of building each track.
You can assume the network is connected. The order in which the TrackIDs are returned does not matter. The “goodness” of a track can be calculated with the formula
min(start building, end building, track capacity) ⌊ ⌋ track cost
3.4 static addPassenger(String name) + static searchForPassengers(String firstLetters)
In this this task, you will implement a system to add passengers and search for passengers in McMetro’s system. The addPassenger method will add a new passenger to the search system and the searchForPassengers method will return all the passengers in the system whose names begin with firstLetters. You can assume that we are only storing first names in the system (no spaces) and that if multiple users with identical names exist in the system, we only return one of them. When searching for passengers, the letter case of the names and of firstLetters should not matter (Alex == aLeX), but when we return search results, the first letter of each name should be capitalized. Names should be returned in alphabetical order.
3.4.1 A note on the trie data structure
In order to achieve optimal time complexity for this task, you will need to implement a prefix tree, also known as a trie.
The idea is to start with a tree data structure where a path from the root node to an “end node” in the tree represents a word. When we add a word to the trie, the first letter of the word will be added as a child of the root node (call it c1), the second letter will be added as a child of c1 (call it c2). When we get to the last letter of the word, if the word is k letters long, we mark ck as an end node.
The metro system will be very expensive to build. In order to protect their ROI, McGill insists that there be some level of security to check that passengers riding the metro have bought tickets, so they have decided to hire ticket checkers. They received many qualified applicants for this role, and the applicants have each indicated the times they are free. It was decided that there does not always need to be someone checking tickets, and there never needs to be more than one person checking tickets.
The method returns the maximum number of workers we can hire with non overlapping schedules such that an applicant is hired over the entire interval that they provide.
4 Support
4.1 Ed
As always, we will be accessible on Ed for questions regarding the project. If your question contains information about your implementation or ideas, please make the post private, but if it is asking for clarification about the rules or guidelines, it can be made public.
4.2 Tutorials
5 Acknowledgements
This assignment was created by Joshua Dall’Acqua in collaboration with Will Zahary Henderson and Giulia Alberini.
This material belongs to the course staff of COMP 251. This document, along with all associated code, shall not be shared with anyone outside of the class.
Again, please don’t cheat (we will know), and have fun!
6 Edits
• (Dec 5, 6:16PM) Clarified some wording on the notion of “connectedness” in bestMetroSystem.
Clarified wording on signatures in DisjointSet.
• (Dec 6, 9:30AM) Added floor division to Section 3.3 to remove ambiguity
1 file (87.1KB)
