Worksheet 4 - Question set PDF

Preview

Summary

Question set...

Description

Programming Concepts

Worksheet 4

1 Algorithms 1. A palindrome is a word that is the same if read forwards or backwards: “radar” is one such example. The same idea can be applied to numbers: 12321 and 165561 are palindromes, but 1231 is not. For this question, assume an array of digits (elements of the array are 0–9, for example [1, 9, 5, 2]), and write an algorithm that decides if an input array A[1...n] of digits is a palindrome. Test your answer on the arrays: [1, 6, 5, 5, 6, 1] and [1, 2, 3, 1]. Optional: Suggest an appropriate loop invariant. 2. One disadvantage of using For-loops in sorting algorithms is that the body of the For-loops are repeatedly executed even if it is no longer necessary. For example, consider running the following version of Bubble sort : Input: Array A[1 . . . n] Output: Array A sorted for i ← 1 to (n − 1) do for j ← 1 to (n − i) do if A[j] > A[j + 1] then A[j] ↔ A[j + 1] return A on the array [2, 1, 3, 4, 5]. We know that when 2 and 1 are interchanged, early on in the execution of the algorithm, the array is sorted and all subsequent comparisons are unnecessary. Write a version of Bubble sort which cuts down on these unnecessary comparisons. In particular, when the array is sorted the algorithm should try to stop further comparisons, all of which are redundant. Hint: If the array is ever scanned without any interchanges being made we know that the array is sorted. 3. Write an algorithm to find the second largest element in an array (you can assume that there are more than two elements). Additional question: what about the ith largest?

Questions...