Homework 5 (Spring 2026) - 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 2026) ### Key dates #### Peer review phase  <table> <thead> <tr> <th>Track</th> <th>Plans Due</th> <th>Reviews Due</th> <th>Reflection Due</th> <th>Notes</th> </tr> </thead> <tbody> <tr> <td><strong>Early</strong></td> <td><strong>Tue, April 7</strong></td> <td><strong>Thu, April 9</strong></td> <td><strong>Mon, April 20</strong></td> <td>If you miss a deadline, please submit to the regular submission instead.</td> </tr> <tr> <td><strong>Regular</strong></td> <td><strong>Fri, April 10</strong></td> <td><span style="color:#ff0000;"><strong>Mon, April 13*</strong></span></td> <td><strong>Mon, April 20</strong></td> <td><span style="color:#ff0000;"><strong>*: Hard deadline (no late submissions!)</strong></span></td> </tr> </tbody> </table> <em>Note:</em> You cannot view/review other plans until you submit your own plan. Submit early if you want to start reviews early. #### Final submission <table> <thead> <tr> <th>Item</th> <th>Date</th> <th>Notes</th> </tr> </thead> <tbody> <tr> <td><strong>Final Code Submission</strong></td> <td><strong>Friday, April 17</strong></td> <td>Submit code + tests to Gradescope</td> </tr> <tr> <td><strong>Peer Review Reflections</strong></td> <td><strong>Monday, April 20</strong></td> <td>Complete reflection in Peerceptiv</td> </tr> </tbody> </table> :::success **Gearup**: For an overview of the project, check out the gearup from Fall 2024 by Nick. It'll put the project in context and describes how to start thinking about each component: - 🎥 [Gearup Recording](https://brown.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=58b72fed-1ec2-4236-a88b-b421010c0eb0) - 📝 [Gearup Notes](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** 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! ::: # Overview :::danger ⚠️ **Heads up**: We're still setting up the Gradescope submission for this assignment, so you will not find this assignment on Gradescope yet. Please refresh this page for updates--this message will disappear once Gradescope has been enabled. ::: 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 - Use Python libraries to process save and load data in 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 the profs 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/ALq4bjaQ)** 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. <section> ### Getting Debugging Help (Ed & Office Hours) :::info **Goal:** We'll help you learn to debug. We won't do line-by-line bug hunts or write/fix your code for you. ::: #### Ed Stem policy - Please use the template on EdStem - TAs will give **conceptual guidance and debugging strategy** - After some back-and-forth exchanges, we may suggest that you **come to hours** to talk through your design with us (we want to honor your design decisions!) #### Office Hours policy - Please be ready to **walk us through** the relevant code and where you think the issue is #### Scope of TA help - ✅ OK: Concepts, design choices under constraints, reading error messages, debugger usage, test design, clarifying handout language - ❌ Not OK: Hunting through entire codebases, writing your solution </section> # 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. Seeing these same ideas in new settings is a known strategy for learning 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). - This means that the summary must not include the message body. - 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. Now let's see this 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 ("read-eval-print loop", which is the kind of user-interface used in this project) 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 handout 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 subject or author # If term is "", print all messages # (Also return the summary as a string) def print_summary(term="") -> str: # . . . # Remove a message by id; assume id exists. Return None (but print as specified). def remove_msg(id_num: int): # . . . # 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 `remove_msg()` takes in an existing message ID in your system. If `find_print_msg()` is called on an ID that doesn't exist, it should return an empty string. - 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. *(Languages of the time didn't support these data structures. Today, a language might only support some data structures and not others. We want you to think about how you can get the core ideas of data structures if they aren't part of the system you are programming in).* - **Your program can have at most 10 global variables** in use at any one time. *(The variables mimic a component of computer hardware called a register. Access to data in a register is fast, while access to data in memory is slower, even in today's computers. When we write hardware-level code, we have to plan for having only a few slots for frequently-accessed data; limiting the number of variables exposes to this idea. If you take Compilers (CSCI 1260) at some point, you'll program against registers).* - You may not store whole messages, or summaries of messages, in **global** string variables. *(The size of data that can be stored in a register is limited. We don't want you to circumvent the variable limitations by cramming too much data into a string).* </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/1uFi3mgsVTll7Gwck_qyhR8SQ0pgYwpV9ZHki0BOHCng/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 CS300 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. *(Even today, within memory, data is stored in small chunks; 128 characters is a common size of a chunk)* 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 feedback that will help you later! ::: Your design plan submission is due **Thursday, 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. 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 -- processing strings The implementation involves being able to break down and create strings that are read from or written to files. Low-level string processing is tedious, and not the point of this assignment. Therefore: - you may use `str.split()`, `str.partition`, or `re` (regular expressions) to break a formatted string into parts. You can then access the parts by their index/position in the returned list or value. - you may **not** iterate over the list of strings that one of these functions returns. String helpers are limited to taking strings apart and putting them back together. - you may use `str.join` or string concatenation to assemble strings into a larger string - you may index and slice strings (e.g., `s[0]`, `s[0:5]`) - you may loop over characters in a string (e.g., `for ch in s:`) when processing a **single line** you already read from a file Why these constraints? One point of this assignment is to have you program without data structures, and iteration would mean that you have exposed an iterable data structure. We're letting you use some Python functions that happen to return indexable lists, but you aren't working with the list-ness of those returned values. ### Implementation notes -- working with files - **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. Similarly, you make not use `seek`. - 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! :::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! Use the helpers in `file_utils.py` instead. ::: - 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 ### Implementation notes: storing and updating data Here is a summary of how different operations store, load, and update data: - **connect(username)** In our BBS, "connecting" just tells your system who the current user is. It's likely that you won't need to write any files in this function - (In a real system, you'd also need to dial a phone number, maybe enter a password, etc., but we can skip that part 🙂 ) - **post_msg / remove_msg** These functions modify messages stored in your BBS. **Consider: based on your design, what file(s) or metadata should `post_msg/remove_msg` modify before returning?** There can be multiple ways to handle this: - When posting or deleting a message, you could modify any files immediately, inside this function - You could update some internal metadata, and then write everything to disk when `disconnect` is called  - **disconnect()** This is called when the user logs out. After this, the program may exit! If you have any changes to your metadata that haven't been saved to disk, save them here!!! - Note: the *current user* doesn't need to be saved. The user will be set again when the next user logs in! - **exit() (REPL quit)** This is a built-in Python function to end the program immediately, without calling any other functions. The REPL uses this to quit the program when prompted by the user. Since the program will quit after this, all the data you need to save should be saved beforehand! - **clean_reset()** **Testing-only.** Wipes everything the BBS created inside `disk/` (messages + metadata). `bbs_test.py` is set up to call this function before each test so that each test starts from a clean slate. You should also modify this to clear out any metadata and globals, to make sure all your tests run consistently!   </section> ## Background: files in python :::info We learned terminal file navigation in **[the matrices lab](https://docs.cs200.io/ms6ify-VR0uBxr9lJy0gOg)**! ::: :::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 [the matrices lab](https://docs.cs200.io/ms6ify-VR0uBxr9lJy0gOg). 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, a `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](#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. :::danger As you think about how to manage message IDs, remember that you are not allowed to convert a line/string into a list and iterate over it. You have to find a way to store and process IDs that does not require you to process the IDs as a list. ::: :::info **Heads up about the 128-character line limit:** If you store "which IDs are free" using a string-based encoding, remember that you can't fit 200 IDs' worth of markers on a *single line* in any encoding that uses 1+ characters per ID (e.g., `T/F`, `0/1`, or a repeated marker like `TFTF...`). Whatever encoding you choose, you'll need to **chunk** it across multiple lines/files so each line stays ≤128 characters. ::: </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: - Every test should have a description of what it does. This helps TAs locate your tests more effectively. If you do not have these descriptions, TAs will remove points. - 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/1N5sOUQjdxuUJEZtOgrBsIClgYE9O16zvJA5vntbEhLA/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 XML. 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 might the designers of `process_page` not taken the search term as an input in the first place? 3. 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. ### Task 3.1: Reflect on Information Sharing 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. Submitting earlier will mean more time to review plans from other peers. See the [Key Dates](#Key-dates) section for the deadlines for each component. Due to limitations of the Peerceptiv system, <span style="color: #ff0000">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!!! #### Submission links - [Early Deadline Plan submission](https://app.peerceptiv.com/course/22e09961-9339-4ac2-921f-cd9ef380f2b3/assignment/5e8a4750-40ea-46b5-8ae1-1d7734b1dfcb/dashboard) - [Normal Deadline Plan submission](https://app.peerceptiv.com/course/22e09961-9339-4ac2-921f-cd9ef380f2b3/assignment/578c2e1d-fd1a-48d0-9c4e-4c1f6b15946e/dashboard) # **Handing In** :::danger ⚠️ **Heads up**: We're still setting up the Gradescope submission for this assignment, so you will not find this assignment on Gradescope yet. Please refresh this page for updates--this message will disappear once Gradescope has been enabled. ::: You will submit your initial design file (`data-design.pdf`) to Peerceptiv. After completing this assignment, you should have added or made changes to the following files in your repository: - `bbs.py` - `file_utils.py` - `parse_utils.py` - `query_slow.py` - `query_several.py` - `test_bbs.py` - `data-design.pdf` (no need to modify from its original version) - `hw5.pdf` - **If you have any custom wikis used in testing, please submit these as well! **Adding your PDF files (and, custom wikis, if needed)**: your PDFs will be new files in your repository--to add them, copy the files into your repository and be sure to add them with `git add`. After pushing your code, you should see it on your github page! You will submit your work you should do the following (see the **[Gradescope submission guide](https://docs.cs200.io/gradescope-submission-guide)** for instructions): 1. Commit and push your code to your github repository. After pushing your code, you can check on github that all of the files you modified are present in your repository 2. Submit your code to the **Homework 5: Implementation** assignment on Gradescope. We'll use this submission to grade your code Once you have submitted to each Gradescope assignment, you should receive an email, more or less immediately, confirming your turn-in. # 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 situations 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/eVKnVzRa1zG365zZA)_!_