Meta Option A (Baseline) Asymptotic Analysis
If you feel that this meta option is too simple for you, feel free to select one of the meta options B or C below. If you are unsure, just go ahead with this meta option A.
Within this meta option A, you have to do the sub-option based on the last digit of your GWID, and from the list options shared with you. Each suboption asks you to analyze a piece of code. You are then required to do the following.
- Analyze and write the time complexity of the given program.
- Explain your analysis
- Confirm the time complexity by writing a program and simulating it. Run the code for different values of n. (You will have to play with different values of n that make sense for your question.)
- Document time taken for different values of n
- Draw a graph of theoretical results (from Step 1) and experimental results (Step 2 b) to compare. You may have to change the scale (log scale, etc) to get straight lines. If the plots are curves, we cannot easily compare them.
For more details, see the Asymptotic Analysis Process file, or see this Workbook.
See this Sample Submission for structure.
Meta Option B (Data Structure) Analysis
2a. Analyze Union Find data structure. Implement it. Run experiments on it, and show that the time complexity of m unions and n finds matches the theoretical prediction.
2b. Analyze Bloom Filter data structure. Implement it. Run experiments on it, and show that the time complexity of m unions and n finds matches the theoretical prediction.
Meta Option C (Asymptotic Design) Project
Design a gradebook software, which allows the following features:
- Import a gradebook (CSV file), with fields: “firstname, lastname, email, phone, city, score (0-1000 integer value), department”
- Search the gradebook, with information like: “search key”
- Search should run in O(log n + k) time searching on ALL of its fields, where k is the number of results returned by the search