דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
רן בן-בשט (מדעי המחשב, טכניון)
event date icon
יום רביעי, 25.10.2017, 12:30
event location icon
טאוב 201
Computing the sum of elements over a sliding window is a textbook interview question. By storing the last window and its sum in memory, we can process elements and answer queries in constant time and near-optimal space. In this talk, I will discuss a variant of this problem where the user specifies the window size i≤n query time, and only an upper bound n is known in advance.

As window sizes in practice may be large, standard practice is to settle on approximation algorithms that use sub-linear space. I will present upper and lower bounds on the space required for approximating such queries.