BSc II - Fundamental Data Structures and Algorithms (Revision) - 02 ONovember 2026 - Asha KS

Summary

Asha KS led a revision session on string-matching algorithms, combining exam preparation with an introduction to the naive string-matching method and the KMP algorithm.

Exam preparation and format

The summative exam was described as scenario-based, with several questions or subquestions carrying different mark values. A practice scenario involved representing a college’s departments and courses as a tree.

Asha advised students to explain their answers in enough detail to demonstrate their reasoning, rather than giving only one-line responses. For programming questions, students should show the program’s logic and use correct indentation.

The lecturer initially discussed using notebooks and uploading files. However, a student-support representative later clarified that the secure exam environment would not allow students to open external applications. Students should use the exam’s provided answer space to write code. Their understanding and logic would be assessed; the code would not need to be run.

Asha said revision should emphasize the first four units, while the session focused on the fifth unit: string-matching algorithms.

String matching: core ideas

A string is a sequence of characters. It may contain letters, numbers, spaces, or special characters.

In a matching problem, the text is the larger string being searched, and the pattern is the smaller word or sequence of characters being sought. String matching identifies whether, and where, a pattern occurs within a text. Positions are reported using index values, which begin at 0 in Python.

The class discussed applications including search engines, Ctrl+F, email searches, database lookups, DNA analysis, and detecting suspicious activity in security logs.

Naive string-matching algorithm

The naive method checks possible locations in the text one by one:

1. Start at the beginning of the text.
2. Compare the pattern with the text, one character at a time.
3. If all characters match, record the position where the match begins.
4. If a character differs, shift the pattern one position forward.
5. Repeat until every possible position has been checked.

This approach is straightforward and can find multiple occurrences, including overlapping ones. However, it may repeat many comparisons, especially with long texts or patterns, making it inefficient for large-scale searches.

KMP algorithm and LPS

Asha introduced KMP as a way to reduce the repeated comparisons made by the naive method. KMP prepares information about the pattern before searching, using an LPS array. LPS stands for longest proper prefix that is also a suffix.

A prefix is a sequence taken from the beginning of a string; a suffix is taken from its end. A proper prefix is a prefix that is not the entire string.

When a mismatch occurs, KMP uses the LPS information to determine how far the pattern can shift. This allows it to reuse what it has already learned about matching characters instead of restarting the comparison from scratch.

The overall lesson was to choose an algorithm according to the size and nature of the data: built-in or simple approaches may be sufficient for small searches, while more efficient algorithms are preferable for large texts and frequent searches.

Speakers and sources featured

• Asha KS — Facilitator and primary speaker; led the revision session and gave exam guidance.
• Student-support representative — Unnamed speaker who clarified the restrictions of the secure exam environment and explained that code would be assessed for understanding rather than execution.
• Students — Contributed answers and questions during the activities. Identifiable names or forms of address in the subtitles include Ramulu, Smith, Sheena, Moguby, and Mr. Videsi. Other student contributions are not clearly identified.