Create 2 simple PYTHON programs by converting from pseudo code to python code click here
Complete 4.2.6 and post answers to Google site page title "Tracing code"
Rework the assessment and also post answers to your blog under new page titled "Sorting and Searching"
Section 4.2 Connecting computational thinking and program design (22 hours)
Teacher Notes : These are: addition and retrieval of data.
Teacher Notes : Students should be expected to discuss the differences between algorithms, including both standard and novel algorithms. For example, discussing the advantages and disadvantages of using a binary search as opposed to a sequential search.
Teacher Notes : Examination questions may involve variables, calculations, simple and nested loops, simple conditionals and multiple or nested conditionals. This would include tracing an algorithm as well as assessing its correctness. Students will not be expected to construct a flow chart to represent an algorithm in an externally assessed component.
Examination questions may involve variables, calculations, simple and nested loops, simple conditionals and multiple or nested conditionals. This would include tracing an algorithm as well as assessing its correctness.
Teacher Notes : MYP Mathematics: using flow charts to solve problems in real-life contexts, patterns and sequences, logic, algorithms. MYP Technology: design cycle (inputs, processes, outputs, feedback, iteration). AIM 4 Demonstrate thinking skills to represent a possible solution to a specified complex problem.
Teacher Notes : Suitable algorithms may include both standard algorithms and novel algorithms. Suitable may include considerations of efficiency, correctness, reliability and flexibility. Students are expected to suggest algorithms that will actually solve the problem successfully
Students should understand and explain the difference in efficiency between a single loop, nested loops, a loop that ends when a condition is met or questions of similar complexity. Students should also be able to suggest changes in an algorithm that would improve efficiency, for example, using a flag to stop a search immediately when an item is found, rather than continuing the search through the entire list.
Teacher Notes : Examination questions will involve specific algorithms (in pseudo code/ flow charts), and students may be expected to give an actual number (or range of numbers) of iterations that a step will execute.
Teacher Notes : These include: add, compare, retrieve and store data. Complex capabilities are composed of very large numbers of very simple operations.
For example, “find the largest” is a compound operation.
Teacher Notes : For example, fixed vocabulary, unambiguous meaning, consistent grammar and syntax
Sorting is another very important area of algorithms. Computers often have to sort large amounts of data into order based on some attribute of that data, such as sorting a list of files by their name or size, or emails by the date they were received, or a customer list according to people’s names. Most of the time this is done to make searching easier. For example you might have a large amount of data and each piece of data could be someone’s name and their phone number. If you want to search for someone by name it would help to first have the data sorted alphabetically according to everyone's names, but if you then wanted to search for a phone number it would be more useful to have the data sorted according to people’s phone numbers.
Given an array of N items and L = 0, Selection Sort will:
If you record how many comparisons you had to make each time to find the next lightest box you might notice a pattern (hint: finding the lightest should take 7 comparisons, and then finding the second lightest should take 6 comparisons…). If you can see the pattern then how many comparisons do you think it would take to then sort 9 boxes into order? What about 20? If you knew how many comparisons it would take to sort 1000 boxes, then how many more comparisons would it take to sort 1001 instead?
One of the most intuitive ways to sort, but not very efficient...
Comparison and swap require time that is bounded by a constant, let's call it c.
There are two nested loops in (the standard) Bubble Sort.
The outer loop runs for exactly N iterations.
But the inner loop runs get shorter and shorter:
Thus, the total number of iterations = (N−1)+(N−2)+...+1+0 = N*(N−1)/2 (derivation).
Total time = c*N*(N−1)/2 = O(N^2). (big O n squared)
Divide step: Choose an item p (known as the pivot)
Then partition the items of a[i..j] into three parts: a[i..m-1], a[m], and a[m+1..j].
a[i..m-1] (possibly empty) contains items that are smaller than p.
a[m] is the pivot p, i.e. index m is the correct position for p in the sorted order of array a.
a[m+1..j] (possibly empty) contains items that are greater than or equal to p.
Then, recursively sort the two parts.
Selection Sort may seem like logical ways to sort things into order, but they both take far too many comparisons when they are used for large amounts of data. Remember computers often have to search through HUGE amounts of data, so even if they use a good searching algorithm like Binary Search to look through their data, if they use a bad sorting algorithm to first sort that data into order then finding anything will take far too long!
A much better sorting algorithm is Quick sort! (the name is a bit of a giveaway)
Create a solution in pseudo code to perform a selection sort ( set start position = 0 then compare the element the start position with the rest of the elements ( performing a swap ) if next is smaller than current at then end of the first iteration the smallest element should be in position 0, but you need to sort all elements.
Open Jupyter Notebook and write program to perform the selection sort
Post both pseudo code and python code to your google site:
What is a Flow Chart
Activity A : Find the error
Why is it inefficient how could you improve it ?
User Enters 3,5,6,4,4
What is the Output ?
User Enters 6,5,3,2,1
What is the Output ?
User Enters 2,4,78,99
What is the Output ?
Rank above into how efficient they are
loop while COUNT < 15
COUNT = COUNT +1
SUM = 0
loop COUNT from 0 to 5
SUM = SUM + COUNT
An array is a data structure that lets you hold list of like items ( rather than use multiple variables)
Example if we wish to store a list of car manufactures we could hold as 1 dimensional array. Remember the first element starts at 0
car_array = ["Volvo","BMW","Honda"]
In python we can iterate thru a list in 2 ways
for i in range(len(car_array)):
for element in car_array:
In real-world Often tasks have to store rectangular data table( board games for example). Such tables are called matrices or two-dimensional arrays. In Python any table can be represented as a list of lists (a list, where each element is in turn a list).
When we process 2D arrays we use a loop with a loop : Write some code to print out each element in car_array
# row 0 = bmw, honda
# row 1 = red, blue
a = [["bmw","honda"],["red","blue"]]
for i in range (len(a)):
for j in range (len(a[i])):
#print each element in the array
Given an array of N integers ranging from (0,20). Write pseudo code to iterate thru and print out the average value and the number of zero values.
Assume array contains the following integers [1,6,18,20,0,1,7,9,8,6,2,1,3,0]
This algorithm calculates the second hand price of different models of car. The variable condition is an integer between 1 and 4 where 1 is excellent and 4 is very bad.
By copying the table below, trace the following algorithm using the data in the collection DATA. Note: B and C are also collections and are initially empty.