Question

1.             (5 marks) Perform a selection sort on the list 23, 59, 34, 13, 31, 10. Show the list after each exchange that has an effect on the list ordering.

2.             (5 marks) Explain why the bubble sort algorithm does Ө(n²) comparisons on an n-element list. The bubble-sort algorithm is shown just after question 10 on p. 141.

3.              (5 marks) Write the resulting data list, give the ending value of legit, and find the exact number of copies done by the converging pointers algorithm when executed on this set of data:

72

0

0

35

41

0

13

27

44

0

4.              (5 marks) If the pattern-matching problem was changed to only find the first instance of a pattern of length m in the text of length n.

(a)    Describe the data that would cause the worst-case performance and the performance in terms of n. Use "Big-O" notation, e.g. Θ(n), Θ(n²), etc.

(b)   Describe the data that would cause the best-case performance and the performance in terms of n. Use "Big-O" notation, e.g. Θ(n), Θ(n²), etc.

5.             (5 marks) Do Exercise 38 from Chapter 3 on page 147.

6.             (5 marks) Calculate the decimal value of the following numbers. Show your work.

(a) The base 5 number 342

(b) The base 6 number 415

(c) The base 16 hexadecimal number 7EAh (the h indicates hex)

7.             (5 marks) Give the decimal value of the following numbers). Show your work.

(a) The 2s complement number 01010101

(b) The 2s complement number 10101101

(c) The 2s complement number 01111111

(d) The 2s complement number 10000111

(e) The a sign/magnitude number 10001101

8.              (5 marks) Using the ASCII code given in Figure 4.3 on p. 164 (162 in 6th edition) give the binary representation for the phrase "Hi Paul!", ignoring the quotation marks. Make sure to space each 8-bit ASCII code apart from the next so they are easy to read, e.g.

01000001 01100010 01000011

Answer 1

Answer 1.

23 59 34 13 31 10

Find minimum element in [23 59 34 13 31 10] and swap it with the element at beginning of [23 59 34 13 31 10]
10 59 34 13 31 23

Find minimum element in [59 34 13 31 23] and swap it with the element at beginning of [59 34 13 31 23]
10 13 34 59 31 23

Find minimum element in [34 59 31 23] and swap it with the element at beginning of [34 59 31 23]
10 13 23 59 31 34

Find minimum element in [59 31 34] and swap it with the element at beginning of [59 31 34]
10 13 23 34 31 59

Find minimum element in [31 59] and swap it with the element at beginning of [31 59]
10 13 23 34 31 59

Find minimum element in [59] and swap it with the element at beginning of [59]
10 13 23 34 31 59

LIST IS SORTED

AS PER CHEGG'S POLICY ONLY FIRST QUESTION WILL BE ANSWERED