Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Bitonic Sorters Of Minimal Depth
event speaker icon
Tamir Levi (Ph.D. Thesis Seminar)
event date icon
Wednesday, 05.05.2010, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. A. Litman
A Bitonic sorter is a comparator network that sorts every Bitonic input sequence. In our research, we studied the minimal depth of such networks. Building on previous works, we establish that the minimal depth of a Bitonic sorter of n keys is 2ceiling(log(n)) -floor(log(n)). This result is constructive - that is, we present, for every n, a Bitonic sorter of that depth. In this talk I will also present other results from my PhD research.