Εκφώνηση: https://k08.chatzi.org/projects/project2/

Όνομα: ΕΡΙΚ ΚΑΓΙΑΤΣΚΑ

Α.Μ.: sdi2100043

• Ασκηση_1
• Ασκηση_2
• Ασκηση_3
  • Bonus_ασκ3
• Ασκηση_4
  • Bonus1_ασκ4

Ασκηση1

Η λειτουργια queue_remove_front εχει πολυπλοκοτητα Ο(n). Οι υπολοιπες λειτουργιες εχουν πολυπλοκοτητα O(1).

Ασκηση2

Η λειτουργια queue_remove_front, οταν η 2η στοιβα ειναι κενη, εχει πολυπλοκοτητα Ο(n) επειδη γινεται αντιγραφη ολων των στοιχειων απο την 1η στη 2η στοιβα. Οταν υπαρχουν στοιχεια στη 2η στοιβα, αφαιρειται το στοιχειο στην κορυφη, οποτε εχει πολυπλοκοτητα Ο(1). Επομενως, μπορουμε να πουμε οτι η υλοποιηση ADTQueue_alt ειναι πιο αποδοτικη οσων αφορα την λειτουργια queue_remove_front.

Ασκηση3

GRAPHS: QUEUE_BENCHMARK_USING_LIST:

1. Πολυπλοκοτητα Ο(1)
2. Πολυπλοκοτητα Ο(1) QUEUE_BENCHMARK_USING_STACK:
3. Πολυπλοκοτητα Ο(n)
4. Πολυπλοκοτητα Ο(n) QUEUE_BENCHMARK_USING_STACK_ALT:
5. Πολυπλοκοτητα Ο(n) καθως και Ο(1), αναλογα την περιπτωση
6. Πολυπλοκοτητα Ο(1) VECTOR_BENCHMARK_USING_DYNAMIC_ARRAY:
7. Πολυπλοκοτητα Ο(1)
8. Πολυπλοκοτητα Ο(1)

Ασκηση4

Η λειτουργια set_create_from_sorted_values εχει γραμμικη πολυπλοκοτητα, το δεντρο που παραγει ειναι balanced. Επισης, τα επιπλεον τεστ, που ελεγχουν τις υπολοιπες λειτουργιες, δεν εμφανιζουν leaks.

Bonus1 Υπαρχει το προγραμμα /programs/set_benchmark/set_benchmark.c το οποιο κανει διαδoχικα inserts χρησιμοποιωντας την trivial υλοποιηση και την υλοποιηση που ζητουσε η ασκηση 4. Τα αποτελεσματα της καθε υλοποιησης εκτυπωνονται στα αντιστοιχα .csv αρχεια που υπαρχουν στο φακελο /programs/set_benchmark. To προγραμμα θα καλειται ως set_benchmark <type> οπου <type> = real | amortized SET_BENCHMARK_TRIVIAL:

1. Πολυπλοκοτητα Ο(1)
2. Πολυπλοκοτητα Ο(1) SET_BENCHMARK_USING_VectorToBST:
3. Πολυπλοκοτητα Ο(n) οσο αφορα την προσθηκη στοιχειων απο το Vector, O(1) χρησιμοποιωντας την set_insert();
4. Πολυπλοκοτητα Ο(n) οσο αφορα την προσθηκη στοιχειων απο το Vector, O(1) χρησιμοποιωντας την set_insert();