Description

Introduction

Algorithm Design and Analysis is an essential basic course in computer science and technology, and it is a compulsory course for the academic researcher and software developers in various fields of computer science and technology. Through the study of various representative algorithms, it aims at understanding and mastering the main principles of algorithm designing, cultivating students' ability to analyze the complexity of algorithms, and thus laying a solid knowledge base for independent algorithm design and analysis.

Through experiments, students can deepen their understanding of basic algorithm design methods, enhance students' perceptual understanding of the operational efficiency of different algorithms , and make students get systematic training in algorithm design and programming skills, so that lay a good practical foundation for future research and application development.

The experimental course is an in-course experiment, not a single column of credits, will spend a total of 24 hours. The experiment was divided in 6 experiments, each assigned 4 hours. Experiments consist of three categories: Validation, Design and Comprehensiveness, of which experiments 1-5 are validation experiments and design experiments. Experiment 6 is a comprehensive experiment used to replace the final examination.

Experiment I: String Search

1. Purpose

Apply brute force to solve the problem of string matching, further improve string matching efficiency through time-space trade-offs. Please SUBMIT experimental reports.

2. Main requirements

(1) Write and debug the brute force string matching algorithm and apply it to a specific search application.

(2) Write the string matching algorithm using input enhancement technology, repeat the above application, and compare and analyze the efficiency of the two.

3. Instrument and equipment

PC-compatible (language-free).

4. Algorithm's principles

²  Problem formulation

Look for the substring's (the value of i) location of the matching pattern in the text.

Text: a string of n characters.

Pattern: a string of m characters. (m < n)

²  Algorithm strategy

A brute-force algorithm for the string-matching problem is quite obvious: align the pattern against the first m characters of the text and start matching the corresponding pairs of characters from left to right until either all the m pairs of the characters match (then the algorithm can stop) or a mismatching pair is encountered. In the latter case, shift the pattern one position to the right and resume the character comparisons, starting again with the first character of the pattern and its counterpart in the text. Note that the last position in the text that can still be a beginning of a matching substring is n – m (provided the text positions are indexed from 0 to n − 1). Beyond that position, there are not enough characters to match the entire pattern; hence, the algorithm need not make any comparisons there.