Informatyka UJ forum

AMD · pijak Dołączył: 05 Mar 2006 Posty: 161 Przeczytał: 0 tematów

Zakłdam ten temat żeby kazdy kto cos wie o formie lub czasie i miejscu tego warunku napisał to co wie

zaq

Żeby nie zakładać nowego tematu, napiszę tutaj:
Czy ktoś uprzejmy mógłby napisać jak rozwiązać zad. 4 z I kolokwium?
Przypominam treść:

Skonstruuj algorytm, który pozwala posortować n liczb całkowitych z przedziału [0...n^2 - 1] w czasie O(n).

Będę wdzięczny nawet za ideę rozwiązania.

krzycho

z tego co pamietam to byl zwykly radixsort

maniek

a moze ktos walnac rozwiazania zadaniek z kolosa poprawkowego - niby dali wskazowki i jak to rowziwazac ale chcoialbym sie upewnic czy to dobrze zapisyałe : )
z góry dzikekuje

Turalyon

zaq - to byl radixsort, przy czym te liczby zapisywales n-arnie, za pomoca dwu cyfr z przedzialu [0..n-1]. Wtedy radix sprowadzal sie do dwu countingsortow, kazdy o zlozonosci O(n).

Prezioso

Termin i miejsce są już ustalone... są też dodatkowe wymagania...

cinnahmon

nie do końca rozumiem
zy dobrze rozkmiliłem, że jesli brakuje mi tylko egzaminu to drugi podpunkt mnie nie dotyczy :>???

Spectro

@cinnahmon:
Tak. Punkt drugi dotyczy, o ile się orientuję, zaledwie 2 osób.

Pandunia · Gość

[deleted]

Yoter

1. przy założeniu że m > n będzie to m lg n, ponieważ m razy poprawiamy odległości (dla wszystkich krawędzi wychodzących z danego wierzchołka o ile nie prowadzą do wierzchołków które już dodalismy do drzewa) a przy każdej poprawce musimy przesiać kopiec, stąd lg n...
2. lg n znowu z przesiewania kopca, m razy usuwamy element więc trzeba przesiać... (n < m bo nie trzymamy wszystkich elementów ciągów w kopcu, tylko z każdego co najwyżej jeden)...

mam nadzieję że się nigdzie nie rąbnąłem... jak coś to poprawiać....

mateo

ad 1. A Prima nie mozna na kopcu fibonacciego zrobic?? wtedy jest przeciez nlgn

Yoter

można...

Pandunia · Gość

[deleted]

AMD · pijak Dołączył: 05 Mar 2006 Posty: 161 Przeczytał: 0 tematów

Dzisiaj jest z pewnoscią ostatni(realny) dzien na tej uczelni dla kilku z nas.

dzendras

@AMD: nawet mnie k*** nie denerwuj :)

Fen

powodzenia życzę na poprawce!!!!

trzymajcie się i żeby mi nikt z Was nie odpadł!!!

będzie dobrze :)

Ethlinn

macie blogoslawienstwo Chucka...

Trzymam mocno kciuki

Skrobocik

AMD · pijak Dołączył: 05 Mar 2006 Posty: 161 Przeczytał: 0 tematów

Juz po egzaminie
zadania były ciezkie jak na egzamin(przynajmniej dla mnie)
zapewne niestety nie uda mi sie dostac do grona szczesliwcow którzy zdadzą
Wyniki w poniedziałek

Stasiu

gratulacje dla tych co zdali :) ... i powodzenia tym, którym się nie udało :(

Yoter

gratki...

ZenonZajebich

Miło się słucha dzendrasa śpiewającego "We Are The Champions" :)
Z drugiej strony ciężko sobie zdać sprawę z tego, że tak nas mało już zostało... :\

Stasiu

@Zenon: nie dramatyzuj ;) probably_the_best_grill jeszcze ma uzytkownikow ;)
Ale trzeba przyznać, że paru osób brakuje i jakoś pusto na tych wykładach (pomijając fakt, że częśc z nas nie chce się na nie chodzić) ;p

Skrobocik

Gratulacje ludziki ;)

Fen

na 16 osób tylko 6 zdało ;/ myślałem, że Śluman da trochę łatwiejsze zadania... szkoda