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

need idea solution plz.. some one upload soon . :)

plzzzzzzzzzzz koi idea solution upload kren

any body have a solution tu plzzzzzzz upload it. tody is lastdate............

Bro aj last date ha koi to ideal solution share kre

here is the solution.....100% surely correct hai.

bt plz every one write it his own words so that we all can get good marks.

file attach ha.

Attachments:

simply it is idea solution and 100% correct.

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 $d = 1$, sorting on that digit sorts the array correctly.
Inductive step: Assume that RADIX-SORT sorts $d-1$ digits correctly. Consider two elements $a$ and $b$, with their $d$th digit $a_d$ and $b_d$ respectively.
(1) $a_d > b_d$ and $b_d > a_d$ : RADIX-SORT works correctly, because of most significant bit dominates regardless of the lower $d-1$ digits.
(2) $a_d = b_d$ : RADIX-SORT leaves $a$ and $b$ in the same order because it is stable sort. The order is correct since lower $d-1$ digits sorts correctly. That's why we need that the intermediate sort must be stable.

thanks more

thanks dear bro

more thanks for guide line

plzz upload idea solution aj last date hai plzzzzzzzzzzzzzzz

upload tu hochaka he Areeba check karay na

1

## Latest Activity

Sajid Hussain, Samrina, Malaika Iqbal and 2 more joined Virtual University of Pakistan
49 minutes ago

### Mgt610 midterm fall 2021 (jan-14-2022)

6 hours ago
Muhammaad Arif, Student, Batool and 2 more joined Virtual University of Pakistan
yesterday
Nida Arshad Javaid Ch posted photos
yesterday
subhan ali joined + M.Tariq Malik's group

### MGT404 Managerial Accounting

yesterday
Suha Khan joined + M.Tariq Malik's group

### HRM627 Human Resource Development

yesterday
yesterday
Nida Arshad Javaid Ch posted a blog post

yesterday
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 14, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://vustudents.ning.com/forum/topics/cs-502-assignment-no-2-solution?groupUrl=cs502fundamentalsofalgorithms&commentId=3783342%3AComment%3A1234995&groupId=3783342%3AGroup%3A59371", "fetch_time": 1642331618000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2022-05/segments/1642320299852.23/warc/CC-MAIN-20220116093137-20220116123137-00011.warc.gz", "warc_record_offset": 675917204, "warc_record_length": 17986, "token_count": 638, "char_count": 2337, "score": 3.84375, "int_score": 4, "crawl": "CC-MAIN-2022-05", "snapshot_type": "latest", "language": "en", "language_score": 0.7876331210136414, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00015-of-00064.parquet"}