# COMP6714-Project 1
### Submission Deadline for the Project is 23:59:59 PM, on **25 Sep, 2017**
This ipython notebook illustrates the requirements for **COMP6714 Project-1**.
Instructions:
1. You need to implement your code in **`submission.py`** file, provided along with this notebook.
2. For all questions, your codes in the file **`submission.py`** need to output your results according to corresponding format specified in **`Proj1-spec.ipynb`**.
3. We will not consider any output printed out on the screen. All results should be returned in appropriate data structures return by corresponding functions.
4. This Project is not designed to be a full-fledged software program, so we will not evaluate it deliberately using any invalid inputs.
5. You are **not allowed** to change the names of the functions to be submitted in **`submission.py`**.
6. If you choose to skip a question, leave the corresponding function body in the file **submission.py** as it is (i.e., keep the **`pass`** line), otherwise it will affect your marks for other questions.
7. You are allowed to add other functions and import modules (which you may have to in this project), but you are **not allowed to define global variables**, i.e., **only functions are allowed** in **`submission.py`**. Also be careful not to import unnecessary modules, as it may lead to unexpected errors.
8. You are allowed to submit as many times as you want before the deadline, but **ONLY the latest version will be kept and marked**.
9. For your convenience, we will process your codes submitted before the **Deadline** using a sample dataset, you should not consider these results as your final grades.
10. For **Final Grades** we will be using a different test data, so your final scores may vary. We will also check the source code to **ensure** the algorithms specified in the project are implemented.
# Question 0: An example (0 point)
We illustrate the steps for completing the **project** notebook and prepare **`submission.py`** by solving the `Question 0`. In this example question, you are required to implement a function that takes two integer arguments `a` and `b`, and output their sum.
You will be provided with the definition of the function, as given below:
# Question 1: List Intersection using Galloping Search (35 point)
You need to implement a function named **`gallop_to`** using the galloping search algorithm. The function will be used to help the intersection of inverted lists. You may refer to **Note 1** on the course webpage for detailed information about this algorithm.
## Intersection Algorithm using `gallop_to()`
The `gallop_to()` function can be used in the intersection algorithm, *i.e.*, `intersection_galloping`, and it can quickly skip over the list to reposition the cursor.
# Question 2: Logarithmic Merge (35 point)
In this question, we simulate the implementation of (binary) Logarithmic_Merge for Index Merging, given in **L4-slides (36-37)**.
You are required to implement the Logarithmic Megre function: **`Logarithmic_merge(index, cut_off, buffer_size)`**.
The function takes 3 parameters as input,i.e., *(i)* **index**, *(ii)* **cut_off**, and *(iii)* **buffer_size**.
1. First parameter, **index**, represents the live streaming index, we simulate the **index** using a list of unordered integers.
2. Second parameter, **cut_off**, is the cut_off point for the streaming **index**, it is illustrated in the example below.
3. Third parameter, **buffer_size**, represents the maximum size of your memory buffer. When **index** is **greater than or equal** to the **buffer_size**, we write down the **index** in a file.
##### Note: You are not supposed to actually write down your index in the file, you will be simulating the index writing part by adding the index to a list.
#### Example for cut_off:
index = [15, 46, 19, 93, 73, 64, 33, 80, 73, 26, 22, **-77-**, 27, …..]
Assume that you have access to live-streaming data, which is being populated in your list named: **index**. The parameter, **cut_off** defines a threshold for the **index**. For-example, **cut_off = 12** will restrict the function:**`Logarithmic_merge(index, cut_off, buffer_size)`** to use **top 12** values, i.e., it will only consider values upto and including the value **77**.
#### Specifications:
Your inputs will be the *(i)* **index**, i.e., unsorted list of integers, *(ii)* **cut_off**, *i.e.,* the cut-off point, and *(iii)* **buffer_size**, *i.e.,* the maximum size of index that can be kept in memory.
Your output should be a list of sub-lists, where each sub-list stores intermediate result of logarithmic merge. First sub-list will store the value for Z0, the second sub-list will store the value of L0, and the subsequent sub-lists will store values for L1, L2, L3 and so on…
##### Note: Don’t remove empty sub-lists from your final result. It will effect your evaluation.
#### Example:
input: (index, cut_off, buffer_size), e.g., ([15, 46, 19, 93, 73, 64, 33, 80, 73, 26, 22, 77, 27], 10, 3)
##### output: List of sub-lists storing all the intermediate results, and the final result, e.g., [[26], [33, 73, 80], [15, 19, 46, 64, 73, 93]].
**Note**:<br>
1. Z0 should be added at the start of the final list, followed by L0, L1, L3, and so on… <br>
2. In the example output, Z0 = [26], L0 = [33, 73, 80], L1 = [15, 19, 46, 64, 73, 93] <br>
3. **index** within a sub-list should be sorted. <br>
# Question 3: Decoders for Gamma, Delta, and Rice codes (30 point)
In this part you will implement decoders for Gamma, Delta, and Rice codes.
#### Specifications:
For Gamma, and Delta decoders, your input will be a string of bits (0s or 1s) without any space. Your output for Gamma, and Delta decoders should be a list of integers.
For Rice decoder, input constitutes of the *(i)* code, i.e., a string of bits (0s or 1s) without any space, and *(ii)* an integer representing the value of b. Here b = 2^k. Output of Rice decoder should be a list of integers.
##### Note, for Rice Decoder, in contrast to the information provided in (L5, slide57), we assume the input of the decoder is comig from q = [x]/b, and r = (x) – (q.b).
#### (i) Examples for Gamma and Delta:
##### (a) input: (String x), e.g., (“1111111100000000011111111000001001”)
##### (b) output: list of numbers, e.g., [256, 265]
#### (ii) Example for Rice Decoder:
##### (a) input: (String x , int b) e.g., (“11110101111011”,4)
##### (b) output: list of numbers, e.g., [18, 19]