PREGLED I IMPLEMENTACIJA ODABRANIH RETROAKTIVNIH STRUKTURA PODATAKA
Ključne reči:
napredne strukture podataka, retroaktivne strukture podataka, red, stek, red sa prioritetom
Apstrakt
Retroaktivne strukture podataka podržavaju modifikaciju niza operacija izvršenih nad datom strukturom. U ovom radu opisani su koncepti parcijalne i potpune retroaktivnosti, te je ilustrovana parcijalna retroaktivnost pomoću odabranih struktura: red, stek i red sa priotitetom. Glavni fokus rada jeste opis metoda implementacije odabranih struktura pomoću dvostruko povezane liste i strukture treap. Zaključeno je da se može postići vrijeme izvršavanja slično odgovarajućim standardnim strukturama.
Reference
[1] MIT Open Courseware, „Advanced Data Structures“, Prof. Erik Demaine, ocw.mit.edu, Stranica kursa „Napredne strukture podataka“, pristupano: maj 2023.
[2] E. D. Demaine, J. Ianoco, S. Langerma, „Retroactive Data Structures“, Proceedings of the Fifteenth Snnual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Lousiana, USA, January 11-14, 2004.
[3] E. D. Demaine, T. Kaler, Q. Liu A. Sidford, A. Yedidia, „Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing“, MIT CSAIL Cambridge, MA, USA, 2015.
[4] J. W. Andrade Junior, R. Duarte Seabra, „Fully Retroactive Priority Queues using Persistent Binary Search Trees“, Journal of Computer Science, 16(7), pp. 906-915, July 2020.
[5] GeeksForGeeks, „Complete Guide On Complexity Analysis – Data Structure and Algorithms Tutorial“, geeksforgeeks.org, članak na sajtu GeeksForGeeks, pristupano: maj 2023.
[6] S. Agarwal, P. Panwaria, „Implementation, Analysis and Application of Retroactive Data Structures“, Proc. of the Intl. Conf. on Advances in Computer Science and Electronics Engineering, 2012.
[7] Sunita, D. Garg, „Dynamizing Dijkstra: A solution to dynamic shortest path problem through retroactive priority queue“, Journal of King Saud University - Computer and Information Sciences Volume 33, Issue 3, pp. 364-373, March 2021
[2] E. D. Demaine, J. Ianoco, S. Langerma, „Retroactive Data Structures“, Proceedings of the Fifteenth Snnual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Lousiana, USA, January 11-14, 2004.
[3] E. D. Demaine, T. Kaler, Q. Liu A. Sidford, A. Yedidia, „Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing“, MIT CSAIL Cambridge, MA, USA, 2015.
[4] J. W. Andrade Junior, R. Duarte Seabra, „Fully Retroactive Priority Queues using Persistent Binary Search Trees“, Journal of Computer Science, 16(7), pp. 906-915, July 2020.
[5] GeeksForGeeks, „Complete Guide On Complexity Analysis – Data Structure and Algorithms Tutorial“, geeksforgeeks.org, članak na sajtu GeeksForGeeks, pristupano: maj 2023.
[6] S. Agarwal, P. Panwaria, „Implementation, Analysis and Application of Retroactive Data Structures“, Proc. of the Intl. Conf. on Advances in Computer Science and Electronics Engineering, 2012.
[7] Sunita, D. Garg, „Dynamizing Dijkstra: A solution to dynamic shortest path problem through retroactive priority queue“, Journal of King Saud University - Computer and Information Sciences Volume 33, Issue 3, pp. 364-373, March 2021
Objavljeno
2023-12-05
Sekcija
Elektrotehničko i računarsko inženjerstvo
