Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό andreass » 02 Δεκ 2020, 18:20

Εδώ μπορείτε να υποβάλετε ερωτήσεις, απορίες ή παρατηρήσεις σχετικές με την Εργασία 2.
andreass
Newbie
 
Δημοσιεύσεις: 23
Εγγραφή: 30 Ιουν 2012, 12:18

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό JimPap21 » 03 Δεκ 2020, 16:45

Κυριε τωρα που γραφουμε κλασεις θα γραφουμε main;
JimPap21
Newbie
 
Δημοσιεύσεις: 4
Εγγραφή: 06 Φεβ 2020, 16:44

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό andreass » 03 Δεκ 2020, 20:43

Στην απάντηση σας στο moodle δεν πρέπει να έχετε main παρά μόνο τις μεθόδους που ζητήθηκαν ή μεθόδους που χρειάζεται να δημιουργήσετε για την εκτέλεση των μεθόδων που ζητήθηκαν. Όμως κατά τις δοκιμές που θα κάνετε offline στο Eclipse/Jetbrain θα χρειαστεί να έχετε μια main όπως σας έδειξα στο εργαστήριο.
andreass
Newbie
 
Δημοσιεύσεις: 23
Εγγραφή: 30 Ιουν 2012, 12:18

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό JimPap21 » 03 Δεκ 2020, 20:49

Επισης πρεπει να φτιαξουμε και στιγμιοτυπο πχ new Stack;
JimPap21
Newbie
 
Δημοσιεύσεις: 4
Εγγραφή: 06 Φεβ 2020, 16:44

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό DemocritusVomitus » 04 Δεκ 2020, 15:33

Καλησπέρα, στο δεύτερο ερώτημα ο έλεγχος επιστρέφει πως παραβιάζεται το όριο συγκρίσεων, παρόλο που δεν υπάρχει.
Συνημμένα
εργ2.2_ΑλγΔΔ202021.png
DemocritusVomitus
Newbie
 
Δημοσιεύσεις: 1
Εγγραφή: 22 Ιαν 2020, 19:23

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό omeleta » 04 Δεκ 2020, 19:20

Στο Ερώτημα 3 ζητάει αριθμό επαναλήψεων O(nlogn) ωστόσο έτρεξα quickSort, mergeSort, HeapSort, countingSort και TimSort, όλες με μέσο χρόνο πολυπλοκότητας O(nlogn) και όλες παραβίασαν τον αριθμό των συγκρίσεων, επομένως μετά από λίγο ψάξιμο βρήκα ότι η mergeSort χρειάζεται T(n*lgn) αριθμό επαναλήψεων, όπου lg =log to the base 2.
Τώρα ή λέω βλακείες και οι κώδικες που έτρεξα είναι όλοι λάθος ή κάτι τρέχει με το ερώτημα.

Επιπλέον όπως προανέφερε ο DemocritusVomitus στο και εμένα μου έβγαζε ότι παραβιάζεται το όριο αλλά βρήκα αλγόριθμο που τρέχει χωρίς λάθη.
Επίσης να συμπληρώσω πως στο τέταρτο ερώτημα μου έβγαζε ότι παραβιάζεται ο αριθμός των συγκρίσεων, μέχρι που έτρεξα τον κώδικα του ερωτήματος 5 και το πήρε σωστό.
Άβαταρ μέλους
omeleta
Newbie
 
Δημοσιεύσεις: 5
Εγγραφή: 23 Ιαν 2013, 17:42
Φοιτητής ΗΜΜΥ: Ναι

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό pefraimi » 04 Δεκ 2020, 19:35

Επισης πρεπει να φτιαξουμε και στιγμιοτυπο πχ new Stack;


Στην απάντησή σας θα υποβάλετε μόνο την υλοποίηση της κλάσης. Δεν
χρειάζεται να υποβάλετε κώδικα που θα χρησιμοποιεί την κλάση αυτή.
Αυτό θα γίνει αυτόματα από το Moodle.

Στον υπολογιστή μας όμως τοπικά καθώς αναπτύσσετε την κλάση καλό είναι
να φτιάξετε μια μέθοδο main που θα χρησιμοποιεί την κλάση για να δοκιμάσετε
τη λειτουργία της.
pefraimi
Sr. Member
 
Δημοσιεύσεις: 305
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό pefraimi » 04 Δεκ 2020, 20:00

Καλησπέρα, στο δεύτερο ερώτημα ο έλεγχος επιστρέφει πως παραβιάζεται το όριο συγκρίσεων, παρόλο που δεν υπάρχει.


Υπάρχει και στο δεύτερο ερώτημα περιορισμός στις συγκρίσεις, απλά είναι λιγότερο αυστηρός: O(n^2)
Θα γίνουν διορθώσεις στο κείμενο της εκφώνησης.
pefraimi
Sr. Member
 
Δημοσιεύσεις: 305
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό pefraimi » 04 Δεκ 2020, 20:03

Στο Ερώτημα 3 ζητάει αριθμό επαναλήψεων O(nlogn) ωστόσο ...
... μέχρι που έτρεξα τον κώδικα του ερωτήματος 5 και το πήρε σωστό.


Υπάρχουν περιορισμοί στις πράξεις που γίνονται πάνω στον πίνακα MyArray.
Θα γίνουν διορθώσεις στο κείμενο της εκφώνησης. Επίσης θα δούμε μήπως
μπορούν τα μηνύματα λάθους όταν παραβιάζονται τα όρια πολυπλοκότητας
να γίνουν πιο κατατοπιστικά.
pefraimi
Sr. Member
 
Δημοσιεύσεις: 305
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό pefraimi » 04 Δεκ 2020, 21:47

Έγιναν διορθώσεις και προσθήκες στις εκφωνήσεις και εμπλουτίστηκε ο κώδικας ελέγχου ώστε να δίνει μια ένδειξη για το είδος της υπέρβασης όταν παραβιάζονται τα όρια για την πολυπλοκότητα των αλγορίθμων. Ελπίζω να είναι καλύτερα τώρα, διαφορετικά να το δούμε ξανά.
pefraimi
Sr. Member
 
Δημοσιεύσεις: 305
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό KMoulakis30 » 05 Δεκ 2020, 18:12

Στο ερωτημα 4 χρησιμοποιώ binary search και μου βγαζει οτι ξεπερασα το οριο στο 2ο τεστ που εχει ενω στο 1ο τα περνα και τα δυο. Αφου δεν μπορουμε να χρησιμοποιησουμε την get από την MyArray δεν ξερω κάποιον πιο αποδοτικο αλγοριθμο συμφωνα με τις διαφάνειες του μαθηματος μηπως υπαρχει θεμα με την ασκηση και το υποερωτημα
KMoulakis30
Newbie
 
Δημοσιεύσεις: 2
Εγγραφή: 13 Δεκ 2016, 22:36

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό VlassisFa » 05 Δεκ 2020, 18:47

Καλησπέρα σας, στο ερώτημα 5 έχοντας ακολουθήσει τα βήματα των διαφανειών για ομοιόμορφη κατανομή μου βγάζει time limit exceeded. Μπορείτε να μου εξηγήσετε την σημασία της φράσης αυτής;
VlassisFa
Newbie
 
Δημοσιεύσεις: 1
Εγγραφή: 06 Φεβ 2020, 16:44

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό andreass » 05 Δεκ 2020, 19:05

VlassisFa έγραψε:Καλησπέρα σας, στο ερώτημα 5 έχοντας ακολουθήσει τα βήματα των διαφανειών για ομοιόμορφη κατανομή μου βγάζει time limit exceeded. Μπορείτε να μου εξηγήσετε την σημασία της φράσης αυτής;

Καλησπέρα, το πιθανότερο είναι πως έχεις μπεις σε κάποιο infinite loop. Έλεγξε τι θα μπορούσες να αλλάξεις στο start, pivot και end γιατί εκεί πρέπει να γίνει η αλλαγή από τον κώδικα. Δες τον κώδικα από τις διαφάνειες του εργαστηρίου 5 για την Αναζήτηση Παρεμβολής.
andreass
Newbie
 
Δημοσιεύσεις: 23
Εγγραφή: 30 Ιουν 2012, 12:18

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό andreass » 05 Δεκ 2020, 19:20

KMoulakis30 έγραψε:Στο ερωτημα 4 χρησιμοποιώ binary search και μου βγαζει οτι ξεπερασα το οριο στο 2ο τεστ που εχει ενω στο 1ο τα περνα και τα δυο. Αφου δεν μπορουμε να χρησιμοποιησουμε την get από την MyArray δεν ξερω κάποιον πιο αποδοτικο αλγοριθμο συμφωνα με τις διαφάνειες του μαθηματος μηπως υπαρχει θεμα με την ασκηση και το υποερωτημα


Έλεγξε αν ο αλγόριθμός σου παρότι είναι σωστός χρησιμοποιεί χωρίς λόγο παραπάνω φορές την compToValue. Θέλουμε ο κώδικας να είναι όσο πιο αποδοτικός γίνεται γιαυτό πρέπει να κάνετε τους λιγότερους δυνατούς ελέγχους. Για να δώσω ένα hint η χρήση της μέσα στην while πρέπει να γίνεται μια φορά. Αν θέλουμε να την ξαναχρησιμοποιήσουμε την αποθηκεύουμε σε μια μεταβλητή ;)
andreass
Newbie
 
Δημοσιεύσεις: 23
Εγγραφή: 30 Ιουν 2012, 12:18

Re: Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Εργασία 2

Δημοσίευσηαπό Aggelos_Kav » 06 Δεκ 2020, 22:46

γεια σας εχω ενα προβλημα,ενω στον υπολογιστη μου στην ασκηση 3 δουλευει κανονικα οταν την παραδεινω λεει οτι δεν κανει sort τον πινακα και και αποτυχαινει καποια κρυφα τεστ,εχετε καμια ιδεα να μοθ προτεινετε?(κανει sort στον υπολογιστη δεν κανει στην παραδωση ονλαιν)
Aggelos_Kav
Newbie
 
Δημοσιεύσεις: 2
Εγγραφή: 06 Δεκ 2020, 20:45

Επόμενο

Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες