 # Algorithm Design about Linear Time Median, BFS with Loop Invariant, and Sorting Post Order Numbers

Subject Computer Science Data Structures and Algorithms

## Question

Question 1:
The linear time median find algorithm of the set for which the median is to be found into groups of 5. Why does this not work with groups of 3 elements?

Question 2:
How can we get a list of post order numbers in sorted order without sorting? We want linear time not Nlogn.

Question 3:
Do a breath first search proof using a loop invariant to show that a breath first search is capable of computing all layers of a graph.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Question 1:
We try to apply the same approach as in the case of 5 and 7 elements per sublist.
Since there are 3 elements in the created sublists, at least half of them have 2 elements which are greater or equal with the value of the pivot. More than this, in the current estimation we need to exclude 2 sublists: one containing the pivot and the last sublist (which might have or not precisely 3 elements). This means there are roughly 2*{1/2* ([n/3]-2)} ~ n/3 -4 elements which are either greater or less than median of medians....

This is only a preview of the solution. Please use the purchase button to see the entire solution

## Related Homework Solutions

File Management in Java \$33.00
Computer Science
Java Programming
Structures
Codes
File Management
Formatting
Operating System
Directories
Storage Media
B-Tree
Errors
Attributes
Statements
Variables
Nodes
Input
Output
Two Dynamic Programming Algorithms: Rod Cutting & Minimum Number of Coins Change \$18.00
Dynamic
Programming
Algorithm
Complexity
Recurrence
Rod
Cut
Coin
Change
Amount
Integer
Denomination
Pseudocode
Maximum
DP
Sale
Unit
Piece
Price
Table
Bottom-up
Example
Analysis
Base
Case
Sorting Algorithms in C++ \$25.00
Computer Science
Sorting Algorithms
C++
Selection Sort
Heap Sort
Counting Sort
Integers
Time Complexity
Dataset
Report
Maximal Element
Range
Statements
Variables
Loops
Algorithm That Finds Common Elemens from Two Sorted Lists \$8.00
Computer
Science
Data
Structures
Algorithm
Sorted
List
Common
Element
Comparisons
Length
Number
Dynamic Programming Model for A Version of Job Scheduling Problem \$30.00
Knapsack
Reduction
Algorithm
Complexity
Problem
Job
Scheduling
Dynamic
Programming
OPT
Optimal
Swapping
Exchange
Argument
Playful
Subset