Lab 3

For this lab you must provide a single python program that can perform all the calculations specified below, similar to the structure used in Lab 2. Your program will take a single commandline argument that tells the program which question is to be calculated, and then uses functions to produce the output.

For example, to execute Question 2, you would type:

$python lab3.py q2

You can use I/O redirection as well to make it easier to create test inputs, as was done in the previous two labs. For example, for Question 2, you need to provide 2 lists as input. This is tedious, so you can put the two lists in a file called “q2input1.txt”, and send it to your program as input:

$python lab3.py q2 < q2input1.txt

Question 1 (execution code “q1”)

Write an iterative version of the Fibonacci problem. Given an input value, n, calculate the nth Fibonacci number, where:

fib(1) = 1

fib(2) = 1

fib(n) = fib(n1) + fib(n2), for n > 2

NOTE: this problem must be solved using loops, you can’t use recursion!

Your internal function must take an integer as an input parameter and produce an integer as a return value; you are not to do any input or output within the function itself (as in Lab 2).

Question 2 (execution code “q2”)

Implement the merge() function that is part of the MERGESORT algorithm. Recall that this function takes two (sorted) lists as input, and merges them into a single sorted list.

In the MERGESORT algorithm you always operate on a segment of the larger input list. For this implementation, though, you can just accept two separate lists as input, and produce a new list as a return value. Your function must not do any input or output, as in Lab 2.

Your function must run in O(n)time, where nis the combined size of the two input lists.

Note that you can get user input of lists by using the input()function, as in:

L1 = list(map(int, input().split(",")))

L2 = list(map(int, input().split(",")))

Then, the user types in commaseparated lists list. For output, you can just print the resulting list, and python will format it for you. Here is a sample run of the program:

$ python lab3.py q2

5, 9, 11, 18, 45, 52

1, 3, 19, 62

[1, 3, 5, 9, 11, 18, 19, 45, 52, 62]

(The first two lines in italics are the user input. The last line in bold is the program's output.)

Question 3 (execution code “q3”)

Write an iterative function that outputs a triangle of asterisk characters whose height is given (as a positive integer) by the user. This triangle should be a rightangled triangle with the right angle at the bottomleft.

For example, if the user entered a height of 6, your function would output the following:

*

**

***

****

*****

******

NOTE: your solution must use iterative loops, not recursion! Also, you may not use “sequence multiplication”; that is, you can’t print a line of asterisks with a command similar to:

print “*” * i

Also, there are no spaces between the stars! Python's print()function always inserts spaces between elements separated by a comma, so you can't do it this way. Instead, build a string of stars, and then print it when it's done:

s = ""

while … :

s = s + "*"

…

print (s)

Unlike the Lab 2 specifications, this time your internal function does do the output, and consequently has no return value!! It must take the input (the height of the triangle) as a parameter, however, and not do the input itself.

Question 4 (execution code “q4”)

Repeat Question 3, only this time you must use recursion, not iterative loops. (You are still prohibited from using sequence multiplication.)

HINT: ask yourself: “If I had a function that could print a rightangled triangle as described, but it had to be smaller than the one I have to draw now, how could I use that function to draw my triangle?”

Question 5 (execution code “q5”)

Repeat Question 3, only this time the right angle needs to be at the bottomright. For example, if the user entered a height of 6, your function would output the following:

*

**

***

****

*****

******

Use space characters before the required number of asterisks on a given line to achieve this effect.

As in Question 3, your solution must use iterative loops and not recursion; your function produces the output and has no return value, and takes the height of the tree as an input parameter and performs no user input itself. There are no spaces between the asterisk characters.

Question 6 (execution code “q6”)

Repeat Question 5, but use recursion instead of iterative loops.

Note that this is a little more difficult that the leftleaning triangle from Question 4! In order for your recursion to work, you have to have a way of telling the recursive function how many space characters it needs to print before the asterisks.

Question 7 (execution code “q7”)

Use Euclid’s method for calculating the Greatest Common Divisor (GCD) of two positive integers.

The general algorithm looks like this:

● Input the two positive integers, X and Y

● Let R be the remainder when you divide X/Y (the “mod” function)

● Repeat until R == 0:

○ Set X = Y

○ Set Y = R

○ Recalculate R as the remainder when you divide X/Y

● Output the value of Y as the final answer

NOTE: you must use iterative loops to solve this problem; you can’t use recursion.

Your function should take the two values as parameters, and return a single value that is the GCD of the two input values. Your function should have no console input or output.

Question 8 (execution code “q8”)

Repeat Question 7, only use recursion instead of iterative loops. We can redefine GCD recursively as follows:

GCD(X, Y) is:

● Y, if X is a multiple of Y

● GCD(Y, X mod Y) otherwise

This should just make sense. It should be obvious that if X is a multiple of Y, then clearly the GCD is Y (consider X=30 and Y=10 … if Y goes evenly into X, then the GREATEST value that goes evenly into both has to be Y!).

But if Y is not a multiple of X, then the GCD between X & Y has to be the same as the GCD between X and the remainder when you divide X/Y. Whatever the GCD is, since it’s not Y, it must go into both X and Y (by definition), and will be contained within the remainder.

(The doesn’t mean the remainder is the GCD … it just means that the GCD will be contained within the factors of the remainder.)

Lab 4

For this lab you must provide a single python program that can perform all the calculations specified below, similar to the structure used in Lab 3. Your program will take a single commandline argument that tells the program which question is to be calculated, and then uses functions to produce the output.

For example, to execute Question 2, you would type:

$python lab4.py q2

You can use I/O redirection as well to make it easier to create test inputs, as was done in the previous three labs. For example, for Question 2, you need to provide 2 sorted lists as input.

This is tedious when testing, so you can put the two lists on separate lines in a file called “q2input1.txt”, and send it to your program as input:

$python lab4.py q2 < q2input1.txt

Question 1 (execution code “q1”)

Write a function that computes the time difference in hours and minutes between two user supplied times.

The time of day will be entered as a 3 or 4digit integer, in the form HHMM or HMM, with the hour specified in 24hour format. Here are some examples:

10:15am > 1015

10:15pm > 2215

7:22am > 722

7:22pm > 1922

2:07pm > 1407

12:00am (midnight) > 000

12:15am > 015

You may assume that the first input is always before the second input, and that the inputs are less than 24 hours apart from each other. You may not assume that the first input is a smaller integer than the second input, however!! In other words, the time span may cross from one day to the next, past midnight.

The function should return a string (and the program should print this string by itself on a line) that states the integer number of hours elapsed, followed by a colon, followed by the integer number of minutes elapsed. Of course, the number of minutes should only be between 0 and 59, inclusive.

The hours should not be zeropadded (except for the actual zero value, which is just the single digit ‘0’); minutes should be zeropadded, so it will always be exactly 2 digits.

Here are some sample outputs:

1:15

10:04

0:15

19:00

Question 2 (execution code “q2”)

You are to write a function that returns the boolean True or False to state whether a positive integer is a prime number of not.

Remember that a prime number is a positive integer that has no factors other than 1 and itself.

The integer 2 is considered to be the smallest prime number.

The input is just a single positive integer, and the output is just the word True or False.

Question 3 (execution code “q3”)

You are to write a function that returns one of three strings:

● “abundant” if the input positive integer is abundant;

● “perfect” if the input positive integer is perfect;

● “deficient” if the input positive integer is deficient.

These three classifications relate to the sum of the number’s proper divisors (i.e. not including itself): “abundant” means the sum is greater than the number itself; “perfect” means the sum is equal to the number itself; and “deficient” means the sum is less than the number itself.

For example:

● 12 is “abundant”, because the proper divisors of 12 are 1, 2, 3, 4 and 6, which add to 16, and 16 > 12;

● 6 is “perfect”, because the proper divisors of 6 are 1, 2 and 3, which add up to 6; and

● 9 is “deficient”, because the proper divisors of 9 are 1 and 3, which add up to 4, and 4 < 9.

The function takes a single, positive integer as input, and outputs one of the three strings as described above.

HINTS

● For Questions 2 & 3, there could be some common subtask. Could you write a function that could be used in both questions, rather than duplicate the work separately for each?

● For Question 1, one of the tricker steps involves converting that input integer into separate hours and minutes. There are different techniques, including:

○ string slices keep the input as a raw text string, and chop it up using slices. Be careful with the different possible lengths of the input values.

○ integer division you can use ‘/’ and ‘%’ to pull out the hour and minute values quite easily, and would be good practice in using these important operations!

Lab 5

Objectives

1. Work with the Python “Dictionary” type

2. Work with file input & output

For this lab you must provide a single python program that can perform all the calculations specified below, similar to the structure used in Lab 4. Your program will take three commandline arguments. The first will indicate the filename of the input text file; the second will be which question you wish to run ("q1" or "q2"). If you choose "q1", the third input will be the word to search for; if you choose "q2", the third input will be the name of the output file.

For example, to execute Question 1, with "big.txt" as the input filename and "fresh" as the search word, you would type:

$python lab5.py big.txt q1 fresh

To execute Question 2, with "big.txt" as the input filename and "stats.txt" as the output filename, you would type:

$python lab5.py big.txt q2 stats.txt

There is no input from STDIN, so you can't use file I/O redirection for your input as in previous labs.

Starting Up

When your program first starts up, it must load data from a file into a dictionary. Both questions below will work directly with the dictionary.

The data file will simply be a large text file filled with English words. You are to read the file linebyline, and store a count of every unique word that is encountered in a dictionary. They key will be the word, and the value will be the count. For simplicity, don't worry about the effect of punctuation or capitalization; just parse the words based on whitespace only.

For example, if the input file was:

the quick brown fox jumped over the lazy dog

The dictionary would look like this:

{ "quick" : 1,

"fox": 1,

"brown" : 1,

"the": 2,

"dog": 1,

"lazy" : 1,

"jumped" : 1,

"over" : 1

}

The actual input file will be a text version of an English novel, so the counts will be very large.

Question 1 (execution code “q1”)

For this question, you are to look for a particular word that the user specified as the third commandline argument. If the word appeared in the data file, you are to output a success message, plus the count of the number of times the word occurred. For example, if the search word was "fresh", and it occurred 138 times in the text, you would output:

The word "fresh" occurred 138 times in the text.

If the search word does not appear in the text, output a failure message. For example, if the search word "hotdog" did not appear in the text, you would output:

The word "hotdog" did not occur in the text.

Question 2 (execution code “q2”)

For this question, you are to write some basic statistics for the words to a text file whose name is given as the final commandline argument.

After you read in the words and have the complete dictionary, go back through the data and calculate:

1. The total number of unique words

2. The word that is used the most

3. The average length of the words

4. A tally of how many words have each of the vowels (caseinsensitive):

a, e, i, o, u

For example, the following would be the contents of the output file given the above example:

There are 8 unique words.

The word "the" is the most used word (2 occurrences).

The unique words have an average length of 4.125.

Vowel usage amongst the unique words:

a or A = 1

e or E = 3

i or I = 1

o or O = 4

u or U = 2

Some important criteria of the output:

The wording must appear exactly as above, including punctuation.

If there is a tie for the most used word, choose the one that comes first alphabetically (you can use the usual operators to test words for "<", "==" etc; the operators are defined for text strings to compare them alphabetically)

There must be a tab character ("\t") before each letter in the vowel tally.

The file should end with a single newline ("\n") character (that is, the utally line would be the final line, but would have a single \nafter the value).

Some of these statistics could be measured as you read the words from the original text, and that would be more efficient; however, this is not required, and it is sufficient to simply do the calculations from the final dictionary from scratch.

**Subject Computer Science Python Programming**