FIT2004 - 2020 Sem 2 (Australia) PDF

Preview

Summary

2020 Semester Two (November-December 2020)Examination PeriodFaculty of Information TechnologyEXAM CODES: FITTITLE OF PAPER: Algorithms and data structuresEXAM DURATION: 2 hours 10 minsRulesDuring an exam, you must not have in your possession any item/material that has not been authorised for your ex...

Description

2020 Semester Two (November-December 2020) Examination Period Faculty of Information Technology

Rules

Page 1 of 23

nstructions

Page 2 of 23

Instructions

Please attempt as many questions as possible; each page is composed of questions from the same topic. Read each question carefully. The marks associated with a question is not an indicator of the question difficulty or solution length. For algorithms and psuedocode questions, you are allowed to use either: 1. Structured indented text structure. 2. Numbered list. Best wishes and all the best!

Page 3 of 23

Correctness State a useful invariant for odd_prod. Use that invariant to prove that odd_prod calculates the product of all odd numbers in L.

5

Note that the empty product (i.e. multiplying no numbers together) is 1. def odd_prod(L[1...n]): prod = 1 i = 1 while i < len(L) if L[i] % 2 == 1: prod *= L[i] i += 1 return prod

Page 4 of 23

Complexity and Recurrence Relation Consider the algorithm for division by subtraction given below (assume that both inputs are always positive integers).

2

Def DivBySub(number, divisor) q = 0 r = number while r >= divisor q += 1 r -= divisor return q, r

What is the big-O time complexity of this algorithm? Note that we do not want the best or worst case complexity, but rather an expression for the exact complexity.

Consider the following pseudocode for three-way merge sort. Which of the recurrences is an expression for the time complexity of this algorithm?

2

Note that merge() is a function which takes as input three sorted lists, and returns a single sorted containing all the elements from each of the inputs, and runs in linear time. Def merge_sort(L[1..n]): if len(L)...