## ← List Ranking Part1 - Intro to Parallel Programming

• 4 Followers
• 21 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=ihnknZirVuA" data-team="udacity"></div> ``` 2 Languages

Showing Revision 4 created 05/25/2016 by Udacity Robot.

1. So let's try a slightly harder algorithm called list ranking.
2. In list ranking, each node has the index of its successor in the list,
3. and we know the first element in the output.
4. What we want to be able to do is put the nodes in order.
5. This has a number of uses, and in our lab, we've used it to decompress data
6. that's been compressed with B sub 2, so let's take a look at an example.
7. As an example we've got 10 nodes here.
8. We know that the output is going to begin with node 0
9. and the successor to node 0, so one farther in the chain is node 5.
10. The successor to node 5 is node 2.
11. The successor to node 2 is node 7 and so on.
12. So this is our input--this array of 5, 6, 7, 9, 2, 3, 0, 1.
13. What's our output going to be?
14. It's going to be the chain 0, 5, 2, 7, 4, 9, 1, 6, 3, 8.
15. So here's our input, and here's the output.
16. Now, you can note that the array is actually circular,
17. so it's necessary to actually designate the starting point,
18. and in this case we're saying that node number 0 is the starting point.
19. Of course, a serial processor could do this N steps.
20. The question is, how can we make it work with parallel hardware
21. with a smaller number of steps?