Tietorakenteet ja algoritmit 1

(Data Structures and Algorithms 1, 5 cr)

Loppukokeen tulokset ja kurssin arvosanat(xls-tiedosto, vain joensuu.fi)

HUOM: Kurssin loppukoe tiistaina 11.5. klo 14:15 - 16:15, salissa T2/D106

HUOM: Luennot tiistaina 4.5. salissa T2/106B

HUOM: Harjoitus 8 sisältää 2 tehtävää, jotka ovat X-tehtäviä. X-tehtävien palautus on 6.5. klo 16:00 mennessä ja ne käydään läpi luennoilla 10.5.

HUOM: 6.4. ei ole luentoja pääsiäisloman vuoksi

HUOM: loppukuulustelulla suoritettaessa: 1/3 harjoituksista tehtynä, yli 1/3 osan ylittävästä lasketaan bonuksia, pakollisten X-tehtävien pisteet lasketaan loppukokeen pisteisiin mukaan

HUOM: kurssilla on myös pakollisia X-harjoitustehtäviä, jotka pisteytetään ja ne lasketaan mukaan kurssin pisteisiin. Lisätietoa myöhemmin www-sivulla ja harjoituksissa kun se on ajankohtaista.

HUOM: ei harjoituksia 1.4. (kiirastorstai), korvaava aika ilmoitetaan myöhemmin

HUOM: Kurssi alkaa viikolla 11, ensimmäinen luento on siis 15.3.2010. Siirto tehty luennoitsijan työmatkan vuoksi.

HUOM: Maanantain luentoaika on muuttunut opinto-oppaassa ilmoitetusta kurssijärjestelyjen vuoksi.

HUOM: Luennot: ma 8-10, ti 14-16, sali Tiedepuistolla T2/D106

HUOM: Harjoitukset: to klo 8-10 ja to 12-14, sali TB179.

HUOM: ILMOITTAUTUMINEN WEBOODISSA

• Luennot 32 t, Harjoitukset 16 t
• Johdatus algoritmien vaativuuteen. Tietojenkäsittelyssä tavallisimmin käytetyt tietorakenteet ja niiden hyödyntäminen. Tietorakenteiden käyttäminen ja toteuttaminen Java-kielellä. Kirjallisuus: Cormen, Leiserson, Rivest: Introduction to Algorithms, Weiss: Data Structures and Algorithm Analysis in Java. Esitiedot: Ohjelmointi.

Kurssin asema

• aineopintojen pakollinen kurssi
• aineopintojen keskeisimpiä kursseja

• Kohtuullinen ohjelmointitaito Javalla.
• Kykyä ratkoa yksinkertaisia matemaattisia lauseita ja lausekkeita

• - Analyysin perusteet:
    * Algoritmien suunnittelu ja toteutusperiaatteista
    * aika- ja vaativuusanalyysi
    * paras, keskimääräinen, pahin tapaus
    * O, o, Omega, theta
    * kompleksisuusluokat
    * rekursiorelaatiot rekursiivisten alg. analyysissa (alustavasti)
  
  - Perustietorakenteet
    * Lista sukulaisineen
    * Puut
    * Joukot
    * Verkot (kevyesti)
  
  - Perusalgoritmeja
    * järjestämisalgoritmeista
      - (yksinkertaiset O(n^2) algoritmit (esim. kuplalajittelu) 
      - pikalajittelu, kasalajittelu, lomituslajittelu, kaukalolajittelu aikavaativuuksineen 
    * hajautus + törmäyksenvälttämisstrategiat
  
  - Perustietorakenteiden toteuttaminen
  

• Kurssin luennointikieli on Java-pohjainen algoritminotaatio (pseudokieli)
• Harjoitukset tehdään pääsääntöisesti Javalla käyttäen tietorakennekirjastoa apuna.

• Nostaa ohjelmien ja ohjelmoijien abstraktiotasoa!

• 15.3. -- 10.5.
  ma 8-10 T2/D106
  ti 14-16 T2/D106

• Ryhmä 1: to 8-10 T/B179
  Ryhmä 2: to 12-14 T/B179

  ---

  • Harjoitus 1 (18.3.)
  • Harjoitus 2 (25.3.)X1-tehtävän pohja
    HUOM: ei harjoituksia 1.4. (kiirastorstai), korvaava aika ilmoitetaan myöhemmin
  • Harjoitus 3 (8.4.) teht. 2-3 pohja ja teht 4-5 pohja ja malliratkaisut
    
  • Harjoitus 4 (15.4.)X2-tehtavan pohja ja malliratkaisut
    
  • Harjoitus 5 (22.4.) ja malliratkaisut
    
  • Harjoitus 6 (29.4.) ja malliratkaisut
    
  • Harjoitus 7 (6.5.), Pohjaksi Lajittelua.java ja malliratkaisut
    
  • Harjoitus 8 (kotitehtävänä, palautus 6.5. klo 16:00) X3-tehtävän pohja, X4-tehtävän pohja ja X4-tehtävän testausohjelma
    

  ---

• Kuplalajittelu
  
• Sulut
  
• PinoJono
  
• PuuEsim.java
  
• BinPuuEsim09.java
  
• Huomioikaa eri vertailut
  
• JoukkoEsimerkki.java
  
• Permutaatiot.java
  
• ArrayList.java
  
• ArrayLinkedList.java
  
• ArrayDoublyLinkedList.java
  
• DoubleLinkedList3.java
  
• DoubleLinkedList3Node.java
  

• Tiistaina 11.5. klo 14:15 - 16:15, salissa T2/D106
  
• Arvostelu: noin 40-50% pakollisista X-tehtävistä, loput loppukokeesta. Muista harjoituksista bonusta 1/3 ylittävästä osasta. Harjoituksista pakollista 1/3.

Kurssin palautteen voi antaa weboodissa. Ilmoitus tästä tulee sähköpostitse 12.5.

• 21.5.2010 ja 6.8.2010, katso tarkemmin laitoksen sivuilta kulustelujen kohdalta.

• javac, versio >= 1.5.0
  
• java 1.6 cs:llä: /usr/local/bin/java6c

• Harjoituksissa kirjastoa käytetään cs -koneella.
• Käyttö:
  kääntäminen: trajc Ohjelma.java
  • ajaminen: traj Ohjelma
• Yleisemmin (kun polku/tra.jar on paikka josta tra.jar löytyy)
  • kääntäminen: javac -cp polku/tra.jar:. Ohjelma.java
  • ajaminen: java -cp polku/tra.jar:. Ohjelma
  • Windowsissa : tilalla ehkä pitää olla ;
• Dokumentaatio online
• Tästä voit ladata kirjaston ja dokut:
  • Luokat sisältävä jar -paketti (35kt) (päivitetty viimeksi Wed Mar 18 14:25:01 EET 2009 , (korjattu TraLinkedList.find())
  • Luokat sisältävä jar -paketti (35kt) Jav a SE 1.6 versio.
    • Uudessa versiossa mukana verkot, lista totetuttaa Iterable:n, prioriteettijo nossa pieniä tyyppimuunnoksia, ListNode:n operaatioissa nimimuutoksia.
  • tra.jar:n ja Dokumentaation (HTML) sisältäv&aum l; zip -paketti (142kt) (2007 versio), ei sisällä yo 2008 korjauks ia.

• Liang: Introduction to Java Programming, comprehensive 7th edition
• Weiss: Data Structures and Algorithm Analysis [in C | Pascal | C++ | Java, | jne]
• Cormen, Leiserson, Rivest: Introduction to Algorithms
• Knuth: The Art of Computer Programming
• Luentomoniste, n. 100 sivua
  • Monistuskulut noin 5 euroa.