Двадцять друга лекція третього сезону відбудеться 29 березня о 18 годині у конференц-залі на третьому поверсі.
Лекцію ведуть: PostScriptum та LeBron.
Тема: Структури даних. Контейнери.
На порядку денному:
- Загальні поняття;
- Елементарні контейнери;
- Складність виконання основних операцій;
- Власна реалізація контейнерів.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearchRedBlack – червоно-чорні дерева
Дещо про STL :
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2
Cписок алгоритмів, описаних на ТopCoder’і.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index
Дякую за хороші лінки.
Якщо хтось надумає розбиратись з червоно-чорними деревами, то ще раджу главу про бінарні дерева пошуку в книжці Седжвіка “Фундаментальные алгоритмы на С++” – там все від елементарних дерев починається і закінчується навіть далі, ніж на червоно-чорних і написано досить доступно.
Не знаю, чого в статті на топкодері не сказано, що червоно-чорне дерево логічно є 2,3,4-деревом. Як на мене, це значно спрощує розуміння операцій різних зсувів. Ось коротка стаття по них:
http://en.wikipedia.org/wiki/2-3-4_tree
—————————–ДОМАШНЄ ЗАВДАННЯ————————————-
1. http://acm.timus.ru/problem.aspx?space=1&num=1220
2. Перевірити коректність послідовності дужок.
3. Знайти найкоротший шлях в графі. BFS, A*, Dijkstra
4. http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1034&
5. Мінімальне остове дерево. http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1047&
6. http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1079&
7. http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1099&
8. http://acm.timus.ru/problem.aspx?space=1&num=1100 – heap sort
І взагалі більша половина всіх задач потребують як мінімум масиву =). Якщо хтось знає ООП, може взятись за наступні завдання (але перевіряти вже їх доведеться вам самим):
1. ILazyPrimeCalculator, який зможе повертати прості числа по їх номеру (перше – 2, друге – 3, п’яте – 11, …). При цьому потрібно виконувати якомога менше зайвих обчислень.
2. IBiDirMap – структуру даних, що аналогічна Dictionary, але дозволяє ефективно знаходити ключ по значенню та перевіряти наявність заданого значення в колекції. Якщо виникає повторення ключів чи значень – кидати ексепшн.
3. IBiDirMultiMap. Дозволити різні значення value для ключа та можливість збереження одного value для різних ключів. Врахувати можливість дублювань пар (key, value).
4. ILazyEnumerator, що забезпечує можливість швидкого повторного проходження по елементах, що додаються в колекцію. Вважати, що отримання самих елементів є дуже важкою операцією і тому необхідно керувати отримані результати для повторного використання. Можете використовувати клас ExpensiveOperationProxy для тестування.
5. ISparseMatrix – інтерфейс, який описує двохвимірний масив (матрицю), який містить елементи типу T і в момент створення заповнений значеннями за замовчуванням (default(T)), при цьому матриця може мати великі розміри, але кількість елементів, значення яких не default(T), невелика. Реалізуйте клас таким чином, щоб він використовував память лише для елементів, значення яких відрізняється від значення по замовчуванню.
6. ISparseArray – багатовимірний аналог ISparseMatrix.