Σύντομη μελέτη πριν το μάθημα της Τετάρτης 8/3

 
Φωτογραφία Orestis Plevrakis
Σύντομη μελέτη πριν το μάθημα της Τετάρτης 8/3
από Orestis Plevrakis - Monday, 6 March 2023, 9:04 AM
 

Στο μάθημα των Αλγορίθμων μάθατε για το πρόβλημα της εύρεσης της μέγιστης αύξουσας υπακολουθίας ενός πίνακα (Dasgupta, Papadimitriou, Vazirani ενότητα 6.2). Μάλιστα, στο μάθημα είδατε ότι υπάρχει καλύτερος αλγόριθμος απ' το DP, ο οποίος λύνει το πρόβλημα σε nlogn. Αν δε θυμάστε αυτόν τον αλγόριθμο, μην τον ψάξετε! Αντ' αυτού, αφιερώστε λίγο χρόνο να προσπαθήσετε να τον ανακαλύψετε μόνοι σας. Την Τετάρτη θα δούμε πώς μπορούμε να τον ανακαλύψουμε, εφαρμόζοντας τις στρατηγικές σκέψης που θα μελετήσουμε στο μάθημα.