README.md 4.07 KB
Newer Older
1 2
# Homework 1. Introduction to Python and File I/O
This homework assignment is meant to be an introduction to Python programming and introduces some basic concepts of encoding and decoding. 
Sanjay Krishnan committed
3

4
Due Date: *Friday April 17, 2020 11:59 pm*
Sanjay Krishnan committed
5

6 7
## Initial Setup
These initial setup instructions assume you've done ``hw0``. Before you start an assingment you should sync your cloned repository with the online one:
Sanjay Krishnan committed
8
```
9
$ cd cmsc13600-materials
Sanjay Krishnan committed
10 11
$ git pull
```
12

13
Copy the folder ``hw1`` to your newly cloned submission repository. Enter that repository from the command line and enter the copied ``hw1`` folder. In this homework assignment, you will only modify ``encoding.py``. Once you are done, you must add 'encoding.py' to git:
Sanjay Krishnan committed
14
```
15
$ git add encoding.py 
Sanjay Krishnan committed
16
```
17
After adding your files, to submit your code you must run:
Sanjay Krishnan committed
18
```
19 20
$ git commit -m"My submission"
$ git push
Sanjay Krishnan committed
21
```
22
We will NOT grade any code that is not added, committed, and pushed to your submission repository. You can confirm your submission by visiting the web interface[https://mit.cs.uchicago.edu/cmsc13600-spr-20/skr]
Sanjay Krishnan committed
23

24 25 26 27 28 29 30
## Delta Encoding
Delta encoding is a way of storing or transmitting data in the form of differences (deltas) between sequential data rather than complete files.
In this first assignment, you will implement a delta encoding module in python.
The module will:
* Load a file of integers
* Delta encode them
* Write back a file in binary form
Sanjay Krishnan committed
31

32
The instructions in this assignment are purposefully incomplete for you to read Python's API and to understand how the different functions work. All of the necessary parts that you need to write are marked with *TODO*.
Sanjay Krishnan committed
33

34 35
## TODO 1. Loading the data file
In `encoding.py`, your first task is to write `load_orig_file`. This function reads from a specified filename and returns a list of integers in the file. You may assume the file is formatted like ``data.txt`` provided with the code, where each line contains a single integer number. The input of this function is a filename and the output is a list of numbers. If the file does not exist you must raise an exception.
Sanjay Krishnan committed
36

37 38
## TODO 2. Compute the basic encoding
In `encoding.py`, your next task is to write `delta_encoding`. This function takes a list of numbers and computes the delta encoding. The delta encoding encodes the list in terms of successive differences from the previous element. The first element is kept as is in the encoding. 
Sanjay Krishnan committed
39

40 41 42 43 44 45
For example:
```
> data = [1,3,4,3]
> enc = delta_encoding(data)
1,2,1,-1
```
46

47 48 49 50 51 52 53
Or, 
```
> data = [1,0,6,1]
> enc = delta_encoding(data)
1,-1,6,-5
```
Your job is to write a function that computes this encoding. Pay close attention to how python passes around references and where you make copies of lists v.s. modify a list in place.
54

55 56
## TODO 3. Integer Shifting
When we write this data to a file, we will want to represent each encoded value as an unsigned short integer (1 single byte of data). To do so, we have to "shift" all of the values upwards so there are no negatives. You will write a function `shift` that adds a pre-specified offset to each value. 
57

58 59 60 61 62 63
## TODO 4. Write Encoding
Now, we are ready to write the encoded data to disk. In the function `write_encoding`, you will do the following steps:
* Open the specified filename in the function arguments for writing
* Convert the encoded list of numbers into a bytearray 
* Write the bytearray to the file
* Close the file
64

65
Reading from such a file is a little tricky, so we've provided that function for you.
Sanjay Krishnan committed
66

67 68
## TODO 5. Delta Decoding
Finally, you will write a function that takes a delta encoded list and recovers the original data. This should do the opposite of what you did before. Don't forget to unshift the data when you are testing!
69

70 71 72 73 74 75 76 77 78 79 80 81 82
For example:
```
> enc = [1,2,1,-1]
> data = delta_decoding(enc)
1,3,4,3
```

Or, 
```
> data = [1,-1,6,-5]
> data = delta_decoding(enc)
1,0,6,1
```
83 84

## Testing
85
We've provided a sample dataset ``data.txt`` which can be used to test your code as well as an autograder script `autograder.py` which runs a bunch of interesting tests. The autograder is not comprehensive but it is a good start. It's up to you to figure out what the test do and why they work.