CS 430 – Fall 2022 Introduction to Algorithms - Sorting Algorithm
CS 430 – Fall 2022 INTRODUCTION TO ALGORITHMS HOMEWORK #1
DUE SEP. 12 (Monday, the end of day)
• Teamwork is NOT allowed.
• Submit the PDF version of the assignment to the Blackboard.
• Late submissions will be accepted through Sep. 15 with a credit deduction. • All solutions should be explained.
1. (5 points)
1a) Use pseudocode to specify a brute-force algorithm that determines when given as input a sequence of n positive integers whether there are two distinct terms of the sequence that have as sum a third term. The algorithm should loop through all triples of terms of the sequence, checking whether the sum of the first two terms equals the third. (2pts)
1b) Give a big-O estimate for the complexity of the brute-force algorithm from part (a). (1pt)
1c) Devise a more efficient algorithm for solving the problem that first sorts the input sequence and then checks
for each pair of terms whether their sum is in the sequence.(1pt)
1d) Give a big-O estimate for the complexity of this algorithm. Is it more efficient than the brute-force algorithm? (1pt)
2. (2 points) Use the definition of big O to prove or disprove. 2a) Is 2^(n+1) ≟ O(2^n) (1pt)
2b) Is 2^(2n) ≟ O(2^n)(1pt) 3. (1point)
4. (2points)
Some sorting algorithms are NOT stable (duplicate keys relative order is preserved after sorting). However if every key in A[i] is changed to A[i]*n + i - 1 (assume 1<=i<=n ) then all the new elements are distinct (and therefore stability is no longer a concern). After sorting, what transformation will restore the keys back to their original values? What is the effect on the runtime of any of the sorting algorithms if you add this transformation before executing the sort and un-transformation after the sort?
