Αλγόριθμοι και Πολυπλοκότητα (Μεταπτυχιακό)
Περιγραφή εβδομάδας
- Χειμερινό Εξάμηνο 2020-2021
Χειμερινό Εξάμηνο 2020-2021
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Θανάσης Λιανέας, postdoc (lianeas@corelab.ntua.gr)
- Αντώνης Αντωνόπουλος, Υ/Δ (aanton@corelab.ntua.gr)
Πέμπτη 19:00-20:00, διαδικτυακά.
Webex link: https://centralntua.webex.com/centralntua/j.php?MTID=m739697906ca74ad33ee0d2725246b9e2
Βιβλιογραφία
[DPV] Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani. 2006. Algorithms (1 ed.). McGraw-Hill, Inc., New York, NY, USA. (PDF) - Τελική Εξέταση
Τελική Εξέταση
Webex link επίδειξης γραπτών (05/04, 1-3μμ):https://centralntua.webex.com/centralntua/j.php?MTID=m01f7a9b671440c389024f593d8b8a51b - 2 October - 8 October
- 9 October - 15 October
- 16 October - 22 October
- 23 October - 29 October
23 October - 29 October
A faster algorithm computing string edit distances, by W. Masek and M. Paterson
Ομιλητής: Αριστοτέλης Κουτσουρίδης
- 30 October - 5 November
30 October - 5 November
Cuckoo hashing, by Rasmus Pagh and Flemming Friche Rodler
Ομιλητής: Χρήστος Δουλάμης
- 6 November - 12 November
- 13 November - 19 November
13 November - 19 November
The Complexity of Theorem-Proving Procedures, by Stephen A. Cook
Ομιλητής: Θωμάς Πιπιλίκας
- 20 November - 26 November
20 November - 26 November
New Directions in Cryptography, by Whitfield Diffie and Martin Hellman
Ομιλήτρια: Δανάη Μπάλλα
- 27 November - 3 December
27 November - 3 December
Minimum-cost spanning tree as a path-finding problem, by B. Maggs and S. Plotkin
Ομιλητής: Νικήτας Πασλής
- 4 December - 10 December
4 December - 10 December
Paths, trees, and flowers, by J. Edmonds
Ομιλήτρια: Μαρία-Μαρκέλλα Διαμαντοπούλου
- 11 December - 17 December
11 December - 17 December
Amortized Computational Complexity, by R. Tarjan
Ομιλητής: Μερκούρης Παπαμιχαήλ
- 1 January - 7 January
1 January - 7 January
Approximation algorithms for TSP and Vertex Cover (Christofides etc.)
Ομιλητής: Φίλιππος Μαυρόπουλος
- 8 January - 14 January
- 15 January - 21 January
15 January - 21 January
Relaxed Heaps: An alternative to Fibonacci Heaps with applications to parallel computation, by J. Driscoll, H. Gabow, R. Shrairman and R. Tarjan
Ομιλήτρια: Ηλέκτρα-Στυλιανή Γεωργιάδου
- 22 January - 28 January
22 January - 28 January
On the computational complexity of algorithms, by J. Hartmanis and R. E. Stearns
Ομιλητής: Γεώργιος Μήτσιου
- 29 January - 4 February
29 January - 4 February
Universal Classes of Hash Functions, by L. Carter and M. Wegman
Ομιλητής: Χαράλαμπος Τζάμος
- 5 February - 11 February
5 February - 11 February
Beyond worst case: Smoothness and solving knapsack through its pareto curve.
Ομιλητής: Κωνσταντίνος Βροχίδης
- 12 February - 18 February
12 February - 18 February
Relationships between nondeterministic and deterministic tape complexities, by Walter J. Savitch
Ομιλητής: Δημήτρης Δεμπέλας