ICS4U – Python Programming Evaluation 3

Instructions

These ICS4U Grade 12 Computer Science python coding questions will form a part of your final grade for this course and are to be handed in for grading. 

For all of the following questions:

  • Use a Python IDE of your choice and create a coded solution to each of the given problems.
  • Hand in commented .py files for your solution.

Your grade will be based on your ability to demonstrate the overall expectations from the Ontario Computer Studies Curriculum

A3 – Designing Algorithms

  • Read and write data to external data files
  • Use search and sort algorithms to solve a problem

A4 – Code Maintenance

  • Write appropriate internal documentation explaining main points of the code
  • Carry Out a testing plan for an algorithm

C2 – Analyze Algorithms

  • Investigate the efficiency of different searching and sorting algorithms

Important

Since you will be using File Input and Output in these questions, store the name of your data file in a variable in the very first line at the top of your program.  Then use that variable in your code to open the file.

The reason for this is so that I can easily change the file name with my own test data when grading.  I won’t have to go and change anything in your code other than the first line. 

				
					#Example 

inputPath = "dataFileIN.txt"
outputPath = "dataFileOUT.txt"

#Use that variable in your code
file = open(inputPath,"r")

				
			

ICS4U Python Programming Evaluation Question 1

File Name:  “ICS4UFrequencySearch.py” 

There are an unknown amount of integers stored one per line in a data file.  

Write a function that will find the Nth most frequent integer that occurs in that file

  • If N = 1, then it finds the most frequent value
  • If N = 2, then it finds the second most frequent
  • If N = 3, then it finds the third most frequent
Notes:
  •  If there are multiple values with the nth largest frequency, then have that function return the smallest of those integers
Example:
  • If the data set is: 5 5 5 5 6 6 6 6 3 3 3 1 1 1 2 2 9 9  0
    • 5 and 6 are the most frequent
    • 3 and 1 are the 2nd most frequent
    • 2 and 9 are the 3rd most frequent
    • 0 is the fourth most frequent
  • If the user wanted the 2nd most frequent, it would return 1
  • If the user wanted the third most frequent it would return 2

Create a main function that reads the data file and allows the user to pick Nth most frequent. 

  • It should have error checking to prevent invalid inputs based on the data set
Create a comprehensive set of data files to test your data.  Think of all the different possibilities where you program might get tricked and create a data file to test those with.  To accompany those test files, provide an explanation on why you picked them.
 
Hand in 
  • Python File with your functions
  • All test data files
  • Explanation of why you created those testing files the way you did
You are only allowed to manipulate normal python lists in your solution.  No other data structures or libraries that you might know about are allowed. (That includes Python dictionaries)If

ICS4U Python Programming Evaluation Question 2

File Names -> You decide

In this question you are going to experimentally test the Time Complexities for the Best, Average, Worst cases, for the Insertion Sort Algorithm

For each case create a graph of Run Time vs Number of elements and then compare it to the Big O Notation discussed in the Lessons

Collecting Data

  • You will need to generate data to represent the best case, average case, and worst case for the Insertion Sort
  • Store your time data in milliseconds
  • Use data sets in the range 200 to 3000 elements with increments of 200 elements in between
  • To eliminate variation in the data sets and run times, you will take an average of 100 runs for each size data set.
    • For Example:
      • If you are testing with a list of 500 elements, generate 100 random lists with 500 elements
      • Find the average run time for the algorithm from those 100 test runs
To help you make the graphs I suggest you write your data to a comma delimited file with the number of elements as the first value, followed by the average run time for the best case, then the average case, and then the worst case scenario.
 
Graphing Option #1 – Use spreadsheet Software
 
  • If you are familiar with Excel or other spread sheet software, you should be able to open the comma delimited file from within that software and then make the graph
  • To make your life easier, when you create the data file using the extension .csv instead of .txt

Graphing Option #2 – Matplotlib in Python

  • Python has a library that is called matplotlib that you can use to generate the graphs directly from lists instead of writing to a data file
  • You are welcome to try that if you want to explore how that library works.
  • You will need to pip install the numpy and matplotlib packages in your IDE to make that work.

Hand in:

  • Any python files you created to accomplish the task
  • 3 graphs representing your results.  (Don’t make a single graph with all the data points)
  • A video explaining and showing your results (include an explanation of any code you created to accomplish the task) Ideally this would be accomplished by you making a screen cast video. Here are some free applications that allow you to make a screen cast video on your computer

Return to ICS4U Main Page