Laskuharjoitukset
Pisteet
Laskuharjoitusaktiivisuudesta voi saada lisäpisteitä tenttiin.
Tentissä on 5 tehtävää, joista kustakin voi saada
6 pistettä. Laskuharjoituksista voi lisäksi saada maksimissaan
4 tenttipistettä. Laskuharjoitustehtäviä on
yhteensä n. 50-60 kappaletta (10-12 viikottaista kierrosta), joista
tenttipisteitä saa siten, että vähintään
- 30% tehtävistä tehneet saavat 1 tenttipisteen,
- 45% tehtävistä tehneet saavat 2 tenttipistettä,
- 60% tehtävistä tehneet saavat 3 tenttipistettä ja
- 75% tehtävistä tehneet saavat 4 tenttipistettä.
Tehtävästä saa yhden laskuharjoituspisteen, jos
- on ratkaissut tehtävän ennen sen käsittelyä ja
- on valmis puolustamaan ratkaisuaan laskuharjoituksissa.
Tehtävät
Laskuharjoituspapereita jaetaan luennoilla ja harjoituksissa.
Paperin saa myös täältä (postscript muodossa).
-
Harjoitus 1:
23.9.1998; perusteet: analyysin perusteet ja kertausta
-
Harjoitus 2:
30.9.1998; perusteet: verkot
-
Harjoitus 3:
7.10.1998; perusteet: verkot; rekursioyhtälöt
-
Harjoitus 4:
14.10.1998; perusteet: pahimman tapauksen ja tasoitettu aikavaatimus
-
Harjoitus 5:
21.10.1998; perusteet: mukautuvat puut (splay-puut)
-
Harjoitus 6:
28.10.1998; suunnittelutekniikoita: hajoita ja hallitse; dynaaminen ohjelmointi
-
Harjoitus 7:
4.11.1998; suunnittelutekniikoita: karsintamenetelmä; pyyhkäisyviiva-algoritmit
-
Harjoitus 8:
11.11.1998; optimointiongelmat: verkon minimaalinen virittävä puu
-
Harjoitus 9:
18.11.1998; optimointiongelmat: binomikeot, Fibonaccikeot, vasemmalle kallistuvat puut
-
Harjoitus 10:
25.11.1998; optimointiongelmat: Kruskalin algoritmi, union-find rakenteet
-
Harjoitus 11:
2.12.1998; optimointiongelmat: branch-and-bound, aproksimointi
Kertyneet pisteet
-
Kotitehtävien
pisteet (kierrokset 1 - 11).
Viimeksi päivitetty 2.12.1998, Ari Korhonen,
archie@cs.hut.fi.
URL: http://www.cs.hut.fi/~archie/ASA/harjoitukset.html