Projektowanie i Analiza Algorytmów

• projekt 1
• projekt 2
• projekt 3
• projekt 4
• projekt 5 i 6

Dotychczasowa punktacja, grupy p. Kusznera

• Ostateczna punktacja za projekt tutaj Reklamacje poprzez e-mail do czwartku do godz. 11, lub pok. 209 czwartek godz. 11-12.
• Punktacja za aktualnie sprawdzone sprawozdania, sprawdziany i punkty dodatkowe na dzien 10 czerwca, godz. 16:30 : tutaj. Aktualizacja w rankingu SPOJ potrwa do godz 18.
• Punktacja za sprawozdanie 1, sprawdzian i punkty dodatkowe na dzien 1 czerwca: tutaj.

Projekty 5 i 6 (TRCTARCH i ostatni)

Sprawdzian (10 pkt)

Algorytmy grafowe

• Przeszukiwanie DFS i BFS
• Algorytm Dijkstry
• Algorytm Floyda-Warshalla
• Algorytm 6-kolorowania grafów planarnych (SL)

Drzewa BDW, AVL i RB

• Kolejności: preorder, inorder, postorer
• Operacje wstawiania, wyszukiwania, usuwania i rotacji
• Złożoność czasowa powyższych operacji
• Minimalna i maksymalna liczba elementów w drzewach o zadanej wysokości

Projekt 4 (PL6COL)

Sprawozdanie - ocena elementów kodu cz. III

Sprawozdania należy sporządzić w grupach 2 - 3 osobowych.

Wszyscy członkowie grupy muszą mieć zaliczone zadanie w systemie SPOJ i należeć do tej samej grupy projektowej.

W ramach grupy każda z osób powinna zapoznać się z kodem napisanym przez inną osobę i ocenić elementy jakości kodu.

Sprawozdanie powinno zawierać:

1. Dane identyfikacyjne
   1. Termin zajęć projektowych z PiAA, nazwisko osoby prowadzącej projekt
   2. Dane autora sprawozdania: Imię i Nazwisko oraz login w SPOJ'u.
   3. Dane autora ocenianego kodu: Imię i Nazwisko oraz login w SPOJ'u.
   4. Numer zgłoszenia w SPOJ'u zadania projektowego(ID zgłoszenia ze statusem Accepted.)
   5. Numer zgłoszenia zadania PALxx05
   6. Wydruk ocenianego programu w możliwie zwartej formie(proszę nie produkować zbędnej makulatury).
2. Listę dostrzeżonych błędów i niedociągnięć w programie. Ocenę należy przeprowadzić pod kątem poprawności kodu i efektywności zaproponowanego algorytmu. Należy uwzględnić zamieszczone poniżej elementy(nie więcej niż 1 strona tekstu):
   1. Zgodność z warunkami zadania, czy i w jakich sytuacjach program może nie zadziałać poprawnie?
   2. Efektywność (czas działania) zastosowanego algorytmu, czy i jaki algorytm byłby szybszy?
   3. Efektywność konstrukcji programistycznych, co i jak można poprawić, aby przyśpieszyć działanie programu?

Punktacja:

• Jakość kodu przedstawionego do oceny (max. 2pkt.)
• Jakość sporządzonej oceny (max. 3pkt.)

Projekt 3 (FOSS)

Sprawozdanie - ocena elementów kodu cz. II

Sprawozdania należy sporządzić w grupach 2 - 3 osobowych.

Wszyscy członkowie grupy muszą mieć zaliczone zadanie w systemie SPOJ i należeć do tej samej grupy projektowej.

W ramach grupy każda z osób powinna zapoznać się z kodem napisanym przez inną osobę i ocenić elementy jakości kodu.

Sprawozdanie powinno zawierać:

1. Dane identyfikacyjne
   1. Termin zajęć projektowych z PiAA, nazwisko osoby prowadzącej projekt
   2. Dane autora sprawozdania: Imię i Nazwisko oraz login w SPOJ'u.
   3. Dane autora ocenianego kodu: Imię i Nazwisko oraz login w SPOJ'u.
   4. Numer zgłoszenia w SPOJ'u zadania projektowego(ID zgłoszenia ze statusem Accepted.)
   5. Numer zgłoszenia zadania PALxx05
   6. Wydruk ocenianego programu w możliwie zwartej formie(proszę nie produkować zbędnej makulatury).
2. Listę dostrzeżonych błędów i niedociągnięć w strukturze programu. Każda wskazana usterka musi być w czytelny sposób poparta kilkoma odwołaniami do ocenianego programu. Ocenę należy przeprowadzić pod kątem modyfikowalności kodu i możliwości ponownego użycia jego fragmentów. Należy uwzględnić zamieszczone poniżej elementy(nie więcej niż 1 strona tekstu):
   1. Możliwe problemy przy zmianie warunków zadania (konsekwentne stosowanie stałych, itp.)
   2. Zgodność kodu ze standardami np. ANSI: ISO/IEC 9899:1990, POSIX:ISO/IEC 9945.
   3. Możliwe problemy przy przenoszeniu kodu na inną platformę lub kompilator (rozmiar i zakres stosowanych typów liczbowych, kodowanie znaków, itp.)
   4. Możliwe problemy przy adaptacji kodu do innego zadania.

Punktacja:

• Jakość kodu przedstawionego do oceny (max. 2pkt.)
• Jakość sporządzonej oceny (max. 3pkt.)

Projekt 2 (TDSU)

Sprawozdanie - ocena elementów kodu

Sprawozdania należy sporządzić w grupach 2 - 3 osobowych.

Wszyscy członkowie grupy muszą mieć zaliczone zadanie w systemie SPOJ i należeć do tej samej grupy projektowej.

W ramach grupy każda z osób powinna zapoznać się z kodem napisanym przez inną osobę i ocenić elementy jakości kodu.

Sprawozdanie powinno zawierać:

1. Dane identyfikacyjne
   1. Termin zajęć projektowych z PiAA, nazwisko osoby prowadzącej projekt
   2. Dane autora sprawozdania: Imię i Nazwisko oraz login w SPOJ'u.
   3. Dane autora ocenianego kodu: Imię i Nazwisko oraz login w SPOJ'u.
   4. Numer zgłoszenia w SPOJ'u. (ID zgłoszenia ze statusem Accepted.)
   5. Wydruk ocenianego programu w możliwie zwartej formie(proszę nie produkować zbędnej makulatury).
2. Listę dostrzeżonych błędów i niedociągnięć w strukturze programu. Każda wskazana usterka musi być w czytelny sposób poparta kilkoma odwołaniami do ocenianego programu. Ocenę należy przeprowadzić pod kątem czytelności i łatwości zrozumienia uwzględniając zamieszczone poniżej elementy(nie więcej niż 1 strona tekstu):
   1. Czytelność kodu: stosowanie wcięć, prototypów funkcji, (nie)stosowanie zawiłych konstrukcji.
   2. Spójność konwencji umieszczania kodu np: puste linie między funkcjami, położenie nawiasów klamrowych.
   3. Logiczny podział programu na funkcje.
   4. Stosowanie stałych.
   5. Stosowanie komentarzy, w tym komentarza nagłówkowego.
   6. Czytelność i zrozumiałość komentarzy.
   7. Spójność stylu pisania komentarzy.
   8. Adekwatność stosowanych nazw dla funkcji, stałych i zmiennych.
   9. Spójność przyjętej konwencji nazywania.

Punktacja:

• Jakość kodu przedstawionego do oceny (max. 2pkt.)
• Jakość sporządzonej oceny (max. 3pkt.)

Projekt 1 (TFRACAL)

Sprawozdanie (1pkt)

Sprawozdanie powinno zawierać opis struktur danych użytych w programie, max. jedna strona A4.

Sprawdzian (4 pkt)

Zadania przygotowawcze do sprawdzianu

Zadanie 1

Zbuduj wyrażenie w postaci ONP dla następujących wyrażeń:

1. a-b*c+d-e*f+g*h
2. 2-(a*3-(4+a*c-b))

Zadanie 2

1. xy-xyx--y--
2. 1234a/b/-c/--

Zasdanie 3

#include<assert.h>
#include<stdio.h>

int nwd(int a, int b){
  assert(a>=b);
  assert(b>=0);
  if (a==b||b==0) return a;
  return nwd(b,a%b);
}
int main(){
  printf("%d\n",nwd(126,48));
  return 0;
}

Zadanie 4

1. (1,4,2,5,3)
2. (1,2,4,7,6,5,3)

Zadanie 5

Zadanie 6

1. n=12121 c=3 x=5
2. n=AB c=13 x=2
3. n=1000101 c=2 x=21

Zadanie 7

Zadanie 8

struct P{
  int v;
  struct P*next;
} A;

int T[2][3];

void fun1(){
  int *p=(int*)T;
  *p=5;
  *(p+3)=10;
  /* podaj zawartosc T */
}


void fun2(){
  int *w[3]=T;
  w[1][2]=10;
  /* podaj zawartosc T */
}

void fun3(){
  int (*w)[3]=T;
  w[1][2]=10;
  /* podaj zawartosc T */
}

void fun4(){
  struct P* w=(struct P*)malloc(sizeof(struct P));

  w->next=&A;
  w->next->next=NULL;
  w->next->v=9;
  w->v=10;
  /* co zawiera A i w ? */

}

void fun4(){
  struct P* w=(struct P*)malloc(sizeof(struct P));

  w->next=A;
  w->next.next=NULL;
  w->next.v=9;
  w->v=10;
  /* co zawiera A i w ? */

}

void fun5(){
  struct P* w=(struct P*)malloc(sizeof(struct P));

  P->next=A;
  P->v=5;
  A.next=NULL;
  A.v=9;
  
  /* co zawiera A i P ? */
}

void fun6(){
  struct P* w=(struct P*)malloc(sizeof(struct P));

  w->next=&A;
  w->v=5;
  A->next=NULL;
  A->v=9;
  
  /* co zawiera A i w ? */
}


void fun7(){
  struct P* w=(struct P*)malloc(sizeof(struct P));

  w->next=&A;
  w->v=5;
  A.next=NULL;
  A.v=9;
  
  /* co zawiera A i w ? */
}


void fun8(){
  struct P* w=(struct P*)malloc(sizeof(struct P));

  w->next=&A;
  w->v=5;
  A->next=NULL;
  A->v=9;
  
  /* co zawiera A i w ? */
}

Odpowiedzi do zadań

Zadanie 1

1. abc*-d+ef*-gh*+
2. 2a3*4ac*+b---

Zadanie 2

1. (x-y)-((x-(y-x))-y)
2. 1-(2-(3-(4/a)/b)/c)

Zadanie 7