Seminar • Algorithms and Complexity — The Combinatorics of Furthest and Nearest ValuesExport this event to calendar

Wednesday, May 22, 2019 1:30 PM EDT

Lily Wang, University of Waterloo

A classical problem asks us to find, for each element $A[i]$ of an array of integers, the position of the nearest smallest element. Similarly, we can ask about the dual problem: for each element of an array of integers $A[i]$, what is the position of the furthest smaller element? 

In our paper, we discussed both these problems from a combinatorial perspective and considered algorithms to solve them. By examining results of permutations of distinct integers and behaviour of the algorithms, we find many classical combinatorial sequences such as the Stirling numbers, the Catalan numbers, the Bell numbers, and the harmonic numbers.

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
  1. 2024 (98)
    1. April (21)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)