Dana jest tablica \(n \times n\), \(n > 1\), w której w każde pole wpisano liczbę całkowitą. Chcemy przejść z dolnego lewego rogu (z \( (1,1) \) ) do górnego prawego rogu (do \( (n,n) \) ) i wrócić, idąc w drodze z \( (1,1) \) zawsze w prawo lub w górę, a z powrotem - w lewo lub w dół. Z danego pola można przejść tylko na pola sąsiednie (współrzędne różnią się o 1 na dokładnie jednej pozycji). Żadne pole nie może się pojawić na całej trasie (czyli tam i z powrotem) więcej niż raz, poza polem (1,1), które pojawia się na początku i na końcu trasy. Zaprojektuj algorytm znajdowania najtańszej trasy, czyli takiej, na której suma wartości pól jest najmniejsza.
Niech \( n \) będzie liczbą całkowitą większą od 1, a \( X = \{ (x,y): x = 0, 1, \ldots, n-1, y = 0, 1, 2, 3, 4 \}\) zbiorem punktów na płaszczyźnie. Danych jest \( n \) różnych prostych, z których każda przechodzi przez dwa różne punkty ze zbioru \( X \), różniące się zawsze pierwszą współrzędną. Każda prosta zadana jest przez parę punktów \( [(x1,y1),(x2,y2)] \), \( x1 < x2 \). Zaprojektuj algorytm, który w czasie liniowym posortuje wszystkie proste niemalejąco względem ich kątów nachylenia do osi OX.
Podaj permutację liczb \( 1, 2, \ldots, 7 \), dla której algorytm HeapSort wykona największą liczbę porównań. Uwaga: należy wziąć pod uwagę obie fazy algorytmu – budowę kopca i właściwe sortowanie; poprawianie kopca odbywa się zawsze przez przesiewanie stosownego elementu w dół kopca; sortujemy rosnąco.
Uwaga: uzasadnij poprawność swoich rozwiązań oraz przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów; każde zadanie rozwiązujemy na oddzielnej kartce.