CSC111 Winter 2023 Assignment 1: Linked Lists and Blockchain
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSC111 Winter 2023 Assignment 1: Linked Lists and Blockchain
|
|
In the first two weeks of this course, you learned about linked lists, a node-based implementation of the List abstract data type. On this assignment, you’ll apply what you know about linked lists in two differen ways. In Part 1, you’ll complete a code correctness and debugging exercise, similar to past analysis you’v done in CSC110. In Part 2, you’ll explore one conceptual application of linked lists to a popular and nove area of computing: blockchain and cryptocurrencies.
Logistics
Due date: Wednesday, February 1 before 12pm noon Eastern Time.
We are using grace credits to allow you to submit your work up to 30 hours after the due date. Please review the Policies and Guidelines: Assignments page ( module_item_id=4243599) carefully!
This assignment must be done individually.
You will submit your assignment solutions on MarkUs (see Submission instructions at the end of this handout).
Starter files
To obtain the starter files for this assignment:
1. Login to MarkUs (https://markus.teach.cs.toronto.edu/2023-01) and go to CSC111.
2. Under the list of assignments, click on Assignment 1.
3. On the assignment page, click on the Download Starter Files button (near the bottom of the page). This will download a zip file to your computer.
4. Extract the contents of this zip file into your csc111/assignments/ folder.
5. You should see a new a1 folder that contains the assignment’s starter files!
You can then see these files in your PyCharm csc111 project, and also upload the a1.tex file to Overle to complete your written work.
General instructions
This assignment contains a mixture of both written and programming questions. All of your written wor should be completed in the a1.tex starter file using the LaTeX typesetting language. You went through the process of getting started with LaTeX in the Software Installation Guide ( module_item_id=1346385), but for a quick start we recommend using the online platform Overleaf () for LaTeX. Overleaf also provides many tutorials (https://www.overleaf.com/learn/latex/Learn_LaTeX_in_30_minutes) to help you get started with
LaTeX.
|
Tip: See this video tutorial (https://www.overleaf.com/learn/how- to/How_to_upload_files_to_a_new_project) for instructions on how to upload a .tex file to Overleaf. |
|
Your programming work should be completed in the different starter files provided (each part has its ow starter file). We have provided code at the bottom of each file for running doctest examples and PythonT on each file. We are not grading doctests on this assignment, but encourage you to add some as a way to understand and test each function we’ve asked you to complete. We are using PythonTA to grade your work, so please run that on every Python file you submit using the code we’ve provided. Part 1: Linked List Debugging Exercise In the starter file a1_part1.py, we have provided our linked list implementation from lecture and one additional method that David implemented: LinkedList.swap_first_and_last. |
|
class LinkedList: def swap_first_and_last(self) -> None: " " "Mutate this linked list by swapping the first and last items. Do nothing if there are fewer than two items in this linked list. " " "
while curr.next is not None: curr = curr.next # After the loop ends, curr is the last node in the linked list. assert curr.next is None
# Swap the first node and the last node using parallel assignment self._first, curr = curr, self._first |
Unfortunately (for David), Mario points out that there are at least two different errors in the implementation of LinkedList.swap_first_and_last.
Your task is the following:
1. Identify one error in the given implementation.
a. In a1.tex, explain what the error is. (Do not just explain how to fix it.)
b. In a1_part1.py, fill in the test_swap_first_and_last_error1 test case to illustrate th error.
Note: the test case should show the correct expected behaviour of the function. But the test case should not pass, either because an assertion fails, or because an error is raised.
2. Repeat Question 1, but for a second error in the given implementation. Write your explanation o the error in a1.tex and fill in the test_swap_first_and_last_error2.
Note the errors you identify in Questions 1 and 2 must be logically distinct, meaning that even if yo fix the error you identified in Question 1, the test case you defined for Question 2 should still fail, and vice versa.
3. a. In a1_part1.py define a third test case test_swap_first_and_last_no_error, which passes despite the errors you identified in Questions 1 and 2.
b. In a1.tex, explain why the test case you defined in part (a) avoids the two errors you identified.
4. Finally, fix the errors you identified in Questions 1 and 2 (as well as any additional errors) so that LinkedList.swap_first_and_last is implemented correctly. You may do this either by updating node items or by modifying the next attributes.
After you complete this question, the tests you wrote in Questions 1 and 2 should pass, in addition the test you wrote in Question 3.
Note: you can always refer to the code above for the original incorrect implementation.
Part 2: Blockchain and Cryptocurrencies
For the rest of this assignment, we’ll learn about one application of linked lists: to blockchains and cryptocurrencies like bitcoin. To provide context for this part of the assignment, we’ll imagine that we want to create a new cryptocurrency called Titancoin, or TC for short. For our cryptocurrency system, we’ll need a way to keep track of transactions in the system (like David paying Mario 10 TC) to both validate transactions and prevent tampering. We’ll also learn about how to give people the ability to create new TC by spending computational resources in a process called Titancoin mining.
Part (a): Transactions and Ledgers
To start, we’ll focus on using a linked list to record financial transactions between parties. Read the following text, and then complete the tasks below it.
Transactions and ledgers
In our simple cryptocurrency, there are two types of transactions that people can make:
transfer: one person sends some amount of currency to another person
For example, “David sends Mario 10 TC”
mining: one person creates a new amount currency
For example, “David mines 5 new TC”
A ledger is a sequence of transactions, stored in chronological order (i.e., the order they occurred). For example, a ledger might contain the sequence of transactions:
|
1. David mines 5 TC 2. Mario mines 8 TC 3. David transfers 2 TC to Mario 4. David mines 3 TC Additionally, each ledger keeps track |
2023-01-31