Homework 5 (Spring 2025) - HedgeDoc

<style> h3 { border-bottom: 1px solid #ccc; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; background-color: #f7f7f7; border: 1px solid #ccc; } summary { font-weight: bolder; } summary:hover { text-decoration: underline; } .todo { color: #ff00ff; border: 2px dashed #ff00ff; padding: 0em 1em; border-radius: 5px; margin-top: 1em; margin-bottom: 1em; //display: none; // UNCOMMENT TO HIDE TODOs } </style> # Homework 5 -- Sharing Information History (Spring 2025) **Key deadlines**  - **Design plan (submit via Peerceptiv)**: - <span style="color: #ff0000">Plans due by **Wed, April 9 at 11:59:00 pm**</span> - <span style="color: #ff0000">*Hard Submission Deadline*: no late days!</span> - Reviews start Tues, April 8 at 11:59pm - You cannot see/review other plans in Peerceptiv until you have submitted your own plan; to review early, you must submit your own plan early - Reviews due **Fri, April 11 at 11:59pm** <span style="color: #ff0000">(Hard deadline)</span> - Reflections due Wed, April 16 at 11:59pm - **Final deadline: Wed, April 16 at 11:59 pm** :::success **Gearup**: For an overview of the project, check out the gearup from Fall 2024 by Professor Nick DeMarinis (who those from the CS 11/12/17 track have met back in February). It'll put the project in context and describes how to start thinking about each component: - [Gearup Recording (MP4)](https://drive.google.com/file/d/1G1KqZUx4lFDktkf_z741oE6G3wXji1m4/view) - [Gearup Notes (PDF)](https://brown-csci0200.github.io/assets/lectures/reviews/hw5-gearup-notes.pdf) ::: :::warning :warning: **Warning**: This is a design-focused assignment. As you work on it, two important things to keep in mind: - Your first step is to submit a **design plan** by Wednesday, April 9 to Peerceptiv. This is an important chance to get feedback on your work before you start building--please take advantage of this! - **Do not leave this assignment until the last minute.** Design problems can be tricky--you will want to ensure you have the breathing room to step back and think about how to solve problems (and come to hours, take a break, sleep on it, etc.). Trying to rush everything at the end--when you won't have time to think carefully--is likely to get frustrating, and cost you more time overall! As always, we are here to help you think about how to approach problems, but we can be most helpful if you come to us sooner rather than later! ::: As usual, we will maintain a HW5 FAQ post on EdStem to aggregate common questions, so please check there first!  # Overview People have been sharing information via computers long before the Internet. How documents have been shared, both within and across communities, has evolved with the capabilities of hardware and software. In this assignment, we'll explore aspects of this history as it manifests in data structures: you'll implement parts of information-sharing systems from two pivotal moments in computing history: a late-1970s-era Bulletin Board System (BBS), and an early form of web search.  #### Learning Objectives - Apply design and computational ideas to a real-world problem - Practice making design decisions while working with constrained resources - Analyze performance based on constrained resources - Understand how to save and reload data - Use Python libraries to process files - Practice key course ideas in new contexts #### Collaboration policy This assignment uses the default course [collaboration policy](https://docs.cs200.io/collaboration-policy). Roughly, you may discuss conceptual and design issues with others, but the code you write down must be your own. See the collaboration policy for details and examples of what is and isn’t allowed. #### Limited version Students taking the course S/NC, or students who want to do a lighter version of the assignment for less credit, can implement a limited version of the assignment requirements. For details, see [Grading](#Grading). If you are not sure whether the limited version is for you, please email Kathi at cs200-profs@brown.edu (or just sign up for a one-on-one office hours slot). ## Setup You can download the stencil code using this **[Github Classroom](https://classroom.github.com/a/xfQMeRdV)** link. :::warning :warning: **Warning**: **Be sure to read the [**Python Stencil Setup Guide**](https://docs.cs200.io/s/python-stencil-setup-guide)** for important instructions on how to set up VSCode to use the stencil. In particular, **make sure you [set up your environment](https://docs.cs200.io/s/python-stencil-setup-guide#Setting-up-your-environment)**--if you don't this, you won't be able to run any tests! ::: This assignment contains several stencil files with helper functions, which you should not modify. The files **you *will* be modifying** are: - `bbs.py` - `test_bbs.py` - `query_several.py` In the rest of this handout, we'll introduce what each stencil file does and how you should use it, and also how to use the helpers. # Part 1: Community-Curated Resources (BBS Services) **Imagine that you wanted to create a messaging app** in which people could post messages, get summaries of available topics (perhaps filtered by a search term), read, and delete messages. What data structures would you set up? Given what we've covered so far this semester, you might create a message class, set up lists, hashsets, or dictionaries to hold messages, and develop methods for searching and displaying messages, etc. This is something we could certainly build. **But, in this assignment, there's a catch**: To explore some computing history (and how this manifests in data structures), we want to think about how we could build a messaging system like this when computers were much more limited. Specifically, we're going to "rewind" our CS capabilities back to 1978, which was when people first started creating these kinds of systems, which took the form of digital "bulletin boards" to share messages within communities. ## Context Back in 1978, computers were much more resource-constrained than they are today, and were just starting to become available to consumers. (Brown's CS department didn't even exist until 1979!). At the time, computers that consumers could buy looked like this: <table> <tr><td> ![](https://upload.wikimedia.org/wikipedia/commons/8/82/Home_or_Personal_Computers_from_1977_-_Commodore_PET_2001%2C_Apple_II%2C_TRS-80_Model_I%2C_together_called_%27Trinity77%27_%28edited_image%29.jpg) *The "trinity" of personal computers in 1977: (left to right) a PET 1000, Apple II, and TRS-80. These were some of the first personal computers available to consumers, at very high prices--for more info, see [here](https://en.wikipedia.org/wiki/History_of_personal_computers#1977_and_the_emergence_of_the_%22Trinity%22). Image from Wikipedia.* </td> </tr> </table> Computers like these had a tiny fraction of the processing power and memory that our computers and phones have today (the entire memory of one computer wouldn't be enough to hold *a single photo* that you take with your smartphone!). As such, programming languages did not come with lots of libraries and built-ins, and needed to store data in more primitive ways. **You're going to develop a basic bulletin board system (BBS) under constraints that mimic those found in this era of computing.** **Why should you care, you ask?** There are a few reasons: 1. There are still lots of settings today where resource-constrained programming matters (such as in some embedded systems, where a very small chip is part of another device like a hearing aid, or high-performance systems that serve thousands or millions of clients, where every tiny amount of memory used is a big deal). Exposure to this mindset can be useful to you later on! 2. Many of the same design and computational ideas from earlier this semester are present even in these earliest systems, though they show up in different ways. We hope that seeing these same ideas in new settings will help you understand the concepts more deeply. ... we also think it's just fun to think differently now and then, and we hope you'll find this enjoyable too! :smile: ## BBS features :::success **If you're reading for the first time**: This section provides a broad overview of the features of a BBS, as we define it in this assignment. For a more detailed *specification* of what you need to implement, see the later sections, which provide more detail and discuss edge cases, error handling, and assumptions you're allowed to make. ::: In the days of BBS systems, a person who wanted to set up a BBS would connect their computer to a phone line, and give out their number to others who wanted to join the system. Users would connect by using their own phone lines to "dial in" to the BBS, leave messages for others, and then hang up (disconnect) so someone else could join. You can find a demonstration of BBS's functionality [here](https://www.youtube.com/watch?v=MnvBQB9BLEo&t=3m33s). For our BBS, we won't be using phone lines or connecting to a network, but you'll perform the same kinds of operations on your local system. Concretely, here's an example for the kinds of operations a BBS will perform (with examples below, followed by an overview of how this turns into stencil code): - Users connect to the system and provide a username - **Any user can post a (public) message to the system**. Broadly, each message consists of: - An ID number - A subject - The username of the user who posted the message - The actual content of the message (called the *body*) - To find new content, **users can ask for a *summary* of the current messages** on the BBS. A summary is each message's ID number, subject, and poster (i.e., everything except the content). - Optionally, a user can provide a *search string* to filter messages, which shows only messages that include the search string in **the username or subject line** - Once the user sees a message they want to read, they can view the whole message by entering its ID number - Users can also delete messages by ID number. Any user can delete any message. - The system allows switching users (e.g. multiple people connecting from the same computer) - When a user is done, they can fully disconnect from the system. After leaving, the BBS retains all the messages for the next user who connects. Got the idea? Now let's see it in action! ### Example: Using a BBS Here's some examples of what it would look like to use our BBS. The "user interface" for a BBS was via terminal: the system provided a REPL where users could enter commands that would perform the core operations (adding messages, listing a summary of messages, printing messages, etc). Here are some examples for entering commands in our REPL, which we provide for you in `bbs_repl.py`. Let's say user `kathi` connects to the system and posts two messages (using the `A` command, for "**a**dd message"): :::info <pre> $ python3 bbs_repl.py Welcome to our BBS! Enter a username: <b>kathi</b> ==== Welcome kathi! > <b>A "homework update?" "is the handout ready? Need it soon"</b> <i># Add message</i> Created message 1 > <b>A "vscode headache" "reinstall to fix the config error"</b> <i># Add message</i> Created message 2 > <b>X</b> <i># Disconnect</i> $ █ </pre> ::: After that, another user (eg. `nick`) can connect to the system and look for messages (e.g., find all messages containing "homework" in the subject). **Note that the BBS retains data stored to it, even after `kathi` leaves!** Your job will be to implement the core features of the BBS for storing data persistently (in files, rather than just in objects in memory), and then retrieving it when it's requested again. :::info <pre> $ python3 bbs_repl.py Welcome to our BBS! Enter a username: <b>nick</b> ==== Welcome nick! > <b>S homework</b> <i># Get summary of messages with "homework" in the subject</i> ==== ID: 1 Poster: kathi Subject: homework update? > <b>P 1</b> <i># Show message with ID 1</i> ==== ID: 1 Poster: kathi Subject: homework update? Message: is the homework ready? Need it soon </pre> ::: Now that Nick has seen Kathi's message, he can delete it and post a follow-up: :::info <pre> > <b>D 1</b> <i># Delete message 1</i> > <b>A "handout followup" "almost ready to go"</b> <i># Add message</i> Created message 3 > <b>S</b> <i># Show summary of all messages</i> ==== ID: 2 Poster: kathi Subject: vscode headache ==== ID: 3 Poster: nick Subject: handout followup > <b>X</b> <i># Disconnect</i> $ █ </pre> ::: ## What you will build Your task will be to implement the core functionality of the BBS. Specifically, you'll implement several functions to handle the main *operations* the BBS performs (defined in `bbs.py`). :::warning :eyes: **Heads up!** Don't start implementing these functions yet! The remainder of the handout describes more on the specification of how these functions should work, and the constraints you'll be operating under for this assignment. Keep reading for more details! ::: ```python # Connect to the BBS (logging in as user given by username) def connect(username: str): # . . . # Post a message to the BBS (as the currently logged-in user) def post_msg(subj: str, msg: str) -> int: # . . . # Print out the message ID, poster, subj, & msg given by id_num # (Also return the message as a string) def find_print_msg(id_num: int) -> str: # . . . # Print summary of messages where term appears in the subjet or author # If term is "", print all messages # (Also return the summary as a string) def print_summary(term="") -> str: # . . . # Switch to a different user (without disconnecting) def switch_user(username: str): # . . . # Disconnect the current user, saves data so program can be restarted def disconnect(): # . . . # Deletes all files and resets all variables to start a clean run of the BBS def clean_reset(): # . . . ``` These core set of functions define an interface for how the BBS should operate, which we'll use in two ways: - You'll write some tests using these functions to check your BBS's behavior (and our autograder will do the same) - You can go back to 1978 and interact with your BBS like a real user using the REPL (which we provide in `bbs_repl.py`). (You aren't required to do this, but it may be useful for testing as you get started.) ## Requirements and constraints: resource-limited programming, circa 1978 As we've stated, computers in 1978 had only a small fraction of the processing power and memory that our systems have today. Storage devices like hard drives had been invented (mid 1950s), but they were huge, expensive, and only available to large companies or governments. There was only a small amount of memory in the computer itself (~4KB -- that's equivalent to roughly 4000 text characters), and limited file storage (1.2 MB). For context, 1MB is space for roughly 250 pages of text data, or ~20% of a photo you might take on your smartphone--and this was the **total** amount of data that could be stored in the entire computer! To emulate a BBS system of the era, your messages should adhere to the following requirements: <section> ### Message Requirements - Your system should be able to store at most **200 messages** - **Usernames** may be at most 16 characters, and only contain letters and numbers (no spaces or symbols) - The **subject** may be at most 32 characters - The **content** of each message may be at most 128 characters - Message IDs must start at 1, not 0 - Messages will use the following characters only: upper-case and lower-case letters, and the symbols `,.?!#[](){}+=/:;_-` and the space character. - You may assume that all message fields (username, subject, content) will always contain **at least one non-space character**--e.g., an empty string, or just the space character, is not a valid username, subject, etc. - You may assume that your BBS functions will only ever be called using inputs that meet the length and allowed-character requirements. (In other words, you don't need to check that your inputs are well-formed.) - You may assume that `find_print_msg()` and `remove_msg()` both take in an existing message ID in your system. - Messages (and any other metadata in your system) must persist in the BBS after the user disconnects (until deleted, or the system is reset). This means that messages must be stored using files, and you might need to store other metadata in files as well. - Exception: The current user *does not* need to persist across connections. In other words, you may assume that a new user logs in on each new connection. </section> While 200 short messages may not seem like a lot of data, this was still a lot for an early computer system! To emulate what programming was like on an early computing system (and to give you practice with resource-limited programming in other contexts), **your BBS implementation must adhere to the following programming constraints**: <section> ### Constraint 1: Memory is limited With so little working memory (ie, environment and heap space), it would not have been possible to store many messages in memory, or even keep track of the kinds of data we need to implement ArrayLists, hash tables, etc. To emulate this: - **Your program cannot create or use internal data structures or classes** (like lists, dictionaries, etc.) to hold messages or other metadata. In general, it would not have been possible to have a language with these features! - **Your program can have at most 10 global variables** in use at any one time. - You may not store whole messages, or summaries of messages, in **global** string variables. **Exceptions** (to remember for later): We make a few exceptions to the "no internal data structures" rule, particularly for helper functions that process strings: <details> <summary>Expand for details on exceptions</summary> - You may use lists returned by string processing helpers like `str.split()`, `str.partition()`, or regular expression functions. These functions will let you deconstruct a string and access specific numbered portions of the results (e.g., if str = `"hi-there"`, then `str.split("-")[0]` produces `"hi"` and `str.split("-")[1]` produces `"there"`). However, you may not iterate over the results of `str.split()`. - Similarly, you may use `str.join()` to join an array of items from `str.split()` back into a string We allow these functions because writing this functionality by hand is annoying and not instructive within the goals of working with limited memory. </details> </section> In other words, your memory is too limited to store messages through data structures in the heap. Instead, you will need to **store messages in files**, where storage is less limited. <section> ### Constraint 2: File access is expensive Without data structures, you'll have to store data in `.txt` files to save and access data. When working with files, we have two broad constraints: - As we stated earlier, early storage devices were also quite small, so we will have limits on the size and number of files - Compared to storing data in heap memory ([Lecture 26](https://docs.google.com/document/d/1wBjy079DMFMQIA5AieTmL2jbYFRjkJVvxNRP4-TvBY0/edit?tab=t.0)), storing data in files is quite slow. This was true back in 1978, and is still very true today! (Though modern systems can hide this slowness somewhat... take CS 300 to learn more!) Concretely, we will apply the following constraints on files: 1. Your system can store at most 32 files 2. No single line in a file may contain more than 128 characters (not including the newline character `\n` at the end). This means that you must store messages on *at least* two lines if you want to handle all possible messages uniformly. 2. Any one file can contain at most 2048 characters (not including newlines) 4. Since files are slow, **you should try to reduce the number of file operations** (ie, number of times files are opened, number of calls to `readline()`). To discuss this, you will do a **big-O analysis in terms of the numbers of file operations needed by your design** as part of [Task 1.5](#Task-15-Performance-Analysis-PDF). To lower this figure, you should consider storing more than one message per file. :::info ***Note:*** We're not asking you to squeeze every last file access out of your code, but we do want you to use a design that has made reasonable attempts to reduce the number of read/write actions. In terms of how we've discussed big-O, don't worry about minimizing the constants, but instead think about the higher-order multiplicative factors of the key variables. For more information on this, see [Task 1.5](#Task-15-Performance-Analysis-PDF). ::: </section> ## Concrete Tasks Now that we've defined the system and requirements, it's time to start designing! If this sounds like a lot, don't worry: we've structured the assignment so that you have a good amount of time to plan your implementation, ask questions, and get feedback. :::success **What to expect**: **this is a design heavy assignment**: that means that you should spend a good amount of time thinking about *how* you'll implement things before you jump in and start writing code. We've provided a number of resources to help with this: - The gearup provides some background about the project, a demo, and describes a mental model for working with files - Your first task is to submit a design plan for how you'll store and retrieve data from files. You'll receive feedback via peer review, and you can discuss your plan with the course staff - As always, we're here to help talk about your design in office hours and on EdStem, and we encourage you to talk to your peers as well! ::: <section> ### Task 1.1: Create a design plan Before you begin your implementation, you should put together a concrete design plan in a file called `data-design.pdf`. Your design plan should discuss the following: 1. What format will you use for storing messages in files? 2. What is the relationship between messages and files? That is, when writing a message to a file, what files does it go in? (Or, when you read a message, how do you know what file to open?) 3. Do you need any other files to hold additional metadata, other than messages? 4. Write a plan for how `remove_msg` will work (which removes a message given the message ID. You can assume the message exists.) For each question, provide an overview of how your implementation will handle each component, and a brief justification. :::warning **Important notes**: - For details on how each BBS function should operate, see the comments in `bbs.py`, which describe important assumptions you can make - Be sure that your design follows the **[Implementation requirements and constraints](#Requirements-and-constraints-resource-limited-programming-circa-1978)** defined earlier. These will affect your design significantly, so you'll want to plan for these now! - We encourage you to take this planning phase seriously. This assignment is quite open-ended, and this is your chance to get feedabck that will help you later! ::: Your design plan submission is due **Wednesday, April 9 at 11:59pm (though you are welcome to submit earlier to start seeing/reviewing other plans earlier)**. Upload to Peerceptiv for peer review (instructions [here](#Peer-review)). After submitting your design plan, it's okay if you need to revise your design as you work further on the project and get feedback--you don't need to resubmit the plan. :::info <details> <summary>Hints and design-stage notes</summary> - For a primer on how to think about working with files, we recommend checking out the gearup - If you're stuck, start by thinking about how you'd store messages in files, and how you'd begin writing a message to a file. After that, consider how you'd *retrieve* that same message (given its ID number). This should help you gain a more concrete idea on how handle the other operations - You don't need to display (or store) messages ordered by their ID numbers. The order is up to you. </details> ::: </section> <section> ### Task 1.2: Implement the Core Functionality Once you complete your plan and receive feedback, implement the core BBS operations in `bbs.py`. To do this: - For details on how each method should behave, see the comments in `bbs.py` - As you get started, don't worry about reusing space from deleted messages. Just produce a system that stops accepting messages once the message-count limit has been reached. - See the next sections for some important background and implementation notes (more added after the gearup!) ### Implementation notes  - **All new files that your program creates MUST be created inside the `disk` directory.** - The pattern `with open ("filename.txt", mode) as file` will handle opening and closing files without you having to close them manually (there's a summary of file access just below Task 1-2). - **When operating on files, use only the readline() method to read a line of text from a file.** Specifically, you should NOT use helper methods like `readlines()` (plural), which violate our implementation constraints on using data structures. File methods other than `readline()` have semantics that we haven't discussed, which will make it hard to discuss their runtime when you do your Big-O analysis later. - The file `file_utils.py` contains helpers for checking if files exist, removing files, and renaming files. **You should use only these functions** to do these operations: we have designed them specially to work with our stencil, and to avoid edge cases where you might accidentally delete other files, like your code! - For testing purposes, you will want a way to initialize the system with a smaller limit on messages than the 200 allowed in the full system, to make it easier to test when you reach the limit :::danger In particular, **DO NOT USE METHODS IN PYTHON'S `os` PACKAGE**, or any other builtin Python functions for file operations, as a tiny bug might cause you to delete something important from your computer! ::: </section> ## Background: files in python :::info We learned terminal file naviation in **[Lab 6](https://docs.cs200.io/3AW_PFdyQaCsjW9K9waWWA?view#Extracting-Data-from-Files)**! ::: :::success <details> <summary>How to Read and Write to Files in Python</summary> - To **read** a file named `fname.txt` line by line without modifying it, use the `r` flag: ```python with open("fname.txt", "r") as input: line = input.readline() # repeat to read multiple lines # when you reach the end of file, line will be "" ``` - To open a file named `fname.txt` for **writing**, use the following syntax with the `w` flag. *This will replace the contents currently in the file*. If `fname.txt` does not exist, this operation will create a new file fname.txt with "hello" as its contents. ```=python with open("fname.txt", "w") as file: file.write("hello") # write "hello" into the file # if you want to add to the end of the file, # use "a" instead of "w" ``` - To add content, or **append**, to a file named `fname.txt`, use the `a` flag: ```=python with open("fname.txt", "a") as file: file.write("my name is") ``` - It may be helpful to separate certain elements of messages as you write into files. There are a few ways of doing this, one being the newline character, or `\n`. ```=python with open("example.txt", "w") as f: f.write("first line\n") f.write("second line\n") ``` will write in `example.txt`: ```=python first line second line ``` </details> ::: :::success <details> <summary>Helpful Methods and Syntax</summary> - `strip()` can be used to strip off newline chars after readline - `global`: Similar to instance variables, `global` variables are variables you can use throughout the file. To declare global variables, instantiate them at the top, outside of any constructor or function: ```=python my_var = "variable" ``` Then, if you want to modify the value of `my_var` in a function, you would put `global my_var` in the beginning of the function. ```=python def example_func(): global my_var my_var = new_value ``` </details> ::: ::: danger <details> <summary>Allowed/Forbidden Functions</summary> Note that you do not *need* any of these functions, there is a perfectly valid solution that does not use any of these. For any of these functions which are allowed, please use our specified runtimes when analyzing for Task #### Allowed #### - `re` is the Python regex library, which we learned about in [lab 6](https://docs.cs200.io/3AW_PFdyQaCsjW9K9waWWA#). You are allowed to use regex operations on any string that already adheres to the restrictions we've laid out, namely that the string is not larger than 128 characters. In practice, this means that you can use a regex on any individual line of a file, but not on the entire file at once. Similar to `str.split()`, you may not iterate over the results of `re.findall()`, but may access specific numbered portions of the results. Regex matches themselves do not cost any `open`, `read/readline` or `write` operations, but to get the string to do the match, one or more of these operations may still be necessary. #### Not Allowed #### - `.seek(offset)` is a method that can be called on an open file object to move to a particular location in the file to start reading from. This offset is in terms of _bytes_, not characters or lines, which we have not covered how to compute. `seek()` is both more complicated to use and does not save you any `readline` operations. Do not use it. - `json` is the Python library for parsing JSON, a common data format for storage. The `json` library parses data into either dictionaries or other custom objects, both of which are themselves already forbidden in the handout, so this library is by extension also not permitted. - `readlines()` (plural), as mentioned above, is NOT allowed! Only use `readline()` (singular) in your code. Other file methods including `readlines()` violate our data structure implementation constraint. - **DO NOT** use `os.remove`, `os.replace`, or `os.rename`. It's very easy to accidentally remove critical files from your computer. Instead, take a look at some of the functions provided in the stencil, like `remove_file` and `rename_file` from `file_utils.py`! </details> ::: ::: warning <details> <summary>Common File-Reading Bugs</summary> When I try to add text to my file, all of my previously-written text disappears. Why? * You may be opening your file with `'w'` instead of `'a'`. `'w'` (write) clears a file before you start writing, while `'a'` (append) conserves the contents of the file. </details> :::  <section> ### Task 1.3: Handle the Message Limit The limit of 200 messages (which was driven by the memory capacity of disks) poses a challenge: the community could easily run into this limit. It was important, then, that people deleted messages once they were no longer needed. Additionally, the system had to make sure that no more than 200 messages were being stored at any time. There are a couple of approaches here: 1. The system could keep generating new message IDs, but make sure that at most 200 IDs are in active use at any time. 2. The system could track which of the valid IDs between 1 and 200 are (not) in use and allocate available IDs to new messages. In this case, no message ID is ever larger than 200. In either case, an `MessagesFull` exception (provided in the stencil) should be thrown when someone tries to add a 201st active message. Implement **one** of these strategies. The second will [be worth more points than the first](https://docs.cs200.io/GYL6VGu5TGK38VNnmrRwUA?view#Grading) simply because it is more challenging but more efficient (especially since you can't maintain data structures and want to minimize file access). Write a brief description of your approach in a file `hw5.pdf` to help guide the graders in understanding how your implementation works. </section> <section> ### Task 1.4: Testing (Code) Write a collection of test scenarios and assertions for the system in a file `test_bbs.py`. We've defined a basic test example for you, which looks like this: ```python def test_sample_From_handout(): # clean_reset() executed before test bbs.connect("kathi") bbs.post_msg("post homework?", "is the handout ready?") bbs.post_msg("vscode headache", "reinstall to fix the config error") s1 = bbs.print_summary("headache") assert "Poster: kathi" in s1 # Message content NOT part of summary assert "reinstall to fix" not in s1 bbs.switch_user("nick") bbs.post_msg("handout followup", "yep, ready to go") bbs.remove_msg(1) # Kathi's message is first message s2 = bbs.print_summary("followup") assert "Poster: nick" in s2 ``` Your tests should follow a similar format to this. Some notes on how testing works: - To simplify testing, our testing file is configured such that **your BBS resets cleanly between tests** by calling `bbs.clean_reset()` This makes sure your tests should run in a consistent way that matches the autograder - **Be sure to follow the specification for return values from your BBS functions**: many functions return information about your system, in addition to printing text to the screen, so we can use it when testing. For example, `post_msg` should return the ID of the new message, so you then write a test to look it up with `find_print_msg`. See the comments in `bbs.py` for a specification of what each function should return. - Your tests do not need to call `disconnect`, but you should use that in your own testing to make sure that your code does work if restarted. </section> <section> ### Task 1.5: Performance Analysis (PDF) In your `hw5.pdf` file, give a single expression for the cost (number of operations from `open`, `readline`, and `write`) that your implementation has for running: - a single call to `post_msg` - a single call to `remove_msg` - a single call to `print_summary("bear")` State your answer in terms of the variables: - $M$, the maximum number of messages in the system (In our case it is 200 but we call it $M$ to generalize) - $F$, the maximum number of files used to store messages in the system and the constants: - $p$, the cost of a single open-file operation - $r$, the cost of a single readline operation - $w$, the cost of a single write-to-file operation :::info **Note**: You are NOT required to use all of the parameters here. We are just giving definitions for everything we can think of, so that everyone uses consistent notation! ::: **Example**: let's say you want an expression for **multiple** (not single) calls to `post_msg`. If your `post_msg` code opened 1 file per message and did a total of 5 `readline` operations, you would write: `post_msg` needs $p*M + 5r$ if called for $M$ messages Ideally, your design will try to reduce the $M$ and $F$ multipliers on $p$, $r$, and $w$ (but small constants like $5r$ versus $4r$ aren't important). </section> *If you are interested in more details of the technical history, check out the article [Hobbyist Computerized Bulletin Board](https://vintagecomputer.net/cisc367/byte%20nov%201978%20computerized%20BBS%20-%20ward%20christensen.pdf) by Wade Christensen and Randy Suess, which is perhaps the first published design description of a BBS.* # Interlude (no tasks, just some context) Fast forward a few years. Storage is getting larger (desktops were up to 1GB by the mid 1990s). BBS systems and their descendents can store more than a handful of messages. Many systems start to store entire documents. They are also supporting communities that have documents on different topics that people want to organize and search through. For example, the [AfroNet BBS](https://blacksoftware.com/before-blacks-had-the-internet/) took off as an online forum for Black Americans, providing messaging services and information on topics such as black culture, arts, politics, and technology. Enter hierarchical organization. Much like the system of nested folders that you still use today, online community organizations would leverage administrators and volunteers to help manually put documents into their underlying filesystem. # Part 2: Crawl and Commercialize In the early 1990s, the internet was still indexed manually, but there were efforts to gather centralized information on the various documents stored across individual services. The volume of information was growing so fast that people couldn't keep up with the manual work of organizing it. Enter web-crawlers: programs that could walk around the internet, find pages/documents, and organize information about them. Enter search engines, which provided users with tools to access the organized information. Enter a new group of tech entrepreneurs, who saw tremendous commercial opportunity in connecting people with the information they wanted to find, even if they didn't know it existed. #### Structuring Data for Search Concretely, a search engine is a program that takes a search **query** and returns a list of websites that satisfy that query. On the surface, it sounds simple: scan through pages to find ones that contain the query words. In practice, there are several technical challenges, including: - **scale**: as of Jan 2024, there were roughly 3.72 billion pages on the internet - **staying current**: hundreds of thousands of pages are added or edited daily - **prioritization**: how to decide which pages should come first in the output? Modern search engines use data structures creatively to address these challenges. #### A High-Level Example of Querying Pages Here (in the blue boxes) are two barebones "web pages". The part in bold is the title of the page. :::info **CS200 Policies** You have up to three late days. The [syllabus](https://docs.google.com/document/d/14D6T2fpMeLx9-cAsoiQm4-eJF_SoowVNqanEZZcT2xU/edit?tab=t.0#heading=h.gpun8jyluwej) has more solid detail. ::: :::info **CS200 Collaboration Details** Students may discuss ideas with others, but your submitted code *must be yours alone*. This to help solidify your understanding. ::: Here are some sample queries and the lists of page titles each would return: <section> 1. search for "Collaboration" would return `["CS Collaboration Details]"` 2. search for "detail" would return `["CS Collaboration Details", "CS200 Policies"]` - the order doesn't matter - capitalization doesn't matter - plurals don't matter  3. search for "solid" would return `["CS200 Policies"]` - substrings of words don't always match (`"solidify"` stems to `"solidifi"`, not `"solid"`); this case is more obvious for words like `"leak"` and `"bleak"` -- `"bleak"` contains the substring `"leak"` but their meanings are not very similar! - more info on what "stem" means here later! 4. search for "the" would return `[]` ("the" is too common a word to search) 5. search for "google" would return `[]` even though it is part of the URL linked to the word "syllabus" (we ignore URL contents) </section> Your task will be to set up data structures and a collection of functions that support running queries such as the ones above. We will give you the code for a slow and low-quality query engine. You will finish the code for a faster and slightly more sophisticated query engine. ### How are "Pages" stored? On the real internet, web pages are stored in a format called HTML, which is a variant of a document format called . The details of HTML and XML are not important for doing this project: we are giving you the pages on which to test your work, and the stencil provides the functions that you need to extract data from pages. If you are interested, you can expand the next section to see the page structure, but this is not necessary. :::success <details> <summary>How pages are captured in XML</summary> Here's an example with two pages, the first of which is the CS200 Policies page from our example above: ```xml= <xml> <page> <title>CS200 Policies</title> <id>26</id> <text> You have up to three late days. The [[syllabus|https://docs.google.com/document/d/14D6T2fpMeLx9-cAsoiQm4-eJF_SoowVNqanEZZcT2xU/edit?tab=t.0#heading=h.gpun8jyluwej]] has more detail. </text> </page> <page> ... </page> </xml> ``` Each individual web page is wrapped in `<page>...</page>` tags (one within lines 2 and 10, another within lines 11 and 13). Within those tags, there are separate tags to mark off the page *title*, *id number*, and *text* (or content). Multiple pages can appear within the same `<xml>...</xml>` wrapper. The id numbers are unique across pages within the same `xml` wrapper (but otherwise carry no meaning). **Links:** Line 7 shows what a link will look like in our format. It consists of double square brackets around the text to show and the destination page, which are separated from one another with a vertical line. Summarizing: ``` [[link text|URL]] # a link to a URL with the URL hidden [[URL]] # a link in which the URL is also the text ``` Rather than use full http URLs, our test data will just use names of pages as "URLs". They are a lot shorter, and we don't need full URLs (since we aren't loading them into a web browser). For example: ``` [[course policies|CS200 Policies]] ``` </details> ::: ## Understand Slow Query The stencil provides a file named `query_slow.py`, which gives the slow search engine implementation. To run the search engine (lines 17 and 18), the user creates a `QuerySlow` object with the name of the wiki file that contains the pages. The user then calls the `query` method in the object with the term to search for. ```=python= class QuerySlow: matching_titles = [] # the titles of docs with the search term search_term = "" # the search term wikifile = '' # the name of the wikifile being searched def __init__(self, wikifile: str): ... def process_page(self, wiki_page:str) -> None: ... def query(self, search_term: str) -> list: ... # an example of using the search engine def main(): qs = QuerySlow('wikis/Example1.xml') qs.query("B") ``` The stencil also provides a file called `parse_utils.py` that contains functions needed to read the XML and divide it into separate pages (you don't need to understand how these functions work unless you want to). For `QuerySlow`, the important function is `parse`, which takes the name of the wiki file (with many pages) to process and a function to use to process each page. The `process_page` method in `QuerySlow` is used as the argument to `parse`. In the `QuerySlow` class, `process_page` uses functions from `parse_utils.py` to extract the title, id, and text from the page, then checks whether the search term appears in the title or text. `process_page` adds the title of any page that contains the search term to a list called `matching_titles`. Bigger picture, `process_page` is an example of passing a function as an argument to customize the work of another function. `parse` is going to extract pages for you, but how you use that information depends on the design of your search engine. By putting your handling of a page in the `process_page` function, `parse` can do useful work for you, while leaving you in charge of what to do with the pages that it extracts. <section> ### Task 2-1: Reflect on the Design of `QuerySlow` Answer the following questions and submit in a document named `hw5.pdf`: 1. Why is `matching_titles` a field in the class, rather than just a local variable in the `query method`? What happens if we just make it a local variable? 2. Why is `search_term` a field in the class, rather than have `query` pass it to `process_page`? 3. Why might the designers of `process_page` not taken the search term as an input in the first place? 4. Assume that the user wants to run $Q$ queries over a wikifile with $P$ pages. Both of these can be large values (think about Google Search). What is the cost of running a single query? Write your answer in terms of $Q$ and $P$. </section> ## Towards a Better Search Engine Earlier in the handout, we mentioned that scale and prioritization were two features that matter in making a realistic search engine (we'll get to page updates later). **Addressing Scale:** In practice, search engines don't read every page afresh on every search attempt. Assume for the moment that the set of wiki pages doesn't change. In that case, we should be able to store some information as we process the pages that can get reused on subsequent searches. In other words, consecutive queries such as: ``` query("cats") query("parrots") query("banana") ``` would only require calling `process_page` once on each page (rather than once per query). This means that we will move the call to `parse` from `query` into the `QuerySeveral` constructor. Since we are parsing pages only once, rather than once per query, our search engine needs to save information on which words appear in which pages. Query will then use that information to look up results. What info do we need to store? Since queries search for documents containing words, here we will maintain a hashmap/dictionary from words to the pages that contain them: ```=python # dictionary with words as keys # the values are ??? word_freq_dict = {} ``` What should the values here be? One option would be a collection of pages (either page ids or titles). But remember that our other goal is prioritization of pages based on frequency of words. **Addressing Prioritization:** Ideally, we want to use this dictionary to track how often words appear on each page. This suggests the following design: ```=python # dictionary with words as keys # the values are dictionaries from page ids to counts word_freq_dict = {} ``` Specifically, if the word "cat" appears twice on page 124 and 3 times on page 465, this dictionary would contain: ```=python {"cat": {124: 2, 465: 3}} ``` We can then use the word frequencies to sort the matching pages, so that the pages with the **most** uses of the search term appear **first**. We can do this using Python's built-in [`sorted`](https://docs.python.org/3/library/functions.html#sorted) function. This dictionary is using page ids rather than titles to reference pages. It could go either way, but the ids are shorter and sometimes easier to work with. To let us work with titles instead, we will also maintain a second dictionary: ```=python # keys are page ids, values are page titles id_title_dict = {} ``` Both `word_freq_dict` and `id_title_dict` are provided in the stencil. #### Stemming and Stopping In practice, matching queries is challenging due to variations on words. Consider a query on the word "ink". Should that match the words "inks", "inking", or "stinks"? While `QuerySlow` accepted all of these, `QuerySeveral` is going to be a bit more careful and accept the first two but not the second. The key to doing this is to reduce words (both in queries and in web pages) to their core and storing counts of the core words instead. This process is called *stemming*. In addition, search engines don't bother to index extremely common words that don't contribute depth of meaning, such as "the" or "and". These are often referred to as *stop words*. In the stencil code, we have included both of these functionalities in `parse_utils.stem_and_stop()`, which uses Python-provided libraries to reduce a given word to its stem, as well as check if it's a stop word. Your code should only need to store and lookup word stems that are not stop words. <section> ### Task 2-2: Finish `QuerySeveral` Finish the `QuerySeveral` class. Comments in the stencil tell you what needs to be edited and where. You may NOT modify any of the already-existing code in `parse_utils.py`, except to fill in the locations marked by comments. You may add additional helper functions. Note that this should not involve many lines of code, once you understand how to make use of the hashmaps. :::warning There is **no required test suite** for Part 2 (the querier)! We give you `test_query.py`, which you do not have to submit, to show you how to run the querier and give you a place to write tests, if this helps with your implementation. ::: </section>  ## Part 3: Contrasting Two Moments in Time Each of BBS groups and Google search arose from significant technological developments (home computers and connecting them with phone calls for BBS, large-scale storage and processing capacity for Google Search). Each also resulted in new cultural experiences of information sharing and online community. As technologists, we have a responsibility to reflect on how these different approaches to organizing information online might affect users. Consider a "community" of people trying to find each other and share information online (this community could be an identity-based group, an interest group, a religious group, etc -- what matters is that they have specialized interests and a desire to find each other and share information online). For each of the two approaches, answer the following questions (say by creating a table like the one below or by using a bullet list for each question) in `hw5.pdf`. A sentence or two for each cell will suffice. We're looking for answers to have a connection to the corresponding system, in ways that highlights the differences between the two systems. | Question | a phone-based BBS | Internet-Scale Search | | -------- | -------- | -------- | | Who identifies which information is relevant to the community? | | | | Who decides which information represents the community?| | | | What were the costs to run the community and who provided them? | | | Overall, what are the advantages and disadvantages of this form of organizing information from the perspective of communities? | | ### If you found this history interesting ... * Check out [Black Software](https://global.oup.com/academic/product/black-software-9780190863845?cc=us&lang=en&) for a more detailed history of Black online communities and how they flourished and faltered under these changes * Check out the [cultural history of the internet course](https://internet.medialities.org/syllabus/week-3/) at Johns Hopkins University * Look for courses elsewhere at Brown that talk about cultural history (these show up in Literary Arts, Modern Culture and Media, Science and Technology Studies, and other departments) # Peer Review For this assignment, you have some flexibility in your timing of planning and peer review. Reviews will start being assigned on **Tues, April 8 at 11:59pm**. Submitting earlier will mean more time to review plans from other peers. <span style="color: #ff0000">**Wed, April 9 @ 11:59:00 pm**</span> is the latest you can submit plans (hard deadline will be enforced). Thus, you can take up to an extra day to focus on your plan, but do note that you will not be able to see/review other plans until your plan has been submitted to Peerceptiv. All reviews due by **<span style="color: #ff0000">Fri, April 11 @ 11:59pm. </span>**   Due to limitations of the Peerceptiv system, <span style="color: #ff0000">both review deadlines are **hard deadlines**, no late days!</span>. We have no way to grant extension on this. To ensure that you and your peers get feedback, please be sure to submit on time!!! After receiving your reviews, you have until the assignment deadline **Wed, April 16 at 11:59pm** to submit your peer review reflections on Peerceptiv, using the same link below. #### Submission links - [Plan submission](https://app.peerceptiv.com/course/60daf3a6-a765-4c09-aa06-f344588f04c5/assignment/bb7f25e3-eaf8-4768-ba3d-577de4ca388e/dashboard) # **Handing In** You will submit your initial design file (`data-design.pdf`) to Peerceptiv. You should submit the remaining files to Gradescope using the **Homework 5: Implementation** assignment: - `data-design.pdf` (no need to modify from its original version) - `hw5.pdf` - `bbs.py` - `file_utils.py` - `parse_utils.py` - `query_slow.py` - `query_several.py` - `test_bbs.py` - **If you have any custom example wikis used in testing, please submit them as well!** # Grading As we near the end of the semester, we know you are juggling final assignments and deciding where to put your efforts. Those of you taking the course S/NC or not necessarily aiming for an A may have different goals for what you get out of this assignment. For this assignment, we're therefore being explicit about minimal versus full functionality expectations (you still pass the assignment at minimum functionality). | Component | Full points | Minimum Functionality | | -------- | -------- | -------- | | Message Limits (BBS)| BBS limited to 200 messages. Deleting messages frees up space for more messages. | Limit of 200 messages. Can skip `remove_msg`. | | QuerySeveral | Search results sorted from most to least occurrence of query term in the pages | Search results not sorted by word frequency Whether you do full or minimum functionality, we'll be looking at the following components in grading your work: 1. **Design** (15%) 2. **Engagement in Peer Review** (10%) 3. **Functionality** (35%) 4. **Testing** (20%) 5. **Resource Efficiency** (12%) 6. **Societal Analysis (Part 3)** (8%) The thoroughness of your testing and your functions' efficiency will be graded manually. For testing, think about which combinations or sequences of sitauations should be tested. Checking combinations of operations is the key, not simply having lots of tests. "Engagement in Peer Review" includes that you submitted designs and reviews and were constructive in giving your review feedback. *** _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out our_ [_anonymous feedback form_](https://forms.gle/2vjmmnSdvHnbKQtA9)_!_