nycomp

Hash Table (Collision Resolution) Practice

In the last session, we implemented a Hash Table, the backbone of which is the hash function.

An ideal hash function gives a unique location for each key. However, since the number of possible keys is much larger than the number of locations, some keys will inevitably hash to the same index location. When this happens, it is called a hash collision.

Collision Resolution (Open Addressing)

For this exercise, we will attempt collision resolution using Open Addressing. Refer to your notes if you would like to learn about the other collision resolution strategy, using Closed Addressing.

Some of the open addressing strategies include:

nycomp

Hash Table Practice

A Hash Table is implemented with a fixed-size array.

Reminder: A hash table does NOT do a linear search to locate the item! If you are looking to implement a linear search algorithm within the hash table, think twice!

With reference to the algorithm given in the notes, you are required to Implement a Hash Table class (in the hashtable.py file)

with the attributes:

• size - size of the hash table

nycomp

Performance profiling

Performance profiling refers to the measurement of the performance of code. Performance can be measured in a number of areas, such as memory use, latency, etc. In this exercise, we focus on measuring execution time.

Part 1: Measuring performance

We may think our code is fast, but how do we actually know?

We'll have to measure its performance.

nycomp

Instructions

The task is to read in subtitles from a subtitle file, and store them in an appropriate structure.

SRT files are plain-text files that contain subtitle information for movies. Each subtitle record consists of the following information, all as str type:

• a record number (in sequential order)
• the start time and end time of the subtitle record
• one or more lines of subtitle text

nycomp

Prerequisites: Python programming, Object-oriented programming, Linkedlist

888b     d888        d8888 8888888888P 8888888888      8888888b.  888     888 888b    888 888b    888 8888888888 8888888b.  
8888b   d8888       d88888       d88P  888             888   Y88b 888     888 8888b   888 8888b   888 888        888   Y88b 
88888b.d88888      d88P888      d88P   888             888    888 888     888 88888b  888 88888b  888 888        888    888 
888Y88888P888     d88P 888     d88P    8888888         888   d88P 888     888 888Y88b 888 888Y88b 888 8888888    888   d88P 
888 Y888P 888    d88P  888    d88P     888             8888888P"  888     888 888 Y88b888 888 Y88b888 888        8888888P"  
888  Y8P  888   d88P   888   d88P      888             888 T88b   888     888 888  Y88888 888  Y88888 888        888 T88b   
888   "   888  d8888888888  d88P       888             888  T88b  Y88b. .d88P 888   Y8888 888   Y8888 888        888  T88b  

nycomp

Modules for importing and exporting data

The process of converting an object to text data is known as serialisation.
The process of converting text data to an object is known as deserialisation.

In Python, we can manually serialise or deserialise data using IOStream objects.
The simplest way to get an IOStream object is to use the built-in open() function.

>>> f = open('test.txt', 'w')

>>> type(f)

nycomp

This exercise contains the following files:

• GuessMyNumber.md: This file
• protocol.md: A description of the communication protocol used for GuessMyNumber, a number-guessing game
• guessing.py: Module with functions used to implement a number-guessing game. Used by server.py, not needed for client code
• server.py: The server implementation.

Your task

In main.py, write the client code within the client() function to interact with the server successfully and enable the user to play GuessMyNumber.

nycomp

Socket Programming

Socket programming allows developers to build these kinds of network applications by using programming languages like Python, C, or Java to create, connect, and manage sockets. A network socket is an endpoint for sending or receiving data across a computer network, and it forms the foundation of communication in the TCP/IP stack. When two devices want to communicate, each creates a socket—one to listen for incoming connections (server) and one to initiate the connection (client).

Each socket is defined by a combination of an IP address and a port number. Using sockets, programs can send and receive streams of data over the internet or a local network, whether it's for browsing the web, sending emails, or chatting in real time.

Instructions

1. Write client code in client().
2. Your client should:

nycomp

"""Creating a Digital Signature

<IN SYLLABUS>
A digital signature verifies the authenticity of a digital message.

## Creating a digital signature
1. The message is hashed (using a cryptographic hash function).
2. The message hash is encrypted with the sender’s private key to produce a digital signature.

## Sending a digitally signed message

nycomp

"""Let's get our very own digital certificate!
We could create a self-signed certificate, which means there is no
cert authority (CA), but that wouldn't be trustworthy. It's only useful for
sending encrypted data between machines we own (since we trust our own cert).
Unfortunately, most cert authorities (CA) charge a fee for a certificate (and
the service of verifying it, and making your public key available).
There is one that doesn't: [LetsEncrypt](https://letsencrypt.org/). Let's
request a certificate from them.
LetsEncrypt uses the Automatic Certificate Management Environment (ACME)
protocol to automate the process, which is nice because it means we can write