22 февруари - 28 февруари

Конспект по ДАА-практикум (за всички групи):

1. Запознаване с online judge системи и състезателното програмиране

2. Сортиране О(n^2) - bubble sort, selection sort, insertion sort.

Сортиране count sort

3. Сортиране О(nlgn) - quick sort, heap sort, merge sort

4. Binary search

5. Обхождане на непретеглени графи: DFS, BFS, топологично сортиране

6. Обхождане на претеглени графи: Dijkstra, Floyd, Ford-Bellman

7. Минимално покриващо дърво: Prim, Kruskal

8. Динамично програмиране

Упражнение 1:

Запознахме се с judge системата на http://judge.openfmi.net:9280/ (ако някой все още няма регистрация, ще е хубаво да си направи) и решавахме глупави задачки от там, за да свикнем с нея. Там ще бъдат публикувани всички домашни и контролни, които ще правим през семестъра,

Няколко важни неща:

1. В условието на всяка задача ще е описан строго форматът, в който се въвеждат входните данни и се извеждат изходните. Не слагайте подсещащи или уточняващи съобщения. Решенията се проверяват от компютър.
2. Изхода трябва да завършва с нов ред, за да бъде обработен правилно от проверяващата програма.
3. Оценяването на всяко решение става, чрез няколко (обикновено) 10 предварително зададени теста. Ако всички те минат успешно системата ще върне резултат от вида ok ok ok ok ok ... Ако на някой тест програмата ви даде грешен отговор системата ще върне wa (wrong answer).
4. При оценяването освен верността на изхода в тестовите случаи се проверява и:
• времето за изпълнение - ако е превишено системата ще върне tl (time limit)
• използвана памет - ако е превишена системата ще върне ml (memory limit)
5. Ако има грешка по време на изпълнението системата ще върне re (runtime error) - напр. ако барате извън масив или делите на нула. 
6. Ако има грешка по време на компилацията - ce (compilation error)

Друго

Тези правят периодично онлайн състезания (освен това ако имате добри резултати можете да сложите връзка към профила в CV-то си; дори е възможно досадните ейчш ари да ви налазят докато си решавате там)

• http://codeforces.com/
  
• https://www.topcoder.com/
  
• https://www.hackerrank.com/
  

За тренировка можете да ползвате:

• http://acm.timus.ru/ (тук има доста задачи, разделени по категории)
  
• https://arena.maycamp.com/ (задачки от български ученически състезания; Обърнете внимание, че това е арена, различна от нашата, на която ще правим контролни и домашни!)
• http://bgcoder.com/ 
  
• http://www.spoj.com/
  
• http://judge.openfmi.net:9080/spoj0/ (задачи от български студентски състезания по програмиране)
  
• https://projecteuler.net/ (по-математически ориентирани задачи)
  
• и още много други, за които не се сещам сега

Материали за подготовка:

Algorithms & Data Structures:
TopCoder algorithm tutorials
Introduction to Algorithms (Third Edition) - Cormen, Leiserson, Rivest
Програмиране =++Алгоритми - Преслав Наков, Панайот Добриков
Algorithms, 4th edition - Robert Sedgewick, Kevin Wayne
The Algorithm Design Manual, 2nd edition - Steven Skiena
The Art of Computer Programming - Donald Knuth

C:
C reference guide
The C book
C file handling commands
C and C++ tutorial 

C++:
C++ online reference
C++ FAQ lite
Thinking in C++ (Second Edition) - Bruce Eckel
The C++ Programming Language (Third Edition) - Bjarne Stroustrup

STL:
Standard Template Library Programmers Guide
STL online reference
C++ STL tutorial

Изключително полезен сайт: http://informatika.bg/. В раздела "Лекции" има голяма част от материала, който ще бъде преподаден по ДАА-практикум. Авторът се е стремил да изгражда интуиция у четящия, в резултат на което са се получили доста сполучливи лекции, по които можете да се подготвяте.