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.

We are trying to give you interesting tasks that the solution will be of great benefit for every student. The number of tasks is 12, the total score is 60. The requirement is to submit at least 80% of the tasks by deadline (delay at most 1 week with loss of 20% of the score) and reach at least 50% of the maximum total points available for the assignment. After the result has been announced, you may correct your code in a week. The program code must be sent as attachment to alg.progfel@gmail.com. The file name of the code starts with the job number, followed by the name of the student without spaces. E.g. Adrian Smith's 5th homework is named 5AdrianSmith.py. If you use Python3, the name of the file ended by 3, in our example it is 5AdrianSmith3.py. The subject of the email should be 5. HW Adrian, and for the corrected code 5. HW Adrian corrected. The following text must be added to the accompanying letter for each homework:

  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

Deadline 2019-02-16 saturday 24:00

  • 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')
      text = f.read().strip()
      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