Master Thesis Defense in Algorithms
36 views
Skip to first unread message
Philip Bille
Dec 4, 2012, 4:03:39 AM12/4/12
to alg...@googlegroups.com, Sune Keller, Inge Li Gørtz, Husfeldt Thore
Master thesis defense. All are welcome. Please forward to other interested people. For DTU students who consider doing a master thesis in algorithms, I strongly encourage you to go to these defenses.
When: Wednesday, December 14, 11.00-12.00
Where: 322/030
Title: Persistence in Practice
Speakers: Sune Keller
Advisors: Philip Bille and Inge Li Gørtz
External examiner: Thore Husfeldt, IT University of Copenhagen
Abstract:
The goal of the thesis is to theoretically analyse and compare Node Copying and Rollback, two approaches to making a data structure partially persistent (allowing the access of any previous version), and to evaluate in practice which of them is more suited for use in two different usage scenarios: a sequential one, where operations are applied in long sequences generating versions with large data structures; and a randomized one, where operations are executed in a random order. A doubly linked list is used as the example data structure.
It is found that Node Copying performs significantly better than Rollback in terms of space complexity regardless of the usage scenario. It also performs better in accessing a desired version in the randomized scenario independently of the data set size.
In the sequential scenario, when the data set is large enough, the smaller time complexity related to navigating the data structure at a given version makes an optimized implementation of Rollback faster than Node Copying at reaching a given index inside a desired version.
When: Wednesday, December 14, 11.00-12.00
Where: 322/030
Title: Persistence in Practice
Speakers: Sune Keller
Advisors: Philip Bille and Inge Li Gørtz
External examiner: Thore Husfeldt, IT University of Copenhagen
Abstract:
The goal of the thesis is to theoretically analyse and compare Node Copying and Rollback, two approaches to making a data structure partially persistent (allowing the access of any previous version), and to evaluate in practice which of them is more suited for use in two different usage scenarios: a sequential one, where operations are applied in long sequences generating versions with large data structures; and a randomized one, where operations are executed in a random order. A doubly linked list is used as the example data structure.
It is found that Node Copying performs significantly better than Rollback in terms of space complexity regardless of the usage scenario. It also performs better in accessing a desired version in the randomized scenario independently of the data set size.
In the sequential scenario, when the data set is large enough, the smaller time complexity related to navigating the data structure at a given version makes an optimized implementation of Rollback faster than Node Copying at reaching a given index inside a desired version.
Sune Keller
Dec 5, 2012, 8:45:28 AM12/5/12
to Philip Bille, alg...@googlegroups.com, Inge Li Gørtz, Husfeldt Thore
Please note that the announced weekday is incorrect; it should be Friday, December 14.
--
Sune :)
--
Sune :)
Philip Bille
Dec 14, 2012, 4:02:25 AM12/14/12
to alg...@googlegroups.com, Philip Bille, Inge Li Gørtz, Husfeldt Thore
The room has been changed to the larger 322/033.
\Philip
Reply all
Reply to author
Forward
0 new messages