# Programing tasks for the theory of algorithms (BMETE91AM47/TA)

Oktató:
Kurzus típus:
Elmélet
Nyelv:
angol
Félév:
2018/19/2

The aim of this subject is to maintain the programming skills of the students through the solution of the programming tasks related to the Theory of Algorithms, and at the same time to facilitate a better understanding of the algorithms and the efficiency and complexity of them.

  I encoded this program myself, did not copy or rewrite the code of others,
and did not give or send it to anyone else.

Signature


You have to follow the next rules. You must not submit or look at solutions or program code that are not your own. It is an act of plagiarism to submit work that is copied or derived from the work of others and submitted as your own. You must not share your solution code with other students, nor ask others to share their solutions with you. You must not ask anybody to write code for you. Many forms of collaboration are acceptable and even encouraged. It is usually appropriate to ask others for hints and debugging help or to talk generally about problem solving strategies and program structure. In fact, we strongly encourage you to seek such assistance when you need it. Discuss ideas together, but do the coding on your own.

## Contents

1. Pattern matching (2019-02-16 24:00)

## 1. Pattern maching

• Write a program for comparing the simple matching and the quick search algorithms!
1. The input for the program is given in a terminal command. For Python 2 it looks like
python 1AdrianSmith.py text.text pattern


for Python 3 it is like

python3 1AdrianSmith3.py text.text pattern


The program read the file text.text and search for the first occurrence of the given pattern in it. The command arguments can be read out from the inbuilt array sys.argv:

import sys

print('The name of the file ' + sys.argv[1] + ', the pattern is ' + sys.argv[2])


(The sys.argv[0] contains the name of the program.)

2. For reading a file use the file functions, e.g.
f = open(filename, 'r')
f.close()


The strip() method cut down the unnecessary starting and endig white spaces.

3. In your program you do not need to check if the specified text file exists or whether it actually contains text. The pattern is always at most as long as the text. The text contains lowercase letters of the English alphabet a-z and spaces. There are only lowercase letters in the pattern, but no spaces. According to the algorithms, the program allows the comparison of a single character of the text and the pattern, but does not use the Python string functions except the len() function.
4. Your program have to run the simple matching and the quick search algorithms with the given text and pattern. The output of the program specifies whether the pattern is in the text, at which character position and how many comparisons have been made to the first occurrence:
Simple matching made 2610 comparison(s), the pattern is at 2321
Quick search made 270 comparison(s), the pattern is at 2321


Specify the number of comparisons even if the pattern does not appear in the text:

Simple matching made 2610 comparison(s), no pattern in the text
Quick search made 270 comparison(s), no pattern in the text

• If in Python2 you take a comma after a print command, the output of the next print will be continued in the same line. For this effect in Python 3 use the end option like in print("Hello", end="").
• Try your program with the next downloadable text files and with the given patterns (of course in the test phase of your program, you may use your own very simple text files and patterns):
File Pattern
1.text overscrupulous
1.text zombies
2.text aaaaaaaaa
2.text bbbbbbbbb
2.text aaaaaaaab
2.text aaaaaaaba