Iterative Algorithms Summary

Computer Science 30

Start here: http://www.csfieldguide.org.nz/en/chapters/algorithms.html

Watch the intro video
Read the entire page. It is long but you will learn all you need to know, practically.

Alberta Education Credit Title: CSE3110 Iterative Algorithms 1

Evaluation Guide: For this credit the following will serve as the skills breakdown:

Basic Skills:

Describing Binary Search and comparing it to linear search
Describing and comparing the 3 sort algorithms
Implementing Binary Search on number and String arrays
Implement one Sort algorithm on an array of numbers
Using overloaded methods to implement the above on arrays of both ints, doubles and/or Strings
Designing an experiment to compare the efficiency of the 3 sort algorithms

Advanced Skills:

Using external files to generate large arrays for searching and sorting
Implementing all three required Sort algorithms on an array of Strings
Implementing binary search and one Sort algorithm on an Array or ArrayList of simple objects

Background

So far, we have only looked at simple variables and using two other data structures (Arrays and ArrayLists) to store data. These data structures allow you to create more ‘real world’ programs than before.

Regarding using arrays: Recall the Store Inventory assignment in which you searched for a product name and then returned its information such as price, colour, etc.
Regarding ArrayLists: Recall the Internet Dating activity in which we stored instances of clients. We then used an age and gender to search the client list for good matches.

This credit is all about improving the searching process. In CS20, you used what is called a LINEAR search (aka a sequential search) because you searched each item in your list one at a time, until you found it.
Important concept to consider: If you had 10 clients in your list, a linear search would not take long to do. But what if you had 100,000 items in the list and what you were looking for was at number 99,999? What if we were talking billions of items (think Google!)?

This credit will therefore cover 6 broad concepts

Concept 0: Review and New

Assignment 0.1 Basic Java Algorithms

Concept 1: Better searching - there are lots of search algorithms out there you only need to understand one: BINARY SEARCHING.

AP students you are responsible for knowing this algorithm down to the point where you could write the code from memory.
Regular students, you only need to know theoretically how it works so that you can find existing code on the Internet and adapt it to your specific needs.

Concept 2: Sorting a list - In order to use any type of search algorithm (other than linear), your data must be sorted. There are many sorting algorithms out there. You are required to understand 3:

Bubble Sort
Selection Sort
Insertion Sort
IB students must be able to recognize the differences between these and be able to construct the first two

Concept 3: Merging lists - This will be quick concept that covers taking two lists and combining them into one. This can be accomplished in one of two ways:

Concatenating the lists - super simple, it just means adding one list to the end of the other
Interweaving the lists - a bit more complicated as it involves taking two sorted lists and merging them together in order

Concept 4: Storing your data in an external file. If all we ever work on is 10 item arrays, these algorithms do not save us much time. So let's learn how to work with 10,000 items. This will involve you saving your data to a text file (on your hard drive) and loading data from a saved file into an appropriate list (in memory).
Concept 5 (Projects Advanced Students Only, wanting 80+%): Includes using a file to generate instances of objects, Sorting arrayLists of simple objects and comparing efficiency of Algorithms

Before you begin, create a new Netbeans Project called Iterative Algorithms.

Concept 0: Review

Marked Assignment: Bike-A-Thon Fundraising

Concept 1: The Binary Search Algorithm

3-4 classes.

All assignments in this concept are due before class on: tba

Learning about Binary Search:

Begin by reading the main story on the following link. Hunting Dragons with Binary Search

Here are the basics:

A Sequential search is a search that consists of taking a list of elements and going through the list one element at a time until the desired element is found. This is the simplest search algorithm and also the least cost effective. It is essentially a brute-force search method. This is only good for lists that have only a few elements in them.

A Binary search is a search that takes a given SORTED list (an array) and goes directly to the middle element. It then checks that element and see's if it match's what it is searching for if not then it will check to see if the element is greater or less than the element it is searching for. If the middle element is greater it will take the lower half and do the same thing all over again until the desired element is found. If the middle element is lesser it will then take the greater half and do the same thing all over again until the desired element is found. This search algorithm is much faster and more cost effective then a Sequential search and will take less time in larger lists.

You have more than one option for learning about it. The key is that you have a thorough grasp of how to do it for both numbers and strings.

Option 1: Watch the following two YouTube videos on Binary Searching. They are each about 12 minutes long and do a very good job at fully explaining the algorithm. You do NOT need to type out the java code just watch THOUGHTFULLY.

Option 2: Search the internet and other explanations or videos that explain the binary search algorithm to you.

Very Important Setup Step:

Create a file in your Iterative Algorithms project called SearchAndSort.java. This file will be used throughout the rest of the credit. You will be asked to copy and paste methods into this file. You can then access these methods from any other .java file you create within this or other credits.

Marked Assignment: Binary Search Assignment 1: Blue Pelican (less than one class)

Marked Assignment: Binary Search Assignment A (less than one class)

Marked Assignment: Binary Search Assignment B - Using Strings (less than one class)

>80% Assignment: Binary Search C: Using Files to Create big data sets

>80% Assignment: Searching Objects

Concept 2: Sorting Algorithms

Approximately 3 classes.

All assignments in this concept are due before class on: TBA

Marked Assignment: Sort 1: BubbleSort (1ish class)

Marked Assignment: Sort 2: Selection and Insertion Sort (30 minutes)

Marked Assignment: Sort 3: Sorting Strings (1ish classes)

>80% Assignment: Comparing Algorithms Assignment - see separate document (1ish class)

>80% Test your knowledge: Explain how the algorithms work using a deck of cards. You will be asked to demonstrate the sort algorithms without help. For this year, you only need to explain one sort algorithm plus the binary search. (Next year I am going to make my students demo one for 90% and all three for 100%). You will have only 2 chances to get it right so be ready! Let me know when you are ready for this oral exam.

Concept 3: Merge Algorithms

Approximately 1 class.

Marked Assignment: Merge Algorithm Assignment - see separate document

Concept 4: Major Project (Putting it all together)

Approximately 4 classes.

Marked Assignment: see separate document