Homework 5

Goal: In Modules 5 and 6 video-lectures, we discussed the linked list and hash table data structure. This homework assignment will combine both concepts to create a (heavily) modified Cache class.

General instructions:

•   The work in this assignment must be your own original work and be completed alone.

•   The instructor and course assistants are available on Teams and with office hours to answer any questions you may have. You may also share testing code on Teams.

•   A doctest is provided to ensure basic functionality and may not be representative of the full range of test cases we will be checking. Further testing is your responsibility.

•   Debugging code is also your responsibility.

•   You may submit more than once before the deadline; only the latest submission will be graded.

•   Remove all testing code, code that produces syntax errors and any input() calls before you submit your file

Assignment-specific instructions:

•   Download the starter code file from Canvas. Do not change the function names or given starter code in your script.

•   Each class has different requirements, read them carefully and ask questions if you need clarification. No credit is given for code that does not follow directions.

•   This assignment includes multiple methods interacting with each other over the course of execution. You will need to use the tools described in module 2 for debugging.

•   Value-returning methods must return the output, not print it. Code will not receive credit if you use print to display the output

•   Do not change the string formats given or use the output of __str__/__repr__ in any of the operations you were asked to complete.

•   The doctest contains  in several lines. This line does not need to show up in your code, it simply represents the use of \n in the legible representations of the objects. In your output. it should show just a blank line

•   Execute the entire doctest only when ready to test out all your code. For debugging, it is best to perform each call in the Python shell.

•   If you are unable to complete a method, use the pass statement to avoid syntax errors

Submission format:

•   Submit your code in a file named HW5.py to Gradescope before the due date.

Section 1: What is a Cache? What are we making?

A computer cache is a part of your computer that holds data. It can be accessed very quickly but cannot hold as much information as your main memory.

Most caches on a computer are split into different levels. Your computer will typically look for data starting at the top level (L1) and work its way down the different levels. The most frequently used information is kept in L1 cache because it’s the fastest and the first level it will check.

The implementation of the cache for this project will be very simplified and would ignore some of the features of a cache you might find online – so make sure to read this assignment document carefully.

In our implementation, we will have three different levels of cache (L1, L2, L3). The overall cache structure will be implemented as a hash table using separate chaining for collision resolution, with each individual level implemented as a linked list. Content is put into different levels based on one of the content’s attributes.

Visualization of the Cache, CacheLists, and ContentItems:

Cache Hash Table

Section 2: The ContentItem and Node classes

The ContentItem class holds a piece of content and is described below. All methods have been implemented for you except __hash__. Do not modify the given code.

Attributes

Special methods

__hash__(self) (5 pts)

Returns the hash value for this ContentItem (used by the Cache class). For this assignment, let the hash value be equal to the sum of every ASCII value in the header, modulo 3. This is the special method for the built-in method hash(object), for example hash(‘hello’). Hint: the ord(c)method could be helpful here.

The Node class has been implemented for you and is described below. Do not modify the given code.

Attributes

Special methods