16 SEARCHING AND SORTING
A popular task in life and in programming is to search or sort data. This unit will introduce the student to several algorithms for searching and sorting data and give the student an idea about how to go about analyzing the efficiency (or inefficiency) of the search and sort methods presented.
Watch and Work - "Sorting Algorithms 01"
Find SortingAlgorithms01 lesson in the documents folder.
I will link you to some videos made by another educator. His videos are clear and well done.
The lesson will walk you through learning about bubble sort, selection sort, and insertion sort.
Following each sort are a handful of quetions for you to answer.
There is also a mini-lab that requires you to use X-Sort Lab to time some sorting routines.
Explore Project - "SearchSortExamples"
Open the project SearchSortExamples. Take a look a the class called 'ArraySearchSortFrame'.
This project has the three sorts coded in. When you run this class you can watch the three sorts working (like the applets you viewed before) and take a look at the code to see how the sorts were coded into the program. Note that the speed of the sort cannot be determined by the animation speed (selection sort doesn't require are much 'redrawing' so it appears much faster!). That's it, nothing else to do here - just examine the program.
Watch - "Sequential Search"
An easy way to search for data in an array is sequential search (linear search). This short video walks you through this simple search technique.
Watch - "Binary Search"
Sequential search is good when the list contains values that are not sorted. But if you happen to be searching for an item in a sorted list things get easier. Binary search is a simple and fast algorithm that lets you search a sorted list. Watch the video to find out how it works!
*Optional Watch - "Sequential and Binary Search"
If my videos didn't quite get the idea across, you can watch 'Sequential and Binary Search' on YouTube, or go find any number of videos posted on these topics. Watch until the algorithms make sense to you.
Think About It - "Search Questions 01"
Open the worksheet SearchQuestions01 from the documents folder.
Answer the questions. A solution sheet is provided so you can check your answers. Ask questions about any that you don't get correct!
Code It - "SearchMaster"
In the project SearchSortExamples, there are the two classes SearchingExaples and SearchMaster. SearchingExamples is the runner program that you can use to test out the code that you will write in SearchMaster. Code the two search methods in SearchMaster and then test out. Sequential search should be very quick to code, while Binary Search might take you anywhere from 10-30 minutes. Of course these two routines can be found online, but try your best to code them on your own without help at first!
Explore Project - "SearchSortExamples"
Open the project SearchSortExamples and look at the class 'ArraySearchSortFrame' again. This class also has the two search methods coded into it. Enter a number to search for and it will find it. Remember that for binary search to work you need to sort the array first!
Final Words About Searching / Sorting
The AP Exam will NOT ask you to write the entire code for these searches and sorts. However, you should be able to recognize the algorithms if you were shown their code. You should be able to describe what the code is doing, and know the purpose of each line in the code. You should know general approximations for the amount of work (number of comparisons, loops, etc.) that the different algorithms do when working on various sized lists.
17 TWO DIMENSIONAL ARRAYS (MATRICES)
A regular array keeps a value at each index position. But what if you keep another array at each index position? Then you get an array of arrays - also known as a 2 dimensional array, a matrix, or a grid. This unit takes a quick look at how a 2d array can be a useful data structure.
Watch - "2D Arrays (Matrices)"
A short introduction to how to create and use a 2d array.
Watch - "2D Arrays Length"
With a regular array, you use A.length to find out the length of the array. How do you find out both dimensions with a two dimensional array?
Read and Practice - "2D Arrays Notes"
In the documents folder, open 2D_Arrays_Notes. This document will review some of the basics of 2d arrays and also give you a few short practice problems to attempt on paper. Answers are provided at the end of the document.
Watch - "2d Arrays Gridder"
I've made a grid like drawing program to help you practice some 2d array problems.
The program is in the project called '2D Array Project'
and the class is called Gridder.
The program needs a little explanation - so here's the video. Then continue on to code in some problems.
Code - "Gridder Algorithms 1-6"
Open the document 'Gridder Algorithms'.
After a quick read of the first half of the document, code in problems #1-6 into the Gridder class. Test your solutions!
Watch - "2D Arrays Time Based Changes"
Difficult to explain this one in words - just watch the video! It will prepare you for the final coding challenge of this unit.
Code - "Gridder Algorithms One of Three"
Read the last part of 'Gridder Algorithms'. This section presents 3 problems that require you to use a temporary grid to the solve the problem. Pick 1 of the 3 problems and code a solution. Hint: each year the rotate grid seems to be the one that hurts students minds.
*Optional for Online Students - Game of Life *
You'll see that there is a frame class called GameOfLife in the 2dArray project. Look up on Wiki what Conways Game of Life is about and code it in to the class. You will want to put all of your code to 'update the world' into the STEP() method of the program. When you press RUN, the frame will continuously call the step method so that the game of life proceeds according to the rules presented on the Wiki page. This is a very popular program that is a cult classic in the programming world.
18 RECURSION
Recursion occurs when you repeat the same procedure or algorithm over and over again until a desired end point is reached (hopefully). Easier to demonstrate. In this unit we will introduce the idea of recursive algorithms. We will also discuss some of the pro's and con's of using recursive algorithms to solve problems.
Watch - "Recursion Introduction"
A look at some short recursive routines to help you start getting your mind wrapped around recursion.
*Optional Watch - "Havard CS50 Videos on Recursion"
Recursion can be a tricky topic. Here are two other videos you might want to watch.
Harvard CS50 Recursion 01 -https://www.youtube.com/watch?v=t4MSwiqfLaY
Harvard CS50 Recursion 02 - https://www.youtube.com/watch?v=VrrnjYgDBEk
Code Reading - "Recursion Reading 01"
Find Recursion Reading 01 in the documents folder. Some short recursive methods are shown. Near the bottom of the page are the method calls. Can you predict what the methods would output or return? Sure you can. Answers are provided in the document 'Recursion Reading 01 Solutions'.
*
For now do the problems that are declared as VOID (don't do the method/s that return a value).
Watch - "Recursion With Return Value"
As the name suggests. A look at how a recursive method works when it has a return value.
Code Reading - "Recursion Reading 01"
Finish off the last method or two from the Recursion Reading 01 that involved recursive methods that return a value. What would the methods return given the method call at the bottom of the page?
Code - "Recursion Problems 01"
Answer/code the problems in the document 'Recursion Problems 01'.
Watch - "Recursion Examples"
A final video to show you recursion in action actually doing a task that is not purely number based. You can also look online for many examples of problems that are solved elegantly using recursion.
These algorithms shown in the video are in the Recursion NB project folder if you want to run them.
The code is in the documents folder in a document called 'Recursion In Action'.
19 MERGE SORT
We learned a few sorting algorithms. We learned a little bit about recursion. Now lets take a look at a recursive sorting algorithm called MergeSort that blows away sorts like bubble sort, selection sort, and insert sort on large lists!
*Warning: this algorithm requires some thought. if you don't get it on the first run through, find the determination to figure it out!
Watch - "MergeSort Simple Merge"
Part of the MergeSort algorithm involves the use of a method called 'merge'. In this section we'll look at what the merge method does and get you to code a simple version of it. Then we'll take a look at another version (the one that is actually used in the mergesort algorithm).
After watching this video, it might help to see this visual example with plastic cups. Watch the first 3 minutes of
Harvard CS50: https://www.youtube.com/watch?v=EeQ8pwjQxTM
Code - "Merge Simple Version"
Open the project MergeSort form the projects folder. The class MergeSort has been set up for you to get coding a simple version of the merge method. Your code, when complete, should merge the two sorted arrays (make sure you keep them sorted!) into a third, sorted list. Use the algorithm that was shown in my video and in the CS50 video (first 3 minutes)
Watch - "MergeSort Merge Method"
There is nothing wrong with the merge method you just wrote. But here is the version that is actually used in the mergesort alogorithm. The main difference is that in the mergesort algorithm there is only one array, not two sorted arrays. You will keep track of starting and end points inside the single array to divide the single array into two sections. It's these two sections that you will merge together.
How MergeSort Works
Now that we have a good idea about how merge() can merge sorted numbers, how can we use it to code our recursive MergeSort algorithm?
Watch the rest of the CS50 video (from 3 minutes onward)
Harvard CS50: https://www.youtube.com/watch?v=EeQ8pwjQxTM
Also watch this good video by Joe James: https://www.youtube.com/watch?v=iMT7gTPpaqw
The full code for merge sort is in the documents folder in 'MergeSort Code'
Watch - MergeSort Algorithm
If the videos you watched earlier about mergesort made sense, then all is good. I thought I would add my 6 minutes worth on reviewing the actual 5 lines of the mergesort algorithm talking about the code provided in your project folder.
Review - "MergeSortReview01"
In my class and the AP Exam, the goal is to understand how mergesort works. You do not have to know how to code the entire routine.
Here are a few review questions to see if you understand the basics of mergesort. Open the document MergeSort Review 01.