# Lecture Data Structures and Practise - Hanyang

Lecture 6 Algorithm Analysis Arne Kutzner Hanyang University / Seoul Korea Sorting Networks Sorting Networks Example of Parallel Algorithms Not directly related to our classical computer models (e.g. Turing machines, von-Neumann architecture)

2016/10 Algorithm Analysis L6.3 Comparator wire Input wires Output wires

Works in O(1) time. 2016/10 Algorithm Analysis L6.4 Example of Comparison Network Input

Output Wires go straight, left to right. Each comparator has inputs/outputs on some pair of wires. 2016/10 Algorithm Analysis L6.5 Correctness of Example Network Claim that this comparison network will

sort any set of 4 input values: After leftmost comparators, minimum is on either wire 1 (from top) or 3, maximum is on either wire 2 or 4. After next 2 comparators, minimum is on wire 1, maximum on wire 4. Last comparator gets correct values onto wires 2 and 3. 2016/10 Algorithm Analysis L6.6

Definition of Depth Depth of some Wire: Input depth: dx Output depth: max (dx ,dy) + 1 Input depth: dy Input wires of the network have depth 0 Depth of a comparator := depth of its output wire Depth of a Network := maximum depth of a

an output wire of the network 2016/10 Algorithm Analysis L6.7 Depth - Example Depth 1 2016/10 Depth 2

Algorithm Analysis Depth 3 L6.8 Selection Sorter Foundation: Bouble-Sort Idea Find the maximum of 5 values: 2016/10 Algorithm Analysis

L6.9 Selection Sorter (cont.) We extend our idea: Selection Sorter for 4 elements Depth: 2016/10 Algorithm Analysis

L6.10 Zero-one principle How can we test if a comparison network sorts? We could try all n! permutations of input. But we will see that we need to test only 2n permutations. Theorem (0-1 principle) If a comparison network with n inputs sorts all 2n sequences of 0.s and 1.s, then it sorts all

sequences of arbitrary numbers. 2016/10 Algorithm Analysis L6.11 Important Lemma Lemma: If a comparison network transforms a = into b = , then for any monotonically increasing function f , it transforms

f(a) = into f(b) = . 2016/10 Algorithm Analysis L6.12 Proof of Lemma Important property: Then use induction on the depth of some wire

2016/10 Algorithm Analysis L6.13 Proof of 0-1 principle Suppose that the principle is not true, so that an n-input comparison network sorts all 0-1 sequences, but there is a sequence such that ai < aj but ai comes after aj in the output. Define the monotonically increasing function

2016/10 Algorithm Analysis L6.14 Proof 0-1 principle (cont.) By our lemma proven before: If we give the input , then in the output we will have f(ai) after f(aj)

But this results in an unsorted 0-1 sequence. A contradiction. 2016/10 Algorithm Analysis L6.15 Definition of the notion bitonic A sequence is bitonic if it monotonically increases, then monotonically decreases, or it can be circularly shifted to become so. Examples: <1, 3, 7, 4, 2>, <6, 8, 3, 1, 2, 4>,

<8, 7, 2, 1, 3, 5> For 0-1 sequences bitonic sequences have the form: 2016/10 Algorithm Analysis L6.16 Half Cleaner Comparison network of depth 1 in which input of line i is compared with line i+n/2

for i=1,2,,n/2 2016/10 Algorithm Analysis L6.17 Property of Half Cleaner Lemma: If the input to a half-cleaner is a bitonic 0-1 sequence, then for the output: both the top and bottom half are bitonic, every element in the top half is every element in

the bottom half, and at least one of the halves is clean.all 0.s or all 1.s. Proof: Simple inspection of 8 different cases. 2016/10 Algorithm Analysis L6.18 Bitonic Sorter

Recursively defined, so we have: 2016/10 Algorithm Analysis L6.19 Example for bitonic Sorter 2016/10

Algorithm Analysis L6.20 Merging Network Idea: Given 2 sorted sequences, reverse the second one, then concatenate with the first one get a bitonic sequence. Example: X = 0011 Y = 0111 YR = 1110 XYR = 00111110 (bitonic) 2016/10

Algorithm Analysis L6.21 Merging Network (cont.) How do we reverse Y? We dont! Instead, we reverse the bottom half of the connections of the first half-cleaner: X X

is equal to Y YR 2016/10 Y Algorithm Analysis L6.22 Merging Network - Example

So we get as Merging Network: 1 0 2016/10 Algorithm Analysis 0 1 L6.23

Sorting Network Construction Principle Using the MergeSort-Idea we can recursively construct a Sorting Network by combining several Merger 2016/10 Algorithm Analysis L6.24 Sorting Network - Example

Example: n = 8 Sorter Sorter 2016/10 Algorithm Analysis L6.25 Sorting Network Example (cont.) Merger

2016/10 Merger Merger Algorithm Analysis L6.26 Sorting Network Complexity Analysis

According to the construction principle for sorting networks we get: 2016/10 Algorithm Analysis L6.27

## Recently Viewed Presentations

• As you test each item, record whether it was a conductor or and insulator with a Item Conductor Insulator Did the bulb light? Spoon Paper clip pencil Rubber band eraser Foil Nail coin Use of a circuit tester: To test...
• Stoke Speaks Out, Family Technology, Robotics, Puppet Workshop, First Aid, Flare for Fashion, Caribbean Cook & Eat, African Crafts, ... Etruria Industrial Museum, Community Cohesion x 4 (Newstead & Stoke Minster), BT Paralympic World Cup, Olympic Torch Relay. Football.
• October 30. Planner. Record today's assignments and homework. Warm Up. Study . Knowsys. Read AR. Vocabulary. Knowsys - Crossword. Grammar/Writing - Personal Narrative
• Tips for picking books for preschoolers Find books that they can relate to. Read stories with simple plots. Folk tales and books with animals that act like humans are popular. Little children like rhyming books. Pick books that are interesting...
• Cab Roof Rear of Cab (View from behind the Operator's Station) Master Guidance On/Off Switch Wheel Angle Sensor (View of inside front left wheel hub) Field Installed Valve Kit Isolation Valve (View of tractor left side, hood up, in front...
• Title: Cytologie a anatomie rostlin - cvičení Author: Mycorrhizal Lab Last modified by: user Created Date: 9/18/2007 10:33:44 AM Document presentation format
• fas. rma. fsa. chart2. fsa. adm. dafp. daflp. dafo. daco. dam. fy07. fy08. fy09 . fy10. fy11. fas. immediate office. 10 01 00 0000 00 00 00 00 . 10 04 06 0000 00 00 00 00. 10 05 14...
• Susan Todd. Professor of English, Jefferson College, Hillsboro, Missouri. Author of the forthcoming Pearson Title Links to Literacy. [email protected] The Case for Content in Developmental Writing Assignments