Algorithms 1 - Ticks
- Tick 1: bottom-up mergesort (lecture 3 / section 2.9) — due Mon 6 Feb 2023
- Tick 2: Huffman coding (lecture 7 / section 3.2.2) — due Mon 20 Feb 2023
Please submit your answers to the Moodle submission server, in Python only (submit genuine .py files, not Jupiter notebooks). The instructions for each tick explain what files to submit.
There are also optional starred ticks, so you can challenge yourself further. These carry no course credit: only for your learning and satisfaction. Again, submit your code to the Moodle submission server, in Python only. Ensure your code for the starred ticks passes pycodestyle with no warnings.
There is also a Q&A forum on Moodle for any questions about the ticks.
Assessment
The required ticks form part of your final grade for the year, as per the departmental marking scheme. We expect that nearly all students will complete all their ticks. You must pass the Moodle tester by the deadline listed above. If you have a good reason for not being able to complete the tick on time, please read the Guidance on deadlines page carefully, noting the typical penalties, and follow the process described therein.
All candidates have a non-zero probability of being selected for a one-on-one viva. This is your chance to show off the elegance of your coding, and to discuss your work interactively. We regret we can't offer this to all students. Each of the following activities will increase your probability of being selected, though none will bring it to 1:
- explicitly volunteer on Moodle
- ensure your code passes pycodestyle with no warnings (this is totally optional for the regular ticks, but required for the starred ticks).
- do the starred version of the tick
Details of who has been selected will be provided a few days after each tick's deadline.
Plagiarism
Ticks are offered to you (at substantial preparation effort) in the belief that doing them will make you a better computer scientist. This only happens if you do them yourself. In my personal opinion, they ought to be optional and not associated with course credit: you should do them just because you want to do them! However, in 2022-23 we asked the students and a majority of those who responded indicated that they wanted ticks to continue to be mandatory, because otherwise other things would take priority and they would end up not doing them. So be it. But then please don't cheat. What would be the point of demanding to be obliged to do the work, and then not doing it yourself?
You are welcome to discuss the problems with your fellow students, or with your supervisor, but you MUST implement your code yourself and you MUST be able to explain how it works. Note that the "donor" of copied code will also be considered complicit in plagiarism. If you want the ticks to be mandatory, please do them honestly, doing the actual programming by yourself.
Acknowledgements
These programming problems were created by Frank Stajano, who wrote initial solutions and unit tests for them. They were tested by Victor Zhao, Dimitrije Erdeljan and Lucian Carata and especially Damon Wischik, whose feedback led to many improvements. They were made to run on Moodle by Victor Zhao with extensive help from Damon Wischik. Frank Stajano is extremely grateful to all of them, without whom none of this would work, but assumes responsibility for any remaining infelicities.
Q&A
I have completed the tick and on submission it tells me the tests have passed yet it only gives me 0.5/1.0. Why?
Passing all the tests is only part of the requirements, hence the 0.5. The other half of the mark is awarded after vivas and plagiarism checks.
It tells me I passed all the tests but it mentions some error E302 about there only being 1 out of 2 blank lines. What does it mean?
It's part of the output of pycodestyle, which is a tool that checks compliance with the source code style conventions of PEP8. For the unstarred tick, compliance with PEP8 is not required, so this is just for your information (but you are welcome to clean up your code if you feel so inclined). For the starred tick, instead, compliance is mandatory.
I am trying to implement the lddr method but I think it requires using some memory space in the case of overlapping blocks in the same array, however since it is static it can't access the s array that is meant to be used for scratch space. Is there some mistake in my thinking? Is there a way of doing it without having to create a new array to store the overlapped values?
It is possible to implement lddr without using any extra scratch space, even for overlapping blocks. Think of the options you have in terms of where to start and which direction to go (there’s a reason why there were both a LDIR and a LDDR instruction in Z80 assembly, with I and R standing for increment and decrement respectively). I hope this gives you the right hint. Try moving a block of adjacent marbles / pebbles / buttons... to an overlapping region of the same size, without copying anything out of the array.