A review of probabilistic algorithms

To begin, let’s explore whether we can apply the concepts covered so far to solve the following hypothetical problems:

• A new online dating app, Matcher, has been developed to help users find potential partners. The app functions like a game, aiming to match users with their best possible dates:
  • There are potential matches available on the app (the total number of matches is unknown to the users). Let’s consider a user named Tom.
  • When Tom opens the Matcher app, he is presented with one potential match at a time, selected randomly. Tom has the option to either like (swipe right) or dislike (swipe left) each profile.
  • Tom’s decisions are irreversible; once he swipes right or left on a profile, he cannot change his mind. All decisions are final.
  • Tom can like a maximum of profiles (where n is much smaller than N). Once Tom has liked profiles, the app will no longer show him any more profiles.
  • The interaction ends either when...