Comp 251: Proof Activity Solved

This assessment is based on the concepts of “Crowdsourcing learning” and “Learning by giving feedback”. In particular, the Comp251 community (composed by you) will align around the shared goal of learning about proofs and “prove” that proofs are fun and useful :). In this assessment, we will work as a learning community to generate a corpus of information that will allow the Comp251 students to understand and value the importance of mathematical proofs in algorithms. Each student, will perform the following four activities.

    1. Students submit their work.

    2. Students review their peers’ submissions.

    3. Students review their own submission.

    4. Students reflect on their received feedback.

We will use the software Eduflow to facilitate this peer assessment. Please notice that you will be automatically enrolled when you first access Eduflow from the Content tool in MyCourses (please look for the icon in Content/Information/EduFlow). The software is based on the hypoth-esis that student exposure to their peers’ work nurtures critical reflection, as they consider what they did well and how they can improve. Reviewers learn to give constructive and actionable feedback, while recipients of peer review obtain additional, personalized feedback from another perspective.

Part 1. Students submit their work - Due date: March 15th  (11:59:59pm).

Initially, two proofs dealing with the correctness and efficiency of an algorithm will be randomly assigned to each student - one of each category. You can check this assignation in MyCourses. For each proof the student will have to write out five exercises, all contained in one pdf document (using the software latex) and several java files. We recommend using the free, online service Overleaf to write the report, for which a template will be provided. The student may duplicate and modify the template for their submission. The template is in the form of a sample report, which is available on myCourses. The following five exercises should be contained in the report for each proof:

    1. Report the proof.

Here, the student will need to use mathematical notation to report the proof. The student needs to report at least one reference from where the proof was obtained. Please fit the report in less than one page.

    2. Summary of the proof.

Here, the student needs to summarize the proof. The student is free to select the methodology (e.g., text, images, draws, flows, etc) to present the summary; however, the student can not use a formal mathematical notation in this point. Please fit the summary in less than half of a page (otherwise it will not be a summary :P ).

    3. Report a java algorithm on which the proof is used and/or applied.

Here, the student needs to provide a working java algorithm, related to the proof, in one or more java files (for classes, functions and a main method). The student should try to write
as much of their own Java code as possible, however standard chunks of code may be used when referenced. The student needs to comment the code in their own words, highlighting important information about the code. Any relevant figures, pictures, code snippets, etc should be included in the report.

    4. Explain how/where the proof is used in the algorithm.

Here, for each proof the student needs to relate the proof to the java algorithm by testing aspects of their algorithm in the main method and reporting the results. Any relevant figures, pictures, code snippets, etc should be included in the report.

        ◦ For the asymptotic complexity proof:

Here, the student needs to generate a plot reporting the algorithm run time (the algo-rithm reported in the previous step). In order to generate the plot, the student needs to modify the size of the input and measure the time spent by the algorithm for each input size. The student needs also to discuss if the generated plot (i.e., practice be-haviour) agrees with the theoretical behaviour reported by the proof. We recommend using XChart, a free, easy to use java plotting library. There is an example of how to use XChart in the java code of the sample activity provided. The student can also use any graphing software they choose.

        ◦ For the correctness proof:

Here, the student needs to demonstrate the algorithm (the one reported in the previous step) works correctly on at least three different instances of the problem. In particular, the student needs to run the code on 2 edge (or limit) cases and 1 general case. The student needs to briefly justify the choice of the cases. Also, the student should explain how the proof is used in the algorithm.

    5. Provide a real world example of where the algorithm is used.

Here, the student needs to report a real world application of the assigned proof (or imple-mented algorithm), with at least one reference. The student is free to select the methodology (e.g., text, images, draws, flows, etc) to present the application.

The student needs to submit the PDF file, generated by a tool like latex or Microsoft Word, and a zip file containing the java code in the “submit your work” section in Eduflow. Please notice that you can also submit here a video (of maximum 5 minutes) where you explain your submission. The idea of the (optional) video is that you will be able to provide more information about your submis-sion, which could increase your chances of getting better feedback from your peers, however it is not required. The due date to submit your report is March 15th (11:59:59pm). Please check this

link (https://help.eduflow.com/en/articles/4453207-submitting-your-work) for more in-formation about how to submit your work.

Part 2 (60 points). Students review their peers’ submissions. Due date: March 22nd

(11:59:59pm).

In this activity, each student will have the opportunity to review the submissions made by three of their peers. In particular, you are requested to review submissions from 3 of your peers made in the earlier submission activity. You will provide your feedback based on a standardised peer feedback rubric that we have created for you. This activity will be considered as completed, once you finish all the three required reviews. Please notice that the deadline to finish all the 3 reviews is on March 22nd (11:59:59pm).
Part 3 (10 points). Students review their own submission.  Due date: March 26th

(11:59:59pm).

In addition to having the opportunity to take part in three peer review sessions, you will have also to review your own work or submission. The main hypothesis here is that asking you to go through a process of reviewing your own work is beneficial for your learning process and leads to a deeper understanding of the studied topic. For this step, you will have to complete this self review activity by answering the questions in the feedback rubric that we have prepared for you.

Part 4 (30 points). Students reflect on their received feedback. Due date: March 31st

(11:59:59pm).

In this part of the assessment, you will have the opportunity to see, read, and reflect on the feedback you received from peers (i.e., the three students who marked your submission). You will complete this activity once you answer all the questions of the feedback reflection rubric that we have prepared for you. Please notice that this is the last activity of our assessment and it is due on March 31st (11:59:59pm).

What To Submit?

You have to submit one PDF file (generated by latex or Microsoft Word), one zip file containing your java code, and optionally one video explaining your submission.

Where To Submit?

You need to submit your report in Eduflow. Please note that you do not need to submit anything to myCourses.

When To Submit?

Please do not wait until the last minute to submit your assignment. You never know what could go wrong during the last moment. Please note that the deadlines dates are fundamental for the correct development of this assignment. This Eduflow assignment has more than one due date. There is a due date for submitting your report. There are two other due dates for grading the students who have been assigned to you (this will begin after the submission due date passed) and grade yourself. Lastly, after you have been graded by students you have the chance to rate the grade given to you and comment on the quality of the feedback you received from that student. Please grade your classmates fairly using kind comments. The rule should be to grade the assignments with the same quality that you want your assignment to be graded.

How will this assignment be graded?

Each student will receive an overall score out of 100 points for this assignment. The weight of each part is described below.
    • In Part 2, three peers will grade the student’s report, with each peer’s grade being out of 20 points. In this way, 60 points (3 × 20 points) come from Part 2.

    • Then, in Part 3, each student will grade their own report, out of 10 points.

    • Finally, in Part 4, the three reviews that the student made in Part 2 will each get scored out of 10 by the peers who wrote the three reports. For this reason, Part 4 is scored out of 30 points (3 × 10 points).