Zapoznać się z metodami z bilblioteki http://en.cppreference.com/w/cpp/algorithm. Dla każdej z metod jest w dokumentacji podany przykład użycia kodu.

W przypadku modyfikowania niezainicjalizowanego kontenera może się przydać http://en.cppreference.com/w/cpp/iterator/back_inserter

1. [7 plusów] Przy pomocy algorytmów znajdujących się w bibliotece algorithm należy zaimplementować następujące metody (kolejność przypadkowa):

  std::set<std::string> Keys(const std::map<std::string, int> &m);
  std::vector<int> Values(const std::map<std::string, int> &m);
  std::map<std::string, int> DivisableBy(const std::map<std::string, int> &m,int divisor);
  void SortInPlace(std::vector<int> *v);
  std::vector<int> Sort(const std::vector<int> &v);
  void SortByFirstInPlace(std::vector<std::pair<int,int>> *v);
  void SortBySecondInPlace(std::vector<std::pair<int,int>> *v);
  void SortByThirdInPlace(std::vector<std::tuple<int,int,int>> *v);
  std::vector<std::string> MapToString(const std::vector<double> &v);
  std::string Join(const std::string &joiner, const std::vector<double> &v);
  int Sum(const std::vector<int> &v);
  int Product(const std::vector<int> &v);
  bool Contains(const std::vector<int> &v, int element);
  bool ContainsKey(const std::map<std::string, int> &v, const std::string &key);
  bool ContainsValue(const std::map<std::string, int> &v, int value);
  std::vector<std::string> RemoveDuplicates(const std::vector<std::string> &v);
  void RemoveDuplicatesInPlace(std::vector<std::string> *v);
  void InitializeWith(int initial_value, std::vector<int> *v);
  std::vector<int> InitializedVectorOfLength(int length, int initial_value);
  void CopyInto(const std::vector<int> &v, int n_elements, std::vector<int> *out);
  int HowManyShortStrings(const std::vector<std::string> &v, int inclusive_short_length);
 

1. [5 punktów] Zadanie polega na dodaniu do aplikacji Academia możliwości układania harmonogramu zajęć uwzględniającego różne ograniczenia. W podstawowej wersji należy jedynie uwzględnić brak bilokacji (i multilokacji) studentów z danego roku i nauczycieli akademickich. Zajęcia również w danym oknie czasowym i w danej sali mogą się odbywać tylko jedne zajęcia. Każdy nauczyciel musi poprowadzić określoną listę przedmiotów. Ogólnie ułożenie optymalnego planu zadań jest zadaniem bardzo trudnym, dlatego prawdopodobnie algorytm będzie rozwijany miesiącami. Jednak zanim specjalny zespół od problemów optymalizacyjnych dostarczy wreszcie gotowe rozwiązanie chcielibyśmy mieć namiastkę działającego oprogramowania! Na szczęście jest to możliwe należy zdefiniować kontrakt w postaci interfejsu Scheduler specjalny zespół dostarczy nam za kilka miesięcy algorytm SophisticatedHighlyOptimizedScheduler, a my możemy już napisać bardzo uproszczony algorytm zachłanny, który będzie dostarczał często nieoptymalne wyniki, ale na razie wystarczy. Należy więc przygotować klasy:
   1. SchedulingItem pojedynczy element harmonogramu, obiekt wartości, zawiera pola:
      1. course_id - identyfikator kursu
      2. teacher_id - identyfikator nauczyciela akademickiego prowadzącego te zajęcia o tej godzinie
      3. room_id - identyfikator pomieszczenia w którym odbywają się zajęcia
      4. time_slot - okno czasowe, w którym odbywają się zajęcia, dla uproszczenia cały tydzień jest podzielony na N okien czasowych nie zachodzących na siebie (np. dla 20: 1 ⇒ pon 8:00-10:00, 2 ⇒ pon 10:00-12:00, … 20 ⇒ pią 14:00-16:00). Zajęcia wymagają zawsze pojedynczego okna czasowego i zawsze są z nim wyrównane tzn. nie mogą zajmować połowę 12ego i połowę 13ego
      5. year - rok studiów na którym obowiązuje przedmiot
   2. Schedule cały harmonogram, udostępnia następujące metody:
      1. Schedule OfTeacher(int teacher_id) const - wylicza fragment harmonogramu związany z danym nauczycielem akademickim (może się przydać copy_if…)
      2. Schedule OfRoom(int room_id) const - j.w. tylko związany z danym pomieszczeniem
      3. Schedule OfYear(int year) const - j.w. dla danego roku studiów
      4. std::vector<int> AvailableTimeSlots(int n_time_slots) const - wylicza wektor jeszcze nie zajętych okien czasowych, gdzie n_time_slots jest maksymalną wartością okna czasowego
      5. void InsertScheduleItem(const SchedulingItem &item) - wstawia nowy element planu
      6. size_t Size() const - zwaraca rozmiar planu
   3. Scheduler najważniejszy element układacz planu, interfejs czysto abstrakcyjny stanowiący kontrakt między nami a zespołem pracującym nad zoptymalizowaną wersją algorytmu.
      1. Schedule PrepareNewSchedule(const std::vector<int> &rooms, const std::map<int, std::vector<int» &teacher_courses_assignment, const std::map<int, std::set<int» &courses_of_year, int n_time_slots)
         1. rooms - dostępne pomieszczenia
         2. teacher_courses_assignment - rozpiska nauczycieli (klucz w mapie) i prowadząnych przez nich przedmiotów (wartosć w mapie)
         3. courses_of_year - kursy (wartość w mapie) wymagane dla danego rocznika (klucz w mapie)
         4. n_time_slots - ilość slotów czasowych
   4. NoViableSolutionFound wyjątek wyrzucany, gdy nie udaje się stworzyć planu
   5. GreedyScheduler wersja zachłanna implentacji algorytmu układacza planu zwykła pętla która próbuje przypisywać po kolei przedmioty do sal i nauczycieli