KAIST
EE209: Programming Structures for EE

Assignment 3: Game Ranking System

 

1. Purpose

The goal of this assignment is to deepen your understanding of common dictionary implementations using two fundamental data structures in C: Hash Tables and Binary Search Trees (BSTs). You will learn (1) how each data structure operates, (2) their strengths and weaknesses, and (3) when and why to choose one over the other. By the end, you’ll have practical experience implementing data structures and analyzing their efficiency in real-world scenarios.

2. Background

In online gaming platforms, a player’s skill level is commonly quantified through a Matchmaking Rating (MMR), a numerical measure designed to ensure balanced and competitive matches. When players search for a match, the system typically pairs them with opponents of similar MMR to create fair gameplay experiences. Efficiently managing and retrieving MMR data is essential for maintaining competitive integrity, enhancing user satisfaction, and fostering sustained player engagement.

This assignment requires you to design a simplified Game Ranking System API to support various applications, such as matchmaking programs and ranking dashboards, by managing:

You will implement the system twice: first using a Hash Table, then using a BST. Later, you’ll integrate these implementations strategically to leverage their individual strengths.

3. Assignment Tasks

You'll complete these tasks in order:

NOTE: We provide skeleton code and several utilities (e.g., Makefile and tests) in assignment3.tar.gz. Please download it to your directory before starting your project and check README.md.

4. System Specification

Your API must follow the provided mmr_db.h. Do NOT modify this file. The API supports three categories of operations:


4.1 Database Management Functions

typedef struct MMR_DB *MMR_DB_T; — MMR_DB_T is an object representing the entire game ranking database, maintaining player records and the total number of players in the database.
Function MMR_DB_T CreateMMRDB(void);
Objective Allocates and initializes a new game ranking database.
Return Value
  1. On success, returns a pointer to a new MMR_DB_T object.
  2. On failure (e.g., memory allocation failure), returns NULL.
Function void DestroyMMRDB(MMR_DB_T * db);
Objective Frees all memory associated with the game ranking database and player records.
Guideline Ensure all allocated memory is freed and avoid dangling pointers.
Function int RegisterPlayer(MMR_DB_T db, const char *id);
Objective Adds a new player record to the ranking system with a unique identifier (ID) and an initial MMR value of 0.
Return Value
  1. On success, returns 0.
  2. If same ID already exists in the database, returns 1.
  3. For other failures, returns -1.
Guideline Copy the ID string so that the player record owns its own copy. Consider using strdup(). If you use strdup(), please add -D_GNU_SOURCE after gcc209. (e.g., $ gcc209 -D_GNU_SOURCE -o testclient testclient.c)
Function int UnregisterPlayer(MMR_DB_T db, const char *id);
Objective Removes the player record with the specified ID from the ranking system.
Return Value
  1. On success, returns 0.
  2. If no matching record exists with the given ID, returns 1.
  3. For other failures, returns -1.
Guideline Ensure memory allocated for player record is properly freed.
Function int UpdatePlayerMMR(MMR_DB_T db, const char *id, int mmr_change);
Objective Adjust player’s MMR by the specified change.
Return Value
  1. On success, returns the player’s new MMR.
  2. On failure, returns -1.
Guideline MMR cannot be negative. If addition of mmr_change results in a negative MMR, set the new MMR value to 0.

4.2 MMR Query Functions

Function int GetMMRByID(MMR_DB_T db, const char *id);
Objective Retrieves MMR for a specified player.
Return Value
  1. On success, returns the player’s MMR.
  2. On failure, returns -1.
typedef bool (*MMR_FUNC_T)(const char *id, int mmr); — Function pointer type for iterating over player records. The function should accept a player’s ID and MMR and return a boolean value (true or false).
Function int CountPlayers(MMR_DB_T db, MMR_FUNC_T fp);
Objective Iterates over all player records and counts players matching criteria defined by fp.
Return Value
  1. On success, returns the number of matching (fp returns true) players.
  2. On failure, returns -1.
Guideline This function can be used as a helper function for other operations.

4.3 Rank Query Functions

For easier implementation, you can assume that all users have unique MMR values in all test cases, except during initialization (where MMR = 0). Additionally, the test cases will not include queries for RankByID or IDByRank involving users with an MMR of zero.
Function int GetRankByID(MMR_DB_T db, const char *id);
Objective Returns the rank of specified player in the database.
Return Value
  1. On success, returns the rank.
  2. If the specified ID does not exist in the database, returns 0.
  3. On failure, returns -1.

Function char * GetIDByRank(MMR_DB_T db, int rank);
Objective Retrieves the player’s ID by rank.
Return Value
  1. On success, returns the player’s ID.
  2. On failure, returns NULL.
Guideline Ensure that the function validates the rank parameter (e.g., rank must be positive and within the total number of players).

Note: Handle all invalid inputs robustly (e.g., NULL pointers).

5. Task Guidelines

Each task will be graded independently. The provided test files will help you validate your implementations and receive feedback. A detailed explanation of the build and test process is provided in the next section.


[Task 1] Implementation Using a Hash Table (35 points)

hash table overview

Requirements

Tips

Extra Credit (5 points)

Implement hash table expansion as follows: When the number of player records reaches 75% of the current bucket capacity, double the number of buckets. For instance, expand from 1024 to 2048 buckets when the node count reaches 768 (0.75 × 1024), and expand again from 2048 when the node count reaches 1536 (0.75 × 2048). Continue this expansion up to a maximum capacity of 1,048,576 buckets (2²⁰). After each expansion, ensure all previously stored records remain accessible.


[Task 2] Implementation Using a Binary Search Tree (35 points)

bianry search tree overview

Requirements

Tips

Extra Credit (5 points)

Implement a self-balancing binary search tree (BST), such as an AVL tree or Red-Black tree, to enhance worst-case performance, which can deteriorate significantly in standard unbalanced BSTs. We have included a test case to verify whether your BST implementation maintains self-balancing properties. Failure to pass these tests will not affect your original score; passing them will only grant you extra points.

[Task 3] Integration (20 points)

Integrate the two implementations (Hash Table and BST) into one cohesive system. For each API function, select the data structure most suitable based on its performance characteristics. Your implementation does not need to dynamically adjust based on input; you can select data structures statically. However, ensure that your chosen approach provides better performance than alternative methods in most scenarios.

Tips

[Task 4] Documentation (10 points)

Prepare a comprehensive readme document clearly explaining your design choices and any trade-offs between the two data structure implementations.

Requirements

6. Build and Test

We provide the following directory structure as the starting point for your assignment. All your implementations should be written in the files located in the src folder. The test folder contains test cases that will be used for actual grading.

For documentation (Task 4), you must write your content in the readme file. Additionally, make sure to replace the STUDENT_ID file content with your own student ID before submitting.

├── src/         # Source files (mmr_db implementations and header)
├── test/        # Test functions
├── Makefile     # Build configuration
├── readme       # Documentation (Task 4)
├── STUDENT_ID   # Your student ID (single line)
└── README.md    # This file

To simplify building, testing, and packaging submission of your assignment, we provide a Makefile. You can use the ‘make’ commands to build and test each type of your implementation with the corresponding test cases. Detailed instructions are provided in README.md, so please read it carefully before starting the assignment.

7. Logistics

The test cases are organized into two groups:

7.1 Correctness Test

This step checks whether each implemented functionality returns the correct output. There are 50 test cases, ranging from simple cases to scalability checks. Not all test cases are independent. For instance, test cases targeting UpdatePlayerMMR will not pass if CreateMMRDB and RegisterPlayer are not correctly implemented. Therefore, we highly recommend implementing in order.

These test cases are shared across all three types of implementations. If you pass all correctness tests, you will receive full points for Tasks 1, 2, and 3. The second part of grading will add to or subtract from this score based on performance.

7.2 Performance Test (Black Box Test)

This part evaluates the efficiency and completeness of your implementation. The details vary depending on the implementation type:

Even if your code passes locally, it might fail on the eelab server. Since many students use the same hardware, performance may vary during peak usage. We strongly recommend testing multiple times at different hours to ensure stability. Final grading will be fairly conducted on the same device across all student submissions.

8. Submission

Please submit your assignment using the KLMS submission link. Your submission must be a gzipped tar file named as YourStudentID_assign3.tar.gz. For example, if your student ID is 20251234, the file should be named 20251234_assign3.tar.gz.

You can create this submission file by running the make submit command. This will automatically generate a correctly named tar.gz file. Before running make submit, follow the steps below:

  1. Open the STUDENT_ID file and replace its contents with your actual student ID. This will be used to generate the correct file name.
  2. Download and sign the Observance of Ethics document. Convert the signed document to PDF format and include it in your assignment folder.
  3. Run the make submit command in your terminal. This will package your entire assignment folder into the required tar.gz file.

Your submission file should look like this:

20251234_assign3.tar.gz
20251234_assign3
src
mmr_db.h
mmr_db_ht.c
mmr_db_bst.c
mmr_db_integrated.c
readme
EthicsOath.pdf
NOTE: Please use our Makefile to make your submission file. 
// edit STUDENT_ID with your student id
$ make submit
$ ls 20251234_assign3.tar.gz
20251234_assign3.tar.gz

Grading

If your code cannot be compiled at Haedong lounge server with gcc209, we cannot give you any points (0 point). Please double check before you submit.

We will grade your work on quality from the user's point of view and from the programmer's point of view. To encourage good coding practices, we will deduct points if gcc209 generates warning messages.

From the user's point of view, your module has quality if it behaves as it should.

In part, style is defined by the rules given in The Practice of Programming (Kernighan and Pike), as summarized by the Rules of Programming Style document. These additional rules apply:

Names: You should use a clear and consistent style for variable and function names. One example of such a style is to prefix each variable name with characters that indicate its type. For example, the prefix c might indicate that the variable is of type char, i might indicate int, pc might mean char*, ui might mean unsigned int, etc. But it is fine to use another style -- a style which does not include the type of a variable in its name -- as long as the result is a readable program.

Line lengths: Limit line lengths in your source code to 72 characters. Doing so allows us to print your work in two columns, thus saving paper.

Comments: Each source code file should begin with a comment that includes your name, student ID, and the description of the file.

Comments: Each function should begin with a comment that describes what the function does from the caller's point of view. The function comment should:

Comments: Each structure type definition and each structure field definition should have a comment that describes it. Comments should be written in English.

Please note that passing all provided test cases does not guarantee full credit. TAs may use additional hidden test cases to evaluate the correctness and robustness of your implementation. Manual inspection will also be conducted to ensure your code adheres to the assignment specifications.