\documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage[greek,english]{babel} \usepackage[scaled]{helvet} \usepackage{alphabeta} \usepackage{amsmath} \usepackage{fancyhdr} \pagestyle{fancy} \fancyhf{} \fancyhead[L]{\nouppercase{\leftmark}} \fancyhead[C]{Εργασία Δομών Δεδομένων} \fancyhead[R]{\thepage} \fancyfoot[C]{} \addto\captionsgreek{ \renewcommand{\contentsname}{Περιεχόμενα} } \title{Φύλλο εργασίας 1} \author{ΝΤΕΝΤΑΪ ΜΕΪΓΚΑΝ 12509 ΚΑΙ ΒΙΡΓΙΝΙΑ ΓΚΕΝΟΥΔΗ 12632} \date{\today} \begin{document} \maketitle \tableofcontents \newpage \section{Άσκηση 1} \subsection*{(i) Απόδειξη ότι $n^2 + 3n \in O(n^2)$} Έχουμε: \[ n^2 + 3n \leq n^2 + 3n^2 = 4n^2, \quad \text{για κάθε } n \geq 1 \] Άρα, επιλέγοντας $c = 4$ και $n_0 = 1$, ισχύει: \[ n^2 + 3n \leq 4n^2 \] Άρα: \[ n^2 + 3n \in O(n^2) \] \subsection*{(ii) Απόδειξη ότι $2^n \in \omega(n^{10})$} Υπολογίζουμε: \[ \lim_{n \to \infty} \frac{n^{10}}{2^n} = 0 \] Άρα: \[ 2^n \in \omega(n^{10}) \] \subsection*{(iii) Απόδειξη ότι $n\log n \in O(n^{3/2})$} Για μεγάλα $n$ ισχύει: \[ \log n \leq n^{0.5} \] Άρα: \[ n\log n \leq n^{1.5} \] Άρα: \[ n\log n \in O(n^{3/2}) \] \subsection*{(iv) Απόδειξη ότι $n^5 + 2n^3 \in \Omega(n^5)$} Για κάθε $n \geq 1$ ισχύει: \[ n^5 + 2n^3 \geq n^5 \] Άρα: \[ n^5 + 2n^3 \in \Omega(n^5) \] \subsection*{(v) Ταξινόμηση συναρτήσεων} Η κατάταξη από τη λιγότερο αποδοτική (μεγαλύτερη αύξηση) προς την περισσότερο αποδοτική (μικρότερη αύξηση) είναι: \begin{enumerate} \item $n!$ \item $2^{n/2}$ \item $n^{\log n}$ \item $e^{\sqrt{n}}$ \item $n^3 + n^2$ \item $n^2 \log n$ \item $10n$ \item $\sqrt{n}$ \item $\log^3 n$ \item $\log n$ \end{enumerate} \newpage \section{Άσκηση 2} Μια ακολουθία $A$ περιέχει $n-2$ μοναδικούς ακεραίους στο διάστημα $[0, n-1]$. Θέλουμε να βρούμε τους δύο αριθμούς που λείπουν, σε $O(n)$ χρόνο και με $O(1)$ επιπλέον χώρο. \subsection*{Ιδέα} Αν είχαμε όλους τους αριθμούς από $0$ έως $n-1$, το συνολικό άθροισμά τους θα ήταν: \[ S = \frac{n(n-1)}{2} \] και το συνολικό άθροισμα των τετραγώνων τους: \[ S_2 = \frac{(n-1)n(2n-1)}{6} \] Υπολογίζοντας: \begin{itemize} \item το άθροισμα των στοιχείων της ακολουθίας $A$ (έστω $S_A$), \item και το άθροισμα των τετραγώνων των στοιχείων της $A$ (έστω $S_{A2}$), \end{itemize} προκύπτει: \[ x + y = S - S_A \] \[ x^2 + y^2 = S_2 - S_{A2} \] όπου $x$ και $y$ οι δύο χαμένοι αριθμοί. \subsection*{Επίλυση} Χρησιμοποιούμε την ταυτότητα: \[ (x+y)^2 = x^2 + y^2 + 2xy \] Άρα: \[ 2xy = (x+y)^2 - (x^2 + y^2) \] οπότε υπολογίζουμε το $xy$. Έχοντας $x+y$ και $xy$, λύνουμε τη δευτεροβάθμια εξίσωση: \[ t^2 - (x+y)t + xy = 0 \] Οι δύο ρίζες της εξίσωσης είναι οι δύο χαμένοι αριθμοί. \subsection*{Χαρακτηριστικά} \begin{itemize} \item Ο αλγόριθμος έχει χρόνο εκτέλεσης $O(n)$. \item Ο αλγόριθμος χρησιμοποιεί $O(1)$ πρόσθετο χώρο. \end{itemize} \newpage \section{Άσκηση 3} Έστω $n$ διεργασίες και ένας αριθμός $k$ τέτοιος ώστε $1 < k < n$. Το κόστος της $i$-οστής διεργασίας είναι: \begin{itemize} \item $k$, αν το $i$ είναι πολλαπλάσιο του $k$ \item $1$, διαφορετικά \end{itemize} \subsection*{Απόδειξη ότι το συνολικό κόστος είναι $O(n)$} Οι διεργασίες που έχουν κόστος $k$ είναι όσες είναι πολλαπλάσια του $k$. Ο αριθμός τους είναι περίπου $n/k$. Οι υπόλοιπες διεργασίες έχουν κόστος $1$, και είναι περίπου $n - n/k$. Το συνολικό κόστος υπολογίζεται ως: \[ \text{Συνολικό Κόστος} = (n - n/k) \times 1 + (n/k) \times k \] Αναπτύσσοντας: \[ = n - \frac{n}{k} + n \] \[ = n(2 - \frac{1}{k}) \] Επειδή το $k > 1$, το $\frac{1}{k}$ είναι μικρό και άρα $2 - \frac{1}{k} \approx 2$. Άρα: \[ \text{Συνολικό Κόστος} = O(n) \] \subsection*{Επιμερισμένο κόστος ανά διεργασία} Το επιμερισμένο κόστος ανά διεργασία είναι: \[ \text{Επιμερισμένο Κόστος} = \frac{\text{Συνολικό Κόστος}}{n} = 2 - \frac{1}{k} \] Άρα το επιμερισμένο κόστος είναι σταθερό: \[ O(1) \] \textbf{Συμπέρασμα:} Το συνολικό κόστος είναι $O(n)$ και το επιμερισμένο κόστος ανά διεργασία είναι $O(1)$. \newpage \documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage[greek]{babel} \usepackage[scaled]{helvet} \usepackage{alphabeta} \usepackage{fancyhdr} \pagestyle{fancy} \fancyhf{} \fancyhead[L]{\nouppercase{\leftmark}} \fancyhead[C]{Εργασία Δομών Δεδομένων} \fancyhead[R]{\thepage} \fancyfoot[C]{} \addto\captionsgreek{% \renewcommand{\contentsname}{Περιεχόμενα} } \title{Εργασία Δομών Δεδομένων} \author{} \date{} \begin{document} \maketitle \tableofcontents \newpage \section{Άσκηση 4} \subsection{Συνάρτηση areEqual(listA, listB)} \begin{itemize} \item Αν το μέγεθος των λιστών είναι διαφορετικό, επιστρέφει false. \item Αλλιώς, ξεκινά ταυτόχρονα από το πρώτο στοιχείο και των δύο λιστών. \item Για κάθε στοιχείο: \begin{itemize} \item Αν τα στοιχεία διαφέρουν, επιστρέφει false. \item Πηγαίνει στο επόμενο στοιχείο και στις δύο λίστες. \end{itemize} \item Αν ολοκληρώσει τη σύγκριση χωρίς λάθος, επιστρέφει true. \end{itemize} \subsection{Συνάρτηση isSymmetric(list)} \begin{itemize} \item Θέτει δύο δείκτες: έναν στην αρχή (head) και έναν στο τέλος (tail) της λίστας. \item Όσο οι δείκτες δεν συναντιούνται: \begin{itemize} \item Αν τα στοιχεία που δείχνουν οι δείκτες είναι διαφορετικά, επιστρέφει false. \item Διαφορετικά, ο head πηγαίνει στο επόμενο στοιχείο και ο tail στο προηγούμενο στοιχείο. \end{itemize} \item Αν όλοι οι έλεγχοι περάσουν, επιστρέφει true. \end{itemize} \newpage \section{Άσκηση 5} \subsection{Συνάρτηση isBalanced(node)} \begin{itemize} \item Αν ο κόμβος είναι null, επιστρέφει 0. \item Υπολογίζει το ύψος του αριστερού υποδέντρου. \item Αν αυτό επιστρέψει -1, επιστρέφει -1. \item Υπολογίζει το ύψος του δεξιού υποδέντρου. \item Αν αυτό επιστρέψει -1, επιστρέφει -1. \item Αν η διαφορά των υψών είναι μεγαλύτερη από 1, επιστρέφει -1. \item Αλλιώς επιστρέφει το μέγιστο ύψος των δύο υποδέντρων συν 1. \end{itemize} Η συνάρτηση isBalanced επιστρέφει true αν το αποτέλεσμα της checkHeight είναι διαφορετικό από -1. \subsection{Συνάρτηση isSymmetric(root)} \begin{itemize} \item Αν η ρίζα είναι null, επιστρέφει true. \item Αλλιώς, καλεί τη isMirror(left, right). \item Η isMirror(t1, t2) λειτουργεί ως εξής: \begin{itemize} \item Αν και τα δύο είναι null, επιστρέφει true. \item Αν μόνο το ένα είναι null, επιστρέφει false. \item Αν οι τιμές τους είναι διαφορετικές, επιστρέφει false. \item Αλλιώς, ελέγχει: \begin{itemize} \item isMirror(t1.left, t2.right) \item isMirror(t1.right, t2.left) \end{itemize} \end{itemize} \end{itemize} \end{document}