Computer Science CSC263H St. George Campus
February 15, 2018 University of Toronto
Homework Assignment #4
Due: March 1, 2018, by 5:30 pm
• You must submit your assignment as a PDF file of a typed (not handwritten) document through the MarkUs system by logging in with your CDF account at:
https://markus.teach.cs.toronto.edu/csc263-2018-01
To work with one or two partners, you and your partner(s) must form a group on MarkUs.
• The PDF file that you submit must be clearly legible. To this end, we encourage you to learn and use the LATEX typesetting system, which is designed to produce high-quality documents that contain mathematical notation. You can use other typesetting systems if you prefer, but handwritten documents are not accepted.
• If this assignment is submitted by a group of two or three students, the PDF file that you submit should contain for each assignment question:
1. The name of the student who wrote the solution to this question, and
2. The name(s) of the student(s) who read this solution to verify its clarity and correctness.
• By virtue of submitting this assignment you (and your partners, if you have any) acknowledge that you are aware of the homework collaboration policy that is stated in the csc263 course web page: http://www.cs.toronto.edu/~sam/teaching/263/#HomeworkCollaboration.
• For any question, you may use data structures and algorithms previously described in class, or in prerequisites of this course, without describing them. You may also use any result that we covered in class, or is in the assigned sections of the o cial course textbook, by referring to it.
• Unless we explicitly state otherwise, you should justify your answers. Your paper will be marked based on the correctness and completeness of your answers, and the clarity, precision, and concise- ness of your presentation.
• Your submission should be no more than 2.5 pages long in a 10pt font.
1
Question 1. (1 marks) Consider the sorting algorithm given by the pseudocode below. It takes an array A[1 . . n] of size n, and outputs A with its elements in sorted (non-decreasing) order.
1 2 3 4 5
fori=2ton j=i 1
whileA[j+1]