Simple C Program - Search & Sort

Avg Bid (AUD)
Project Budget (AUD)
$30 - $30

Project Description:
The key objective of this assignment is to learn how to use primitive set operators to
ef?ciently support more complex operations. Speci?cally, we will focus on extending
the Set ADT in Assignment 1 to support INTERSECT. Higher order operations such
as INTERSECT, UNION, and DIFFERENCE operations can be implemented using
F-SEARCH, PREDECESSOR, and SUCCESSOR operations. Each of the latter three
operators is state-modifying, in that they require that a “current” element has been
determined by a previous operation, and in turn it moves that designator to a different
element as a side effect of its execution. As the sequence of operations unfolds,
the locus of activity shifts through the set being processed. In this project, we will
modify 4 standard search algorithms implemented in Project 1 to support SUCCESSOR
and F-SEARCH. These new operators will in turn be used to implement ef?cient
INTERSECT in sets.
Algorithm 1 Binary Set Intersection
INPUT: Two ordered sets S and T, with |S| = n1 and |T| = n2, and n1 ≤ n2.
OUTPUT: An ordered set of answers A.
1: A ← { }
2: x ← FIRST(S)
3: while x is de?ned do
4: y ← F-SEARCH(T, x)
5: if x = y then
6: APPEND(A, x)
8: return A
When there are exactly two sets, intersection is a straightforward problem. The
simplest and most effective approach is to perform an iterative search for the items in
the smaller set. Algorithm 1 shows a simple two set intersection where each element
in the smaller set S is searched for in the larger set. The search always moves forward
and the eliminator item x chosen is monotonically increasing as we proceed from i =
0 . . . n − 1. The general template of Algorithm 1 leaves us free to choose from a range
of options for implementing F-SEARCH, which will be discussed in the next section.

Skills required:
C Programming
Additional Files: test3.dat
About the employer:
Public Clarification Board
Bids are hidden by the project creator. Log in as the employer to view bids or to bid on this project.
You will not be able to bid on this project if you are not qualified in one of the job categories. To see your qualifications click here.