Abstract
In lectures we have discussed that the best way to learn computer programming and problem solving is to get hands on and solve problems. In the labs you have investigated creating user defined modules, data validation, and the list data structure. The following problems require you to apply the define, design, implement and test approach to problem solving.
Instructions
- This assignment is individual work. Groups and sharing are not permitted.
- All source code submitted as part of this assignment must contain a statement of authorship or a grade of 0 will be awarded for the entire problem.
- You will be submitting several source code files as well as an assignment report.
- Your assignment report must contain a title page which includes the title of the assignment, your name, student number, your professor’s name, the date, and a statement of authorship.
- Each problem requires evidence of the DDIT approach: an IPO chart, pseudocode or flow chart and testing traces. You may include pseudocode in your Python solutions as comments but you should make a copy of this in your report as well, do not use a screen shot.
- Each implementation must use the style rules defined in labs 1-3.
- For testing your code and for generating your debug traces from implementation testing you may find it convenient to use the command line technique demonstrated in Lab 01.
Problem 1: Finding Primes
Problem Statement
An ancient algorithm for finding prime numbers is called the Sieve of Eratosthenes. You start with a list of numbers, pick the first and cross out all the multiples of that number in your list. If you start your list at 2 then your first step is to cross out 4, 6, 8, … Then you would pick 3 and cross out 9, 15, … Notice that 6 and 12 were already crossed out because they’re multiples of 2. You then pick 5 because 4 was already crossed out … the first number you cross out is 25! Everything else was already crossed out when you checked 2 or 3. Once you have gone over your entire list whatever numbers remain are prime numbers. After your program creates the list of prime numbers print it out.
Table 1 shows the values for all primes lower than 30. First we created a list of all numbers from 1-30. Then we eliminated all the ones divisible by 2, shown in green. Next we eliminated all the ones divisible by 3 shown in orange - notice that 12, 18, and 30 were previously eliminated. Next we eliminated anything left that was divisible by 5: only 25 was still in the list. The final list is [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29].
- Ask the user to input a number larger than 2. Validate the input according to the slides definition of data validation. Call this validated number n.
- Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
- Create a variable called current that will initially be set to 2.
- For each element in the list, go through the list you created one element at a time. If an element is a multiple of current remove it from the list.
- After you have eliminated all the multiples of current from your list update current to the value of the next highest element of the list.
- While current is less than n repeat steps 4 and 5.
Note: This problem is difficult to work through if you try to work through it entirely in your head. If you use the techniques that have been presented in this course you can solve this problem. To successfully complete this task consider whether you should use 2 for loops nested inside one another. Take the basic algorithm and try writing out a trace. Simple solutions exist that are less than 20 lines long but it’s ok if yours is longer.
Your solution to this problem must be accompanied by an IPO chart, a flow chart, and trace information for a value other than 10. The trace must match YOUR flow chart.
Grading Scheme and Other Requirements
To be eligible for grading your solution must be named primes.py and must contain a statement of authorship.
Problem 2: Ordering at McThoseguys
Problem Statement
For this problem you should create a definition, a design, testing evidence, and implementation for each module you are asked to create. If you attempt to solve this problem without first creating a flow chart then you should expect great difficulty.
The local fast food restaurant, McThoseguys, has started using a computerized order input system for food order taking. You have the job of creating the system which when run asks for the person’s name, greets them and then allows them to pick from several options. Before greeting the person by name the system needs to check if the name that was entered is on the “dirty name” list. If it is on the list then instead of greeting the person ask them to re-enter their name until they enter something that is not on the “dirty name” list. The “dirty name” list is defined below.
In order to build their meal the user has to make several choices. The choices should be presented as a menu in order to minimize the amount of typing the user has to do. See the sample output in section 4.2 for the formatting. First the user will pick their sandwich wrapper. Next they have a protein selection. After choosing a protein they can pick toppings. Finally they may pick a sandwich sauce. Note that they should be allowed to pick only 1 wrapper, 1 protein, [1-3] toppings which may include repeats, for example choosing cheese two times means double cheese and is allowed, and and 0 or 1 sauce.
- McThoseguys’ list of dirty names is: mud, dirt, dust, booger, diaper
- Sneaky users will try to use capitalization to avoid matches, check the names case insensitively
- Make sure that the dirty names do not appear within the given name; Muddy Mike is not allowed
- The available wrappers are sesame seed bun or soft tortilla shell
- The available protein choices are chicken, beef, or tofu
- The available toppings are tomato, lettuce, pickles, cheese, and onions
- The available sauces are ketchup, mayonaise, and McCalorie Secret Sauce
Your solution must create a menu module which accepts a list of choices and the minimum and maximum number of choices allowed as parameters and returns a list to your main program. For example you might choose to create the module as def menuModule( choiceList, minimumChoices, maximumChoices) or in some other manner. Your module must not contain any logic or values from the rest of the problem, for example you may not code in questions that refer to toppings or sauces, the module must be completely generic and would work equally well if I started asking the user for car parts. The module should label each menu option with a single character, of your choice, and loop until the required number of acceptable choices has been input. You must validate that the choices input are correct and display an error message for any incorrect choices. After the user has completed their order you should confirm it by displaying the choices to the user along with a simple yes/no prompt, which you will test as a case insensitive string. You do NOT need to repeat the program if they choose “no”.
Sample Output
Name selection sample:
What is your name? Joe Dirt
Iapos;m sorry, that name is not allowed at McThoseguys.
What is your name? Filthy McMuddy
Iapos;m sorry, that name is not allowed at McThoseguys.
What is your name? There are those who call me ... Tim
Hello There are those who call me ... Tim, welcome to McThoseguys!
Choosing a wrapper without error sample:
What would you like as your sandwich wrapper?
[1]sesame seed bun
[2]soft tortilla shell
What is your choice? 2
Choosing a protein with error sample:
What would you like as your protein choice?
[1]chicken
[2]beef
[3]tofu
What is your choice? 4
Iapos;m sorry, that isnapos;t a valid choice, please try again.
[1]chicken
[2]beef
[3]tofu
What is your choice? 1
Choosing double onions as toppings sample:
What would you like as your topping choice (pick 1-3 items)?
[1]tomato
[2]lettuce
[3]pickles
[4]cheese
[5]onions
What is your choice or enter q to quit? q
Iapos;m sorry, you must choose at least 1 option(s).
[1]tomato
[2]lettuce
[3]pickles
[4]cheese
[5]onions
What is your choice or enter q to quit? 5
[1]tomato
[2]lettuce
[3]pickles
[4]cheese
[5]onions
What is your choice or enter q to quit? 5
[1]tomato
[2]lettuce
[3]pickles
[4]cheese
[5]onions
What is your choice or enter q to quit? q
Choosing “no sauce” sample:
What would you like as a sauce?
[1]ketchup
[2]mayonaise
[3]McCalorie Secret Sauce
What is your choice or enter q to quit? q
Different user confirmation samples:
There are those who call me ... Tim, you have chosen a chicken sandwich on a soft tortilla shell, with onions, onions, and no sauce.
Is this correct, yes or no? no
Sorry, letapos;s try again from scratch.
There are those who call me ... Tim, you have chosen a chicken sandwich on a soft tortilla shell, with onions, onions, and no sauce.
Is this correct, yes or no? maybe
Please enter yes or no.
There are those who call me ... Tim, you have chosen a chicken sandwich on a soft tortilla shell, with onions, onions, and no sauce.
Is this correct, yes or no? yEs
Thank you for shopping at McThoseguys! Enjoy your food!
Grading Scheme and Other Requirements
To be eligible for grading your solution must be named mcThoseguys.py and must contain a statement of authorship.