Understanding the Dueling Algorithm for Data Structures

dueling algorithm n.w
1 / 14
Embed
Share

Explore the Dueling Algorithm for efficient conflict resolution in data structures. Learn about dueling cases, candidates, initialization, main loop, and algorithm completion. Witness how potential candidates interact and agree within mutual ranges.

  • Algorithm
  • Data Structures
  • Conflict Resolution
  • Dueling
  • Initialization
rayaanacharya
thom_za Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Dueling Algorithm

  2. DUEL i and j if j-i m then no conflict otherwise s T[i+W[j-i+1]-1] Cases: if s=* then * if s=P[W[j-i+1]] then kill j else kill i

  3. Data Structures List of potential candidates R = rightmost element of that list N = new element R N

  4. Initialization Add 1 to list R 1 N 2 R N

  5. Main Loop While n-N m-1 (new candidate fits) do: If N-R m (candidates are far) then: add N to list R N N N+1 goto endWhile

  6. Candidates are far R N

  7. Main Loop (Candidates are within mutual range) Duel R and N Cases: N dies R dies * (both live) endWhile

  8. Case 1: N dies If N dies then: N N+1 goto endWhile

  9. Case 1: N dies X R N N

  10. Case 2: R dies If R dies then: Remove R from list. If list empty then: R N N N+1 Goto endWhile else: R points to previous element in list Goto endWhile

  11. Case 2: R dies X R N

  12. Case 3: * (no one dies) If * then: add N to list R N N N+1 Goto endWhile

  13. Case 3: * (no one dies) R N

  14. At end of Algorithm: All elements in list are potential candidates. All elements in list agree with each other.

Related


No related presentations.

More Related Content