версия 0.99

Проекти:

B1. Да се напишат функции/методи реализиращи алгоритмите на Knuth-Morris-Pratt и Boyer-Moore, като се използва Z-алгоритъма за предварителна обработка ([2]: 1.4, 2.2, 2.3). Работата на алгоритмите да се демонстрира чрез програма, която чете два низа (образец и текст) от стандартния вход и извежда брой срещания (на първия ред) и позициите на срещане (на втория ред) на стандартния изход.
Също така, да се напишат функции/методи реализиращи Shift-And метода и Karp-Rabin алгоритъма ([2]: 4.2, 4.4). Работата на алгоритмите да се демонстрира чрез програма, която чете два низа (образец и текст, съставен от малки латински букви) и число k (максимален брой mismatches; за Karp-Rabin алгоритъма k винаги ще е 0) от стандартния вход и извежда брой срещания (на първия ред) и позициите на срещане (на втория ред) на стандартния изход.

B2. Да се напишат функции/методи намираща оптимално налагане на два низа с линейна памет ([2]: 12.1). Работата на алгоритъм на да се реализира с програма, която чете два низа (съставени от малки латински букви) от стандартния вход и извежда оптималното налагане на стандартния изход (като налагането се извежда като при дефиницята от [2]: 11.2.1).
Също така, да се напишат функции/методи реализиращи намирането на longest common subsequence на K низа чрез longest increasing sequence ([2]: 12.5). Работата на алгоритъма трябва да се деомонстрира чрез програмата, четяща едно число K (брой низове, 1 <= К <= 10) и K на брой низа (съставени от малки латински букви) от стандартния вход, и да извежда най-дългата им обща подпоследователност на стандартния изход.

B3. Да се напишат функции/методи реализиращи алгоритъма на Aho-Corasick ([2]: 3.4, 3.5). Работата на алгоритъма да се демонстрира чрез програма, която решава задача G.Картина от Петия Междууниверситетски турнир по програмиране ( http://www.math.bas.bg/~nkirov/2002/5cp/pic.html )

B4. Да се напишат функции/методи реализиращи модифицирана версия на алгоритъма на Aho-Corasick ([2]: 3.4), която за всяка позиция от текста намира най-късия и най-дългия от дадените образци, които завършват на тази позиция. Работата на алгоритъма да се демонстрира чрез програма, която решава задача 1 от 2003/04 Конкурс по програмиране на PC Magazine/BG & Musala Soft ( http://konkurs.musala.com ).

B5. Да се напишат функции/методи реализиращи BYP алгоритъма ([2]: 12.13.1) за k-difference inexact matching. За стъпки b+c използвайте алгоритъм на Aho-Corasick, а за стъпка d динамично оптимиране със сложност O(N^2), където с N бележим дължината на образеца. Работата на алгоритъма трябва да се демонстрира чрез програма, решаваща задача 5 от 2002/03 Конкурс по програмиране на PC Magazine/BG & Musala Soft ( http://konkurs.musala.com ), като стойността на k се търси итеративно (0, 1, 2, ...).

B6. Да се напишат функции/методи реализиращи алгоритъма на Ukkonen ([2]: 6.1) за построяване на суфиксно дърво на даден низ. Работата на алгоритъма да се демонстрира чрез програма намираща лексикографски най-малката циклична ротация на низа ([2]: 7.13). Програмата трябва да чете низ (съставен от малки латински букви) от стандартния вход и да извежда лексикографски най-малката циклична ротация на низа на стандартния изход.

B7. Да се напишат функции/методи реализиращи алгоритъма на Ukkonen ([2]: 6.1) за построяване на суфиксно дърво на даден низ и разширението за построяване на обобщено суфиксно дърво ([2]: 6.4). Работата на алгоритъма да се демонстрира чрез програма намираща най-дългия общ подниз на няколко низа ([2]: 7.6). Програмата трябва да чете едно число K (брой низове, 1 <= К <= 10) и K на брой низове (съставени от малки латински букви) от стандартния вход, и да извежда най-дългия им общ подниз на стандартния изход.

B8. Да се напишат функции/методи реализиращи алгоритъма на Ukkonen ([2]: 6.1) за построяване на суфиксно дърво на даден низ и изчисляването на Matching Statistics ([2]: 7.8). Работата на алгоритъма да се демонстрира чрез програма намираща най-дългия общ подниз на два низа с ефективно ползване на памет ([2]: 7.9). Програмата трябва да чете два низа от стандартния вход и да извежда най-дългия им общ подниз на стандартния изход.

Изборни проект:

B9. Да се напишат функции/методи реализиращи алгоритъм на Ukkonen ([2]: 6.1) и LCA ([3]). Работата им да се демонстрира чрез решение на задача 6 от 2001/02 Конкурс по програмиране на PC Magazine/BG & Musala Soft ( http://konkurs.musala.com ).

B10. Да се напишат функции/методи реализиращи алгоритъм на Ukkonen ([2]: 6.1) и LCA ([3]). Работата им да се демонстрира чрез решение на k-mismatch problem ([2]: 9.4). Програмата трябва да чете два низа (образец и текст) и число k (максимален брой mismatches) от стандартния вход и извежда брой срещания (на първия ред) и позициите на срещане (на втория ред) на стандартния изход.

B11. Да се напишат функции/методи реализиращи алгоритъм на Ukkonen ([2]: 6.1) и LCA ([3]), и решаващи k-difference inexact matching ([2]: 12.2.4). Работата им да се демонстрира чрез решение на задача 5 от 2002/03 Конкурс по програмиране на PC Magazine/BG & Musala Soft ( http://konkurs.musala.com ).

B12. Да се напишат функции/методи реализиращи Chang-Lawler алгоритъма ([2]: 12.3.3) за k-difference inexact matching. Работата на алгоритъма трябва да се демонстрира чрез програма, решаваща задача 5 от 2002/03 Конкурс по програмиране на PC Magazine/BG & Musala Soft ( http://konkurs.musala.com ), като стойността на k се търси итеративно (0, 1, 2, ...).

Литература:

[1] Introduction to Algorithms (First Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

[2] Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology by Dan Gusfield

[3] The LCA Problem Revisited by Michael A. Bender and Martin Farach-Colton