homework 2 searching algorithms

• Part 2 Problem-solving »
• Chapter 3 Solving Problems by Searching
• Edit on GitHub

Chapter 3 Solving Problems by Searching 

When the correct action to take is not immediately obvious, an agent may need to plan ahead : to consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solving agent , and the computational process it undertakes is called search .

Problem-solving agents use atomic representations, that is, states of the world are considered as wholes, with no internal structure visible to the problem-solving algorithms. Agents that use factored or structured representations of states are called planning agents .

We distinguish between informed algorithms, in which the agent can estimate how far it is from the goal, and uninformed algorithms, where no such estimate is available.

3.1 Problem-Solving Agents 

If the agent has no additional information—that is, if the environment is unknown —then the agent can do no better than to execute one of the actions at random. For now, we assume that our agents always have access to information about the world. With that information, the agent can follow this four-phase problem-solving process:

GOAL FORMULATION : Goals organize behavior by limiting the objectives and hence the actions to be considered.

PROBLEM FORMULATION : The agent devises a description of the states and actions necessary to reach the goal—an abstract model of the relevant part of the world.

SEARCH : Before taking any action in the real world, the agent simulates sequences of actions in its model, searching until it finds a sequence of actions that reaches the goal. Such a sequence is called a solution .

EXECUTION : The agent can now execute the actions in the solution, one at a time.

It is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions . The open-loop system means that ignoring the percepts breaks the loop between agent and environment. If there is a chance that the model is incorrect, or the environment is nondeterministic, then the agent would be safer using a closed-loop approach that monitors the percepts.

In partially observable or nondeterministic environments, a solution would be a branching strategy that recommends different future actions depending on what percepts arrive.

3.1.1 Search problems and solutions 

A search problem can be defined formally as follows:

A set of possible states that the environment can be in. We call this the state space .

The initial state that the agent starts in.

A set of one or more goal states . We can account for all three of these possibilities by specifying an \(Is\-Goal\) method for a problem.

The actions available to the agent. Given a state \(s\) , \(Actions(s)\) returns a finite set of actions that can be executed in \(s\) . We say that each of these actions is applicable in \(s\) .

A transition model , which describes what each action does. \(Result(s,a)\) returns the state that results from doing action \(a\) in state \(s\) .

An action cost function , denote by \(Action\-Cost(s,a,s\pr)\) when we are programming or \(c(s,a,s\pr)\) when we are doing math, that gives the numeric cost of applying action \(a\) in state \(s\) to reach state \(s\pr\) .

A sequence of actions forms a path , and a solution is a path from the initial state to a goal state. We assume that action costs are additive; that is, the total cost of a path is the sum of the individual action costs. An optimal solution has the lowest path cost among all solutions.

The state space can be represented as a graph in which the vertices are states and the directed edges between them are actions.

3.1.2 Formulating problems 

The process of removing detail from a representation is called abstraction . The abstraction is valid if we can elaborate any abstract solution into a solution in the more detailed world. The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem.

3.2 Example Problems 

A standardized problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms. A real-world problem , such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data.

3.2.1 Standardized problems 

A grid world problem is a two-dimensional rectangular array of square cells in which agents can move from cell to cell.

Vacuum world

Sokoban puzzle

Sliding-tile puzzle

3.2.2 Real-world problems 

Route-finding problem

Touring problems

Trveling salesperson problem (TSP)

VLSI layout problem

Robot navigation

Automatic assembly sequencing

3.3 Search Algorithms 

A search algorithm takes a search problem as input and returns a solution, or an indication of failure. We consider algorithms that superimpose a search tree over the state-space graph, forming various paths from the initial state, trying to find a path that reaches a goal state. Each node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. The root of the tree corresponds to the initial state of the problem.

The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. The search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root (as in all trees).

The frontier separates two regions of the state-space graph: an interior region where every state has been expanded, and an exterior region of states that have not yet been reached.

3.3.1 Best-first search 

In best-first search we choose a node, \(n\) , with minimum value of some evaluation function , \(f(n)\) .

3.3.2 Search data structures 

A node in the tree is represented by a data structure with four components

\(node.State\) : the state to which the node corresponds;

\(node.Parent\) : the node in the tree that generated this node;

\(node.Action\) : the action that was applied to the parent’s state to generate this node;

\(node.Path\-Cost\) : the total cost of the path from the initial state to this node. In mathematical formulas, we use \(g(node)\) as a synonym for \(Path\-Cost\) .

Following the \(PARENT\) pointers back from a node allows us to recover the states and actions along the path to that node. Doing this from a goal node gives us the solution.

We need a data structure to store the frontier . The appropriate choice is a queue of some kind, because the operations on a frontier are:

\(Is\-Empty(frontier)\) returns true only if there are no nodes in the frontier.

\(Pop(frontier)\) removes the top node from the frontier and returns it.

\(Top(frontier)\) returns (but does not remove) the top node of the frontier.

\(Add(node, frontier)\) inserts node into its proper place in the queue.

Three kinds of queues are used in search algorithms:

A priority queue first pops the node with the minimum cost according to some evaluation function, \(f\) . It is used in best-first search.

A FIFO queue or first-in-first-out queue first pops the node that was added to the queue first; we shall see it is used in breadth-first search.

A LIFO queue or last-in-first-out queue (also known as a stack ) pops first the most recently added node; we shall see it is used in depth-first search.

3.3.3 Redundant paths 

A cycle is a special case of a redundant path .

As the saying goes, algorithms that cannot remember the past are doomed to repeat it . There are three approaches to this issue.

First, we can remember all previously reached states (as best-first search does), allowing us to detect all redundant paths, and keep only the best path to each state.

Second, we can not worry about repeating the past. We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check.

Third, we can compromise and check for cycles, but not for redundant paths in general.

3.3.4 Measuring problem-solving performance 

COMPLETENESS : Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?

COST OPTIMALITY : Does it find a solution with the lowest path cost of all solutions?

TIME COMPLEXITY : How long does it take to find a solution?

SPACE COMPLEXITY : How much memory is needed to perform the search?

To be complete, a search algorithm must be systematic in the way it explores an infinite state space, making sure it can eventually reach any state that is connected to the initial state.

In theoretical computer science, the typical measure of time and space complexity is the size of the state-space graph, \(|V|+|E|\) , where \(|V|\) is the number of vertices (state nodes) of the graph and \(|E|\) is the number of edges (distinct state/action pairs). For an implicit state space, complexity can be measured in terms of \(d\) , the depth or number of actions in an optimal solution; \(m\) , the maximum number of actions in any path; and \(b\) , the branching factor or number of successors of a node that need to be considered.

3.4 Uninformed Search Strategies 

3.4.1 breadth-first search .

When all actions have the same cost, an appropriate strategy is breadth-first search , in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on.

Breadth-first search always finds a solution with a minimal number of actions, because when it is generating nodes at depth \(d\) , it has already generated all the nodes at depth \(d-1\) , so if one of them were a solution, it would have been found.

All the nodes remain in memory, so both time and space complexity are \(O(b^d)\) . The memory requirements are a bigger problem for breadth-first search than the execution time . In general, exponential-complexity search problems cannot be solved by uninformed search for any but the smallest instances .

3.4.2 Dijkstra’s algorithm or uniform-cost search 

When actions have different costs, an obvious choice is to use best-first search where the evaluation function is the cost of the path from the root to the current node. This is called Dijkstra’s algorithm by the theoretical computer science community, and uniform-cost search by the AI community.

The complexity of uniform-cost search is characterized in terms of \(C^*\) , the cost of the optimal solution, and \(\epsilon\) , a lower bound on the cost of each action, with \(\epsilon>0\) . Then the algorithm’s worst-case time and space complexity is \(O(b^{1+\lfloor C^*/\epsilon\rfloor})\) , which can be much greater than \(b^d\) .

When all action costs are equal, \(b^{1+\lfloor C^*/\epsilon\rfloor}\) is just \(b^{d+1}\) , and uniform-cost search is similar to breadth-first search.

3.4.3 Depth-first search and the problem of memory 

Depth-first search always expands the deepest node in the frontier first. It could be implemented as a call to \(Best\-First\-Search\) where the evaluation function \(f\) is the negative of the depth.

For problems where a tree-like search is feasible, depth-first search has much smaller needs for memory. A depth-first tree-like search takes time proportional to the number of states, and has memory complexity of only \(O(bm)\) , where \(b\) is the branching factor and \(m\) is the maximum depth of the tree.

A variant of depth-first search called backtracking search uses even less memory.

3.4.4 Depth-limited and iterative deepening search 

To keep depth-first search from wandering down an infinite path, we can use depth-limited search , a version of depth-first search in which we supply a depth limit, \(l\) , and treat all nodes at depth \(l\) as if they had no successors. The time complexity is \(O(b^l)\) and the space complexity is \(O(bl)\)

Iterative deepening search solves the problem of picking a good value for \(l\) by trying all values: first 0, then 1, then 2, and so on—until either a solution is found, or the depth- limited search returns the failure value rather than the cutoff value.

Its memory requirements are modest: \(O(bd)\) when there is a solution, or \(O(bm)\) on finite state spaces with no solution. The time complexity is \(O(bd)\) when there is a solution, or \(O(bm)\) when there is none.

In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and the depth of the solution is not known .

3.4.5 Bidirectional search 

An alternative approach called bidirectional search simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet.

3.4.6 Comparing uninformed search algorithms 

3.5 Informed (Heuristic) Search Strategies 

An informed search strategy uses domain–specific hints about the location of goals to find colutions more efficiently than an uninformed strategy. The hints come in the form of a heuristic function , denoted \(h(n)\) :

\(h(n)\) = estimated cost of the cheapest path from the state at node \(n\) to a goal state.

3.5.1 Greedy best-first search 

Greedy best-first search is a form of best-first search that expands first the node with the lowest \(h(n)\) value—the node that appears to be closest to the goal—on the grounds that this is likely to lead to a solution quickly. So the evaluation function \(f(n)=h(n)\) .

• DSA Tutorial
• Data Structures
• Linked List
• Dynamic Programming
• Binary Tree
• Binary Search Tree
• Divide & Conquer
• Mathematical
• Backtracking
• Branch and Bound
• Pattern Searching

Introduction to Searching Algorithms

Searching is the fundamental process of locating a specific element or item within a collection of data. This collection of data can take various forms, such as arrays, lists, trees, or other structured representations.

The primary objective of searching is to determine whether the desired element exists within the data, and if so, to identify its precise location or retrieve it. It plays an important role in various computational tasks and real-world applications, including information retrieval, data analysis, decision-making processes, and more.

Importance of Searching in DSA

• Efficiency: Efficient searching algorithms improve program performance.
• Data Retrieval: Quickly find and retrieve specific data from large datasets.
• Database Systems: Enables fast querying of databases.
• Problem Solving: Used in a wide range of problem-solving tasks.

Characteristics of Searching

Understanding the characteristics of searching in data structures and algorithms is crucial for designing efficient algorithms and making informed decisions about which searching technique to employ. Here, we explore key aspects and characteristics associated with searching:

1. Target Element:

In searching, there is always a specific target element or item that you want to find within the data collection. This target could be a value, a record, a key, or any other data entity of interest.

2. Search Space:

The search space refers to the entire collection of data within which you are looking for the target element. Depending on the data structure used, the search space may vary in size and organization.

3. Complexity:

Searching can have different levels of complexity depending on the data structure and the algorithm used. The complexity is often measured in terms of time and space requirements.

4. Deterministic vs Non-deterministic:

Some searching algorithms, like binary search , are deterministic, meaning they follow a clear and systematic approach. Others, such as linear search, are non-deterministic, as they may need to examine the entire search space in the worst case.

Searching Algorithms :

Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.

Below are some searching algorithms:

• Linear Search
• Binary Search
• Ternary Search
• Jump Search
• Interpolation Search
• Fibonacci Search
• Exponential Search

1. Linear Search :

Linear Search, also known as Sequential Search, is one of the simplest and most straightforward searching algorithms. It works by sequentially examining each element in a collection of data(array or list) until a match is found or the entire collection has been traversed.

Algorithm of Linear Search:

• The Algorithm examines each element, one by one, in the collection, treating each element as a potential match for the key you’re searching for.
• If it finds any element that is exactly the same as the key you’re looking for, the search is successful, and it returns the index of key.
• If it goes through all the elements and none of them matches the key, then that means “No match is Found”.

Illustration of Linear Search:

Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30 Start from the first element (index 0) and compare key with each element (arr[i]). Comparing key with first element arr[0]. Since not equal, the iterator moves to the next element as a potential match. Comparing key with next element arr[1]. Since not equal, the iterator moves to the next element as a potential match. Now when comparing arr[2] with key, the value matches. So the Linear Search Algorithm will yield a successful message and return the index of the element when key is found.

Pseudo Code for Linear Search:

LinearSearch(collection, key): for each element in collection: if element is equal to key: return the index of the element return “Not found”

Complexity Analysis of Linear Search:

• Best Case : In the best case, the key might be present at the first index. So the best case complexity is O(1)
• Worst Case: In the worst case, the key might be present at the last index i.e., opposite to the end from which the search has started in the list. So the worst-case complexity is O(N) where N is the size of the list.
• Average Case: O(N)
• Auxiliary Space: O(1) as except for the variable to iterate through the list, no other variable is used.

When to use Linear Search:

• When there is small collection of data.
• When data is unordered.

2. Binary Search :

Binary Search is defined as a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N).

Algorithm of Binary Search:

• Divide the search space into two halves by finding the middle index “ mid ”.
• Compare the middle element of the search space with the key .
• If the key is found at middle element, the process is terminated.
• If the key is smaller than the middle element, then the left side is used for next search.
• If the key is larger than the middle element, then the right side is used for next search.
• This process is continued until the key is found or the total search space is exhausted.

Illustration of Binary Search:

Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , and the target = 23 . Calculate the mid and compare the mid element with the key. If the key is less than mid element, move to left and if it is greater than the mid then move search space to the right . Key (i.e., 23) is greater than current mid element (i.e., 16). The search space moves to the right . Key is less than the current mid 56 . The search space moves to the left . If the key matches the value of the mid element, the element is found and stop search.

Pseudo Code for Binary Search:

Below is the pseudo code for implementing binary search:

binarySearch(collection, key): left = 0 right = length(collection) – 1 while left <= right: mid = (left + right) // 2 if collection[mid] == key: return mid elif collection[mid] < key: left = mid + 1 else: right = mid – 1 return “Not found”

Complexity Analysis of Binary Search:

• Best Case: O(1) – When the key is found at the middle element.
• Worst Case: O(log N) – When the key is not present, and the search space is continuously halved.
• Average Case: O(log N)
• Auxiliary Space : O(1)

When to use Binary Search:

• When the data collection is monotonic (essential condition) in nature.
• When efficiency is required, specially in case of large datasets.

3. Ternary Search :

Ternary Search is a searching algorithm that divides the search space into three parts instead of two, as in Binary Search . It is very useful in the case of unimodal functions .

Algorithm Ternary Search:

• In Ternary Search, start with two midpoints, oneThird and twoThirds , which divide the collection into three roughly equal parts.
• Compare the elements at oneThird and twoThirds with the target key you’re searching for.
• If oneThird contains the key, you’re done and return the index of oneThird .
• If twoThirds contains the key, you’re done and return the index of twoThirds .
• If the key is less than the element at oneThird , eliminate the rightmost one-third of the collection and focus on the left two-thirds.
• If the key is greater than the element at twoThirds , eliminate the leftmost one-third of the collection and focus on the right two-thirds.
• Repeat this process iteratively until either key is found or determine that it’s not present in the collection.

Example of Ternary Search:

Consider an array arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the target = 6 . Ternary Search

Complexity Analysis of Ternary Search:

• Best Case: O(1)
• Worst Case: O(log 3 N)
• Average Case: O(log 3 N)
• Auxiliary Space: O(1)

4. Jump Search :

Jump Search is another searching algorithm that can be used on sorted collections (arrays or lists). The idea is to reduce the number of comparisons by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

Illustration of Jump Search:

Let’s consider the following array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). The length of the array is 16. The Jump search will find the value of 55 with the following steps assuming that the block size to be jumped is 4. Jump from index 0 to index 4; Jump from index 4 to index 8; Jump from index 8 to index 12; Since the element at index 12 is greater than 55, we will jump back a step to come to index 8. Perform a linear search from index 8 to get the element 55.

Time Complexity of Jump Search:

• Time Complexity: O(√n) , where “n” is the number of elements in the collection. This makes it more efficient than Linear Search but generally less efficient than Binary Search for large datasets.
• Auxiliary Space: O(1) , as it uses a constant amount of additional space for variables.

Performance Comparison based on Complexity:

linear search < jump search < binary search

5. Interpolation Search

Interpolation Search is an efficient searching algorithm for sorted collections of data, such as arrays or lists. It is an improvement over Binary Search , particularly when the data is uniformly distributed.

6. Fibonacci Search

Fibonacci Search is an efficient searching algorithm used for finding a target value in a sorted collection, such as an array or list. It is similar in principle to Binary Search but uses Fibonacci numbers to determine the positions to be compared.

7. Exponential Search

Exponential Search is a searching algorithm designed to find a target value in a sorted collection, such as an array or list. It combines elements of Binary Search and Linear Search to efficiently locate the target, especially when its position is near the beginning of the collection.

Easy Problems on Searching:

• Count 1’s in a sorted binary array
• Ceiling in a sorted array
• k largest(or smallest) elements in an array
• Kth smallest element in a row-wise and column-wise sorted 2D array
• Given an array of of size n and a number k, find all elements that appear more than n/k times .

Medium problems on Searching:

• Find a peak element
• Search an element in a sorted and rotated array
• Find the minimum element in a sorted and rotated array
• Find the closest pair from two sorted arrays
• Allocate Minimum Number of Pages from N books to M students
• Assign stalls to K cows to maximize the minimum distance between them

Hard problems on Searching:

• Median of two sorted arrays
• Median of two sorted arrays of different sizes
• Search in an almost sorted array
• Find position of an element in a sorted array of infinite numbers
• Given a sorted and rotated array, find if there is a pair with a given sum
• Longest Increasing Subsequence Size (N log N)

Please Login to comment...

Similar reads, improve your coding skills with practice.

What kind of Experience do you want to share?

Search Algorithms – Linear Search and Binary Search Code Implementation and Complexity Analysis

Search algorithms are a fundamental computer science concept that you should understand as a developer. They work by using a step-by-step method to locate specific data among a collection of data.

In this article, we'll learn how search algorithms work by looking at their implementations in Java and Python.

What is a Search Algorithm?

According to Wikipedia, a search algorithm is:

Any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values.

Search algorithms are designed to check or retrieve an element from any data structure where that element is being stored. They search for a target (key) in the search space.

Types of Search Algorithms

In this post, we are going to discuss two important types of search algorithms:

Linear or Sequential Search

Binary search.

Let's discuss these two in detail with examples, code implementations, and time complexity analysis.

This algorithm works by sequentially iterating through the whole array or list from one end until the target element is found. If the element is found, it returns its index, else -1.

Now let's look at an example and try to understand how it works:

Suppose the target element we want to search is 7 .

Approach for Linear or Sequential Search

Start with index 0 and compare each element with the target

If the target is found to be equal to the element, return its index

If the target is not found, return -1

Code Implementation

Let's now look at how we'd implement this type of search algorithm in a couple different programming languages.

Linear or Sequential Search in Java

Linear or sequential search in python, time complexity analysis.

The Best Case occurs when the target element is the first element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1) .

The Average Case: On average, the target element will be somewhere in the middle of the array. The number of comparisons, in this case, will be N/2. So, the time complexity will be O(N) (the constant being ignored).

The Worst Case occurs when the target element is the last element in the array or not in the array. In this case, we have to traverse the entire array, and so the number of comparisons will be N. So, the time complexity will be O(N) .

This type of searching algorithm is used to find the position of a specific value contained in a sorted array . The binary search algorithm works on the principle of divide and conquer and it is considered the best searching algorithm because it's faster to run.

Now let's take a sorted array as an example and try to understand how it works:

Suppose the target element to be searched is 17 .

Approach for Binary Search

Compare the target element with the middle element of the array.

If the target element is greater than the middle element, then the search continues in the right half.

Else if the target element is less than the middle value, the search continues in the left half.

This process is repeated until the middle element is equal to the target element, or the target element is not in the array

If the target element is found, its index is returned, else -1 is returned.

Binary Search in Java

Binary search in python.

The Best Case occurs when the target element is the middle element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1) .

The Average Case: On average, the target element will be somewhere in the array. So, the time complexity will be O(logN) .

The Worst Case occurs when the target element is not in the list or it is away from the middle element. So, the time complexity will be O(logN) .

How to Calculate Time Complexity:

Let's say the iteration in Binary Search terminates after k iterations.

At each iteration, the array is divided by half. So let’s say the length of array at any iteration is N .

At Iteration 1,

At Iteration 2 ,

At Iteration 3 ,

At Iteration k ,

Also, we know that after k divisions, the length of the array becomes 1 : Length of array = N⁄ 2 k = 1 \=> N = 2 k

If we apply a log function on both sides: log 2 (N) = log 2 (2 k ) \=> log 2 (N) = k log 2 (2)

As (log a (a) = 1) Therefore,=> k = log 2 (N)

So now we can see why the time complexity of Binary Search is log 2 (N).

You can also visualize the above two algorithms using the simple tool built by Dipesh Patil - Algorithms Visualizer .

Order-agnostic Binary Search

Suppose, we have to find a target element in a sorted array. We know that the array is sorted, but we don’t know if it’s sorted in ascending or descending order.

Approach for Order-agnostic Binary Search

The implementation is similar to binary search except that we need to identify whether the array is sorted in ascending order or descending order. This then lets us make the decision about whether to continue the search in the left half of the array or the right half of the array.

We first compare the target with the middle element

If the array is sorted in ascending order and the target is less than the middle element OR the array is sorted in descending order and the target is greater than the middle element, then we continue the search in the lower half of the array by setting end=mid-1 .

Otherwise, we perform the search in the upper half of the array by setting start=mid+1

The only thing we need to do is to figure out whether the array is sorted in ascending order or descending order. We can easily find this by comparing the first and last elements of the array.

Order-agnostic Binary Search in Java

Order-agnostic binary search in python.

There will be no change in the time complexity, so it will be the same as Binary Search.

In this article, we discussed two of the most important search algorithms along with their code implementations in Python and Java. We also looked at their time complexity analysis.

Thanks for reading!

Subscribe to my newsletter

Hello! I am Ashutosh and I enjoy creating things that live on the internet. I was first introduced to programming in my freshman year and since then, I started developing Web projects. I am currently working at Thoughtworks India as an Application Developer.

If you read this far, thank the author to show them you care. Say Thanks

Learn to code for free. freeCodeCamp's open source curriculum has helped more than 40,000 people get jobs as developers. Get started

• Table of Contents
• Course Home
• Assignments
• Peer Instruction (Instructor)
• Peer Instruction (Student)
• Change Course
• Instructor's Page
• Progress Page
• Edit Profile
• Change Password
• Scratch ActiveCode
• Scratch Activecode
• Instructors Guide
• About Runestone
• Report A Problem
• 7.1 Intro to ArrayLists
• 7.2 ArrayList Methods
• 7.3 Traversing ArrayLists with Loops
• 7.4 ArrayList Algorithms
• 7.4.1 Free Response - String Scramble B
• 7.4.2 Free Response - Climbing Club A
• 7.4.3 Free Response - Climbing Club B
• 7.4.4 Free Response - Climbing Club C
• 7.4.5 Free Response - CookieOrder A
• 7.4.6 Free Response - CookieOrder B
• 7.4.7 Free Response - StringFormatter A
• 7.4.8 Free Response - StringFormatter B
• 7.4.9 Free Response - Delimiters A
• 7.4.10 Free Response - Delimiters B
• 7.4.11 Free Response - Grid World A
• 7.5 Searching Algorithms
• 7.6 Sorting Algorithms
• 7.7 Ethics of Data Collection and Data Privacy
• 7.8 ArrayList Summary
• 7.9 Input Files (Optional)
• 7.10 Mixed Up Code Practice
• 7.11 Toggle Mixed Up or Write Code Practice
• 7.12 Code Practice with ArrayLists
• 7.13 Multiple-Choice Exercises
• 7.13.1 Easier Multiple Choice Questions
• 7.13.2 Medium Multiple Choice Questions
• 7.13.3 Hard Multiple Choice Questions
• 7.13.4 Easier Search/Sort Multiple Choice Questions
• 7.13.5 Medium Search/Sort Multiple Choice Questions
• 7.13.6 Hard Search/Sort Multiple Choice Questions
• 7.14 College Board Celebrity and Data Labs
• 7.4.11. Free Response - Grid World A" data-toggle="tooltip">
• 7.6. Sorting Algorithms' data-toggle="tooltip" >

Time estimate: 90 min.

7.5. Searching Algorithms ¶

Computers store vast amounts of data. One of the strengths of computers is their ability to find things quickly. This ability is called searching . For the AP CSA exam you will need to know both linear (sequential) search and binary search algorithms.

The following video is also on YouTube at https://youtu.be/DHLCXXX1OtE . It introduces the concept of searching including sequential search and binary search.

Sequential or Linear search typically starts at the first element in an array or ArrayList and looks through all the items one by one until it either finds the desired value and then it returns the index it found the value at or if it searches the entire array or list without finding the value it returns -1.

Binary search can only be used on data that has been sorted or stored in order. It checks the middle of the data to see if that middle value is less than, equal, or greater than the desired value and then based on the results of that it narrows the search. It cuts the search space in half each time.

If binary search requires the values in an array or list to be sorted, how can you do that? There are many sorting algorithms which are covered in the next lesson.

7.5.1. Sequential Search ¶

Sequential or linear search can be used to find a value in unsorted data. It usually starts at the first element and walks through the array or list until it finds the value it is looking for and returns its index. If it reaches the end of the array or list without finding the value, the search method usually returns a -1 to show that it didn’t find the value in the array or list. Click on Show CodeLens below to see linear search in action.

The code for sequentialSearch for arrays below is from a previous AP CSA course description. Click on the Code Lens button to see this code running in the Java visualizer.

Here is the same search with an ArrayList . The same algorithms can be used with arrays or ArrayList s, but notice that size() and get(i) are used with ArrayList s instead of length and [i] which are used in arrays. Many of our examples will use arrays for simplicity since with arrays, we know how many items we have and the size won’t change during runtime. There are methods such as contains that can be used in ArrayLists instead of writing your own algorithms. However, they are not in the AP CSA Java subset.

Here is a linear search using ArrayLists. Notice that size() and get(i) is used with ArrayLists instead of length and [i] which are used in arrays. Click on the Code Lens button to step through this code in the visualizer.

7-5-4: Which will cause the longest execution of a sequential search looking for a value in an array of integers?

• The value is the first one in the array
• This would be true for the shortest execution. This would only take one execution of the loop.
• The value is in the middle of the array
• Why would this be the longest execution?
• The value is the last one in the array
• There is one case that will take longer.
• The value isn't in the array
• A sequential search loops through the elements of an array or list starting with the first and ending with the last and returns from the loop as soon as it finds the passed value. It has to check every value in the array when the value it is looking for is not in the array.

7-5-5: Which will cause the shortest execution of a sequential search looking for a value in an array of integers?

• This would only take one execution of the loop.
• Are you thinking of binary search?
• This would be true if you were starting at the last element, but the algorithm in the course description starts with the first element.
• This is true for the longest execution time, but we are looking for the shortest.

You can also look for a String in an array or list, but be sure to use equals rather than == . Remember that == is only true when the two references refer to the same String object, while equals returns true if the characters in the two String objects are the same.

Demonstration of a linear search for a String. Click on the Code Lens button or the link below to step through this code.

7.5.2. Binary Search ¶

How do you search for something in a phone book or dictionary that is in alphabetical or numerical order? If you’re looking for something beginning with M or on page 100 in a 200 page book, you wouldn’t want to start with page 1. You would probably start looking somewhere in the middle of the book. This is the idea behind binary search .

If your array or list is already in order (sorted), binary search will on average find an element or determine that it is missing much more quickly than a linear search. But binary search can only be used if the data is sorted.

Binary search keeps dividing the sorted search space into half. It compares a target value to the value in the middle of a range of indices. If the value isn’t found it looks again in either the left or right half of the current range. Each time through the loop it eliminates half the values in the search area until either the value is found or there is no more data to look at. See the animation below from https://github.com/AlvaroIsrael/binary-search :

Binary search calculates the middle index as left + right / 2 where left starts out at 0 and right starts out at the array length - 1 (the index of the last element). Remember that integer division gives an integer result so 2.5 becomes 2. It compares the value at the middle index with the target value (the value you are searching for). If the target value is less than the value at the middle it sets right to middle minus one. If the target value is greater than the value at the middle it sets left to middle plus one. Otherwise the values match and it returns the middle index. It also stops when left is greater than right which indicates that the value wasn’t found and it returns -1.

The code for binarySearch below is from the AP CSA course description. A recursive version of this algorithm will be covered in Unit 10.

Demonstration of iterative binary search. Click on the Code Lens button to step through this code.

You can also use binary search with a String array. But, when you look for a String , be sure to use compareTo method rather than < or > which can only be used with primitive types. Remember how the String method compareTo works:

int compareTo(String other) returns a negative value if the current string is less than the other string, 0 if they have the same characters in the same order, and a positive value if the current string is greater than the other string.

Demonstration of binary search with strings using compareTo. Click on the Code Lens button to step through the code.

7.5.3. Runtimes ¶

How do we choose between two algorithms that solve the same problem? They usually have different characteristics and runtimes which measures how fast they run. For the searching problem, it depends on your data.

Binary search is much faster than linear search, especially on large data sets, but it can only be used on sorted data. Often with runtimes, computer scientist think about the worst case behavior . With searching, the worst case is usually if you cannot find the item. With linear search, you would have to go through the whole array before realizing that it is not there, but binary search is much faster even in this case because it eliminates half the data set in each step. We can measure an informal runtime by just counting the number of steps.

Here is a table that compares the worst case runtime of each search algorithm given an array of n elements. The runtime here is measured as the number of times the loop runs in each algorithm or the number of elements we need to check in the worst case when we don’t find the item we are looking for. Notice that with linear search, the worst case runtime is the size of the array n, because it has to look through the whole array. For the binary search runtime, we can calculate the number of times you can divide n in half until you get to 1. So, for example 8 elements can be divided in half to narrow down to 4 elements, which can be further divided in half to narrow down to 2 elements, which can be further divided in half to get down to 1 element, and then if that is wrong, to 0 elements, so that is 4 divisions or guesses to get the answer (8->4->2->1->0). In the table below, every time we double the size of N, we need at most one more guess or comparison with binary search. It’s much faster than linear search!

Runtimes can be described with mathematical functions. For an array of size n, linear search runtime is a linear function, and binary search runtime is a function of log base 2 of n (or log n + 1 comparisons). This is called the big-O runtime function in computer science, for example O(log n) vs. O(n). You can compare the growth of functions like n and log 2 n as n, the data size, grows and see that binary search runs much faster for any n. You don’t need to know the log n runtime growth function for the AP exam, but you should be able to calculate how many steps binary search takes for a given n by counting how many times you can divide it in half. Or you can start at 1 and keep a count of how many times you can double it with the powers of two (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, etc.) until you reach a number that is slightly above n.

7-5-9: Which will cause the shortest execution of a binary search looking for a value in an array of integers?

• This would be true for sequential search, not binary.
• If the value is in the middle of the array the binary search will return after one iteration of the loop.
• How would that be the shortest in a binary search?

7-5-10: Which of the following conditions must be true in order to search for a value using binary search?

• You can use a binary search on any type of data that can be compared, but the data must be in order.
• You can use a binary search on any type of data that can be compared.
• The only requirement for using a Binary Search is that the values must be ordered.
• The array can contain duplicate values.

7-5-11: How many times would the loop in the binary search run for an array int[] arr = {2, 10, 23, 31, 55, 86} with binarySearch(arr,55)?

• It will first compare with the value at index 2 and then index 4 and then return 4.
• This would be true if we were looking for 23.
• This would be true if we were looking for 31.

7-5-12: If you had an ordered array of size 500, what is the maximum number of iterations required to find an element with binary search?

• approximately 15 times
• How many times can you divide 500 in half?
• approximately 9 times
• You can divide 500 in half, 9 times, or you can observe that 2^9 = 512 which is slightly bigger than 500.

7.5.4. Programming Challenge : Search Runtimes ¶

Let’s go back to the spellchecker that we created in Unit 6. Here is a version of the spellchecker below that reads the dictionary file into an ArrayList . The advantage of using an ArrayList instead of an array for the dictionary is that we do not need to know or declare the size of the dictionary in advance.

In Unit 6, we used linear search to find a word in the dictionary. However, the dictionary file is actually in alphabetical order. We could have used a much faster binary search algorithm! Let’s see how much faster we can make it.

Write a linear search method and a binary search method to search for a given word in the dictionary using the code in this lesson as a guide. You will need to use size and get(i) instead of [] to get an element in the ArrayList dictionary at index i. You will need to use the equals and compareTo methods to compare Strings. Have the methods return a count of how many words they had to check before finding the word or returning.

This spellchecker uses an ArrayList for the dictionary. Write a linearSearch(word) and a binarySearch(word) method. Use get(i) , size() , equals , and compareTo . Return a count of the number of words checked.

Run your code with the following test cases and record the runtime for each word in this Google document (do File/Make a Copy) also seen below to record your answers.

What do you notice? Which one was faster in general? Were there some cases where each was faster? How fast were they with misspelled words? Record your answers in the window below.

7-5-14: After you complete your code, write in your comparison of the linear vs. binary search runtimes based on your test cases. Were there any cases where one was faster than the other? How did each perform in the worst case when a word is misspelled?

7.5.5. Summary ¶

There are standard algorithms for searching.

Sequential/linear search algorithms check each element in order until the desired value is found or all elements in the array or ArrayList have been checked.

The binary search algorithm starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in each iteration until the desired value is found or all elements have been eliminated.

Data must be in sorted order to use the binary search algorithm. This algorithm will be covered more in Unit 10.

Informal run-time comparisons of program code segments can be made using statement execution counts.

Algorithms part 2 - Searching and sorting

Curriculum > KS4 > Unit

The main focus of this unit is on searching and sorting algorithms, though other topics are covered such as computational thinking, flowcharts and tracing algorithms. Students will have opportunities to analyse, interpret, modify and implement a range of algorithms. (NOTE: there are two learning graphs)

Learning graph

Summative assessment, summative answer.

• Lesson 4 Linear search Log in to download
• Lesson 5 Binary search Log in to download
• Lesson 6 Comparing searching algorithms Log in to download
• Lesson 7 Bubble sort Log in to download
• Lesson 8 Insertion sort Log in to download
• Lesson 9 Coding sorting algorithms Log in to download
• Lesson 10 Merge sort Log in to download
• Lesson 11 Algorithms review Log in to download
• Lesson 12 Summative assessment Log in to download

Help us make these resources better

Or email us at [email protected]

CS 161: Design and Analysis of Algorithms (Spring 2017)

[ Course Schedule | Midterm and Final | Homework Assignments | Recitations | Resources ]

Instructor: Mary Wootters (email: marykw at cs)

Location and time: Monday and Wednesday 3:00 PM - 4:20 PM, Hewlett 200

Important! Sign up on Piazza for discussions and announcements. We strongly encourage discussion and asking questions on Piazza. Questions to the course staff (that are not addressed to a specific person) can be sent using a private post in Piazza.

Course Description This course will cover the basic approaches and mindsets for analyzing and designing algorithms and data structures. Topics include the following: Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, string searching.

Prerequisites: CS 103 or CS 103B; CS 109 or STATS 116.

Requirements: 7 homework assignments (35%), a midterm (25%), and a final exam (40%). There will be no late days. However, we will drop your lowest homework grade. Note: In order to compute scores on the homework (in deciding which to drop and for averaging), we will normalize the scores by the number of points possible. That is, if 40 points were possible on the homework and you scored a 35, this would count as 35/40 = 0.875.

Course Schedule and Lecture Notes

Topics and readings for future lectures are tentative and may be changed as the course proceeds. The readings refer to the 3rd edition of CLRS (see Resources below), but older editions should be fine as well.

Midterm and Final

Midterm: Wednesday, May 10, in class (Hewlett 200, 3:00 pm - 4:20 pm) - [ problems ] [ solutions ] Final: Friday, June 9, Hewlett 200, 3:30 pm - 6:30pm Final Problems and Solutions

Both the midterm and final are closed-book. In the midterm, you are allowed to bring one letter-sized double-sided page of notes, that you have prepared yourself . In the final, you are allowed to bring two letter-sized double-sided page of notes that you have prepared yourself .

The following practice exams are posted here as a resource; the material covered is similar to what we covered this quarter, but not identical.

Practice Midterm 1 Solutions to the Practice Midterm 1 Practice Midterm 2 Solutions to the Practice Midterm 2

Finals from Previous Years

The following final exams are taken from previous offerings of the class. They are posted here as a resource, but the material covered in them may differ what the material covered this quarter, and their structure may differ from this quarter's final exam.

Final Exam 2016 Final Exam 2016 Solutions

Homework Assignments

• Homework 1 (released 4/7, due 4/14 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
• Homework 2 (released 4/14, due 4/21 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
• Homework 3 (released 4/21, due 4/28 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
• Homework 4 (released 4/28, due 5/8 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
• Homework 5 (released 5/12, due 5/19 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
• Homework 6 (released 5/19, due 5/26 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
• Homework 7 (released 5/26, due 6/2 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
• There is no Homework 8. However, if you want some practice on Minimum Cut and Maximum Flow, here are some practice problems (with solutions) from Kleinberg and Tardos: Solved exercise 1 here on randomized algorithms in graphs and Solved exercises 1 and 2 here on min-cut/max-flow .
• Homework 2 (released 10/7, due 10/14 at 3pm) Assignment Solutions
• Homework 3 (released 10/14, due 10/21 at 3pm) Assignment Solutions
• Homework 4 (released 10/21, due 10/28 at 3pm) Assignment Solutions
• Homework 5 (released 11/4, submission deadline extended - see Piazza) Assignment Solutions
• Homework 6 (released 11/12, due 11/19 at 11:59pm, late submission until 11/21 at 11:59pm) Assignment Solutions
• Homework 7 (released 11/19, due 12/2 at 3pm) Assignment Solutions

Submission Instructions and Policies

• All assignments are posted on Fridays, and are due the next Friday at 3pm.
• All assignments must be submitted electronically as a PDF file using Gradescope (access code: MWRJ89).
• All assignments should be typed using LaTeX, LyX, Microsoft Word, or a similar editor. For first time LaTeX users, see the resources section. Scanned handwritten assignments are not accepted.
• Each student is allowed to discuss the assignment (verbally) with any classmates enrolled in CS161. Each student should write and submit their own solution. Solutions must be written in your own words. When you submit the assignment, you should indicate with whom you have discussed the solutions.
• You are allowed to use textbooks and resources that are listed on this page. You may not google around hoping to find a similar problem worked out, but you may use other resources (like Wikipedia, other lecture notes, textbooks) that you find online. If you are using other resources, you must properly cite them, and you must prove any statement from them that you use.
• You are not allowed to look for the answers for any of the homework assignments (online or otherwise). If you accidentally find a solution for a question, do not read it (if it is not too late), and indicate that clearly on your assignment (including where you found the solution).
• Please follow the honor code .
• Late homeworks will not be accepted. However, we will consider your highest 6 (out of 7) homework grades when computing your final course grade.
• For each assignment, regrade requests will open on Gradescope on Wednesday (after the grades have been published) and close on Sunday.
• Please provide a detailed explanation for your regrade request.
• Note that we may regrade any part of the assignment, and the new grade may be greater than, equal to, or less than the original grade.

Recitations

• Section 1 : Loop and recursion invariants, weak and strong induction.
• Section 2 [ problems ] [ solutions ]: Selection, big-O, and recurrences.
• Section 3 : Randomized algorithms.
• Section 4 [ problems ] [ solutions ]: Universal hash functions, randomly built binary search trees.
• YouTube series on red-black trees: Introduction , Rotations , Insertions 1 , Insertions 2
• Section 5 : Midterm review.
• Section 6 [ problems ] [ solutions ]: Graphs.
• Section 7 : Dynamic programming.
• Section 8 [ problems ] [ solutions ]: Greedy algorithms.
• Recitation 1 (week 1) Solutions
• Recitation 2 (week 2) Solutions
• Recitation 4 (week 4) Solutions [Slides from David's Recitation]
• Recitation 5 (week 5) [Slides from David's Recitation]
• Recitation 6 (week of 3/7) Recitation Solutions
• Recitation 3 (10/14-10/19) Solutions
• Recitation 4 (10/21-10/26) Solutions
• Recitation 5 (11/4-11/9) Solutions
• Recitation 6 (11/11-11/16) Solutions
• Recitation 7 (11/18-11/30) Solutions
• Recitation 8 (12/2-12/7) Solutions

The main textbook we use is: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 3rd Edition, MIT Press The book is available online through the Stanford library.

We will also occasionally use: Jon Kleinberg, Éva Tardos, Algorithm Design , Pearson/Addison-Wesley Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms , McGraw-Hill Education

Homework Resources

• Expected level of detail: Your homework solutions should make it clear that you understand what's going on. This means that they should have enough detail to convince the grader that your solution is correct; but they needn't have so much detail that it obfuscates the main points. This is a difficult balance to strike. To help you, here is an example of what we are looking for on the homework assignments.
• Read the submission instructions and policies above.
• Read the submission instructions and policies above. Seriously, do it.
• Look over the problems early. Algorithm design takes time, and even simple algorithms can be surprisingly tricky to develop. We suggest reading over all the problems as soon as the problem set goes out so that you will have the time to play around with them over the course of the week.
• Work on your own before working in a group or attending office hours. Although you are allowed to work in groups, we strongly recommend not doing so until you have already thought about each of the problems and tried out various solutions. The problem sets tend to have solutions that are not particularly complicated but which require some insight to discover. If you immediately start working on the problem sets in a group, you will miss out on the opportunity to come up with these insights on your own.

LaTeX Resources

We strongly recommend typesetting solutions to the homework assignments using LaTeX. LaTeX provides a convenient way to produce high-quality documents and it is the standard used for typesetting computer science papers.

Guide: An introduction to LaTeX can be found here . Other guides can be found at howtoTeX and!--> Wikibooks and NYU .

Online environments: If you do not wish to install LaTeX, ShareLaTeX and Overleaf are online environments that compile previews of your documents as you type and allow you to share documents with collaborators (this feature won't be useful in this course, though). As a Stanford student, you get a free Overleaf Pro account.

LyX: LyX is a version of LaTeX with graphical interface.

Finding mathematical symbols: The introduction mentioned above contains a table of mathematical symbols in LaTeX. Alternatively, consider Detexify .

Examples: homework1.tex homework2.tex homework3.tex homework4.tex homework5.tex homework6.tex homework7.tex --> LaTeX Homework Template: Here is an example of of a LaTeX document, including several elements (section numbering, pseudocode, tables, images, etc) that you might find helpful.

Provide details on what you need help with along with a budget and time limit. Questions are posted anonymously and can be made 100% private.

Studypool matches you to the best tutor to help you with your question. Our tutors are highly qualified and vetted.

Your matched tutor provides personalized help according to your question details. Payment is made only after you have completed your 1-on-1 session and are satisfied with your session.

• Homework Q&A
• Become a Tutor

All Subjects

Mathematics

Programming

Health & Medical

Engineering

Computer Science

Foreign Languages

Access over 35 million academic & study documents

Unit 6 algorithms homework 2 answers.

Sign up to view the full document!

24/7 Study Help

Stuck on a study question? Our verified tutors can answer all questions, from basic  math  to advanced rocket science !

Similar Documents

working on a study question?

Studypool is powered by Microtutoring TM

Copyright © 2024. Studypool Inc.

Studypool is not sponsored or endorsed by any college or university.

Ongoing Conversations

Access over 35 million study documents through the notebank

Get on-demand Q&A study help from verified tutors

Read 1000s of rich book guides covering popular titles

Sign up with Google

Sign up with Facebook

Already have an account? Login

Login with Google

Login with Facebook

Don't have an account? Sign Up

CS:3330:0001 (22C:31) Algorithms, Fall 2019

Syllabus , Announcements , Homeworks , Exams , Projects , Lecture Notes ,

Announcements

Computer projects, lecture notes, online resources.

• Java Tutorials
• Introduction to Java
• Eclipse Video Tutorials
• Eclipse Java Tutorials
• Cool animation of different sorting algorithms . Check out bubble sort vs quick sort.

• 0.00  $ 0 items

 Homework Two: Recursion, Searching, and Sorting Algorithms Solved

20.00  $

If Helpful Share:

Description

• Arrays (20pts)

  Exercise One (10pts) Design and implement and algorithm that compare two strings and check if they are reversed. For instance, if the two strings are google and elgoog, then the method returns 1. If the two strings are “data”, “ata” then the method returns 0. The algorithm should ignore white spaces, lower/upper cases.

Specify the running time of your algorithm in terms of Big-O notation. Attach Exercise One.doc that explains the running time.

• Exercise Two (10pts) Design and implement an algorithm that takes a set of strings. Then, for every three consecutive strings (assuming the list of strings is larger than 3 and the number of strings in your sentence is a multiple of 3) leave only the shortest of the three. In case two string among the three are of the same length then you leave the first one.

For instance, consider the following set of strings: “Other entries include a historic district in Charlottesville Virginia cut-flower greenhouse complex”  à “Other a in complex”

Specify the running time of your algorithm in terms of Big-O notation. Attach Exercise Two.doc that explains the running time.

• Recursion (50pts)
• (10pts) Design and implement a binary recursive algorithm that finds the maximum number in array of size n.
• (20pts) Design and implement a recursive algorithm that returns the number of zeroes in the binary representation of N.

In this exercise the input to the algorithm must be an integer N. Your algorithm should not calculate the binary representation of N but recursively finds the number of zeroes in the binary representation of N. You are NOT allowed to use arrays.

• (20pts)Implement a recursive algorithm that checks if word is A palindrome.

A palindrom is a word or number that is identical when read both forwards and backwards. Please ignore all punctuation. Some simple palindromes include  kayak  radar dad

  Sorting (60pts)

3.1. Provide your own implementation of the six algorithms mentioned bellow.  You must provide your own code. Code copied form the internet or modified will be result into a Zero grade for the entire homework.

Provide a table (attached in a word document) where you compare the running time of the sorting algorithms mentioned bellow in terms of best case and worst case running time.  

  Bubble Sort Non-Recursive (5pts)

• Bubble Sort Recursive (5pts)
• Selection Sort (Non-recursive) (5pts)
• Insertion Sort (Non-recursive) (5pts)
• Merge Sort (Recursive) (5pts)
• Quick Sort (Recursive) (5pts)

3.2       Consider the array mentioned above, show a step by step illustration (either by hand or written in a word document) of applying the sorting algorithms mentioned to the array.

Include all your answers for this HW into a zip file.

Related products

Program #5 Solution

Solution Programming Problem Chapter 9-1 Pg. 447

Racket programming (part 2).