Session 5 : Pseudo Code - Iterated Prisoners Dilemma

6. Session 5 : Pseudo Code - Iterated Prisoners Dilemma#

6.1. Session Overview#

This session is in two parts

6.1.1. Part 1#

The first part of the session is an introduction to using Pseudo Code to describe algorithms. There will be several examples which you are expected to study.

6.1.2. Part 2#

Part 2 of the session is a tutorial to allow you to further develop your code for the Iterated Prisoners Dilemma (IPD).

6.2. What is Pseudo Code ?#

Pseudocode is a high-level, human-readable description of an algorithm that uses a mix of plain English and structured programming conventions (like loops, conditionals, and indentation) without relying on strict syntax. It acts as a bridge between a conceptual idea and actual code, used for planning, communicating, and documenting logic.

Note - AI generated.

6.3. Why Pseudo Code ?#

  • Programming system agnostic

  • Human readable

  • Can incorporate mathematics or other domain specific constructs

  • Most program code is not particularly descriptive (at least for a human reader)

  • Commonly used in text books, journal publications, and technical literature

6.4. Tips for writing Pseudo Code#

There is no standard Pseudo Code. However,

  • It should suggest the appropriate data structures

  • Is should have declarative style information (domain, coddomain, description of what it does)

  • Imperative details should be minimal and language agnostic

  • It should not describe how the code has to be written

A good way to learn how to write good pseudo code is to look at plenty of examples. When studying them, try asking the following questions

  • What data structures are employed

  • What are the inputs

  • What are the expected outputs

  • Are there any edge cases

If you cannot answer these questions, it may not be a good example.

6.5. Example 1#

This example is available online here

Binary Search is a searching algorithm that works only for sorted search space. It repeatedly divides the search space into half by using the fact that the search space is sorted and checking if the desired search result will be found in the left or right half.

Given a sorted array Arr[] and a value X, The task is to find the index at which X is present in Arr[]

BinarySearch(ARR, X, LOW, HIGH)
       repeat till LOW = HIGH
              MID = (LOW + HIGH)/2
              if (X == ARR[mid])
                  return MID
              else if (x > ARR[MID]) 
                  LOW = MID + 1
              else                  
                  HIGH = MID - 1

6.5.1. Exercise#

Study the pseudo code in example 1 and try answering the questions suggested in the section Tips for writing Pseudo Code

6.5.2. Exercise#

Try implementing Binary Search in python

6.6. Using Mathematical Concepts in Pseudo Code#

Pseudo Code can use notation, concepts, and terminology that are appropriate to the target readership. In particular, mathematical concepts are commonly used.

6.7. Example 2#

The following is pseudo code for the optimal partitioning algorithm as described in “Optimal detection of changepoints with a linear computational cost” by Killick, Fearnhead, and Eckley

>

6.7.1. Exercise#

With reference to the above pseudo code how would you represent in python

  • F

  • cp

  • C

  • y

Given your choice of reprersentation for cp, how would you “implement” the operation in step 3 ?

6.7.2. Exercise#

Follow this link to the original work on optimal partitioning and compare the pseudo code presented therein to that provided by Killick et al. Which do you prefer ? Why ?

6.7.3. Exercise#

The following pseudo code is for the PELT methos which is an extension to the Optimal Partitioning Method described previously.

>

6.7.4. Exercise#

  • What python representation would you use for cp in the above pseudo code ?

  • Is your choice informed by the notation in the pseudo code, the concepts the pseudo code invokes, or both ?

  • How would you describe the “structure” of cp after a few iterations of the algorithm ?

  • If you were to choose notation for cp and y in the PELT method what would it be ?

  • The notation for cp is different in the Optimal Partitioning pseudo code and the PELT method. Why do you think this might be ?

6.8. Iterated Prisoners Dilemma#

The remainder of this session is a tutorial for continuing your work on the Iterated Prisoners Dilemma. In this session you should focus on

  • Implementing at least one type of competetion, e.g. a Round Robin Competition whilst exploring any benefits of using Pattern 6 from Session 2.

  • Swap the code for one of your strategies with someone else and try and run theirs in your competition with view to answering the following questions :

    • Did it work ?

    • If not, why not ?

    • Did you have to change their code to make it work ?

    • How did you share the code ?

    • Whose strategy is the best ?

  • Write some pseudo code to describe how your competition works.

Contents