www.vustudents.ning.com

We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.

# CS502 Assignment No 2 Solution & Discussion Due Date: 02-05-2012

Assignment Statements:

Question 1:

Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?

Views: 1560

Attachments:

### Replies to This Discussion

any one get it?

I think a bit error in the above solution file....

Exercise 8.3-3
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
solution:
Basis: If , sorting on that digit sorts the array correctly.
Inductive step: Assume that RADIX-SORT sorts  digits correctly. Consider two elements  and , with their th digit  and  respectively.
(1)  and  : RADIX-SORT works correctly, because of most significant bit dominates regardless of the lower  digits.
(2)  : RADIX-SORT leaves  and  in the same order because it is stable sort. The order is correct since lower  digits sorts correctly. That's why we need that the intermediate sort must be stable.

thanks a lot

iss ki to koi samj nae ae

Any one share the correct solution..............................

yar time kum ha............ kuch to krooooooo

1

2

3

4

5

## Latest Activity

Hina Tahir added a discussion to the group HRM627 Human Resource Development

### GDB: HRM627- Human Resource Development

4 hours ago
11 hours ago
Famia Khan joined + M.Tariq Malik's group

### CS506 Web Design and Development

11 hours ago
Famia Khan added a discussion to the group CS614 Data Warehousing

### cs614 Assigment no1 fall 2021

11 hours ago
Famia Khan joined + M.Tariq Malik's group

### CS614 Data Warehousing

11 hours ago
jamil sadiq joined + M.Tariq Malik's group

### ENG503 Introduction to English Language Teaching

11 hours ago
Famia Khan and Hania Khalid Shariff are now friends
11 hours ago
Ehrish Gul updated their profile
14 hours ago