Systems Programming Binary Search Assignment

Systems Programming Binary Search Assignment

10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 1/10
BST Assignment 1
Due Sunday by 11:59pm Points 100 Submitting a file upload File Types zip
Available Aug 23 at 12am – Oct 28 at 11:59pm 2 months
Start Assignment
Assignment #1 Instructions: Sorting with Binary Search
Tree

Systems Programming Binary Search Assignment

Through this programming assignment, the students will learn to do the following:
1. Know how to process command line arguments.
2. Perform basic file I/O.
3. Use structs, pointers, and strings.
4. Use dynamic memory.
This assignment asks you to sort the words in an input file (or from standard input) and print the sorted
words to an output file (or standard output). Your program, called bstsort (binary search tree sort), will
take the following command line arguments:
% bstsort [-c] [-l] [-o output_file_name] [input_file_name]

Systems Programming Binary Search Assignment

If -c is present, the program needs to compare the strings in upper case. If -l is present, the program
needs to compare the strings in lower case. Otherwise, the case stays as read in. Note that you cannot
have a -c and a -l. If the output_file_name is given with the -o option, the program will output the sorted
words to the given output file; otherwise, the output shall be the standard output. Similarly, if the
input_file_name is given, the program will read from the input file; otherwise, the input will be from the
standard input. You must use getopt() to parse the command line arguments to determine the cases.
In addition to parsing and processing the command line arguments, your program needs to do the
following:
1. You need to construct a binary search tree as you read from input. A binary search tree is a binary
tree. Each node can have at most two child nodes (one on the left and one on the right), both or
either one can be empty. If a child node exists, it’s the root of a binary search tree (we call subtree).
Each node contains a key (in our case, it’s a word which is a string). If the left subtree of a node
exists, it contains only nodes with keys less than the node’s key. If the right subtree of a node exists,
it contains only nodes with keys greater than the node’s key. You can look up binary search tree on
10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 2/10
the web or in your Data Structure textbook. Note that you do not need to balance the binary search
tree (that is, you can ignore all those rotation operations) in this assignment.
2. Initially the tree is empty (that is, the root is null). The program reads from the input file (or stdin) one
word at a time; As long as you continue reading words, if the word is not already in the tree, it should
create a tree node that stores a pointer to the word and then insert the tree node to the binary search
tree. If the word exists, then do not create a node. All duplicate words are ignored.
3. An empty line would indicate the end of input for stdin, an end of file would indicate the end of input
for an input file.

Systems Programming Binary Search Assignment

4. You must develop a string comparison function. You must not use the strcmp() and strcasecmp()
functions provided by the C library. You must implement your own version. You will be comparing the
ASCII values. Note that using ASCII, all capital letters come before all lower case letters.
5. Once the program has read all the input (when EOF is returned or a blank line encountered), the
program then performs an in-order traversal of the binary search tree to print out all the strings one
word at a time to the output file or stdout. The output would be one word per line. If the -c option was
used then use all capital letters, if the -l option was selected then use all lower case letters.
6. Before the program ends, it must reclaim the tree! You can do this by performing a post-order
traversal, i.e., reclaiming the children nodes before reclaiming the node itself. Make sure you also
reclaim the memory occupied by the string as well.
7. It is required that you use getopt for processing the command line and use malloc or calloc and free
functions for dynamically allocating and deallocating nodes and the buffers for the strings. It is
required that you implement your own string comparison function instead of using the corresponding
libc functions.
Here’s are some examples:
crahn@ocelot:~ 105% cat infile1
apple
apple
APPLE
APPLE
Apple
banana
BANANA
crahn@ocelot:~ 106% bstsort -l infile1
apple
banana
crahn@ocelot:~ 107% bstsort -c infile1
APPLE
BANANA
crahn@ocelot:~ 108% bstsort -o outfile1 infile1
crahn@ocelot:~ 109% cat outfile1
APPLE
Apple
BANANA
apple
banana
crahn@ocelot:~ 110%
Please submit your work as one zip file. Follow the instructions below carefully (to avoid unnecessary
loss of grade):
10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 3/10
BST Assignment 1 Rubric Fall 2021
You should submit the source code and the Makefile in the zip file called FirstnameLastnameA1. One
should be able to create the executable by simply ‘make’. The Makefile should also contain a ‘clean’
target for cleaning up the directory (removing all object files at a minimum). Make sure you don’t include
intermediate files: *.o, executables, *~, etc., in your submission. (There’ll be a penalty for including
unnecessary intermediate files). Only two files should be included unless permission is given for more,
those would be bstsort.c, and Makefile. If you feel a need to include a bstsort.h file, please send me a
note with a copy of the file asking for permission.
Late submissions will have a deduction as per the syllabus.
If the program does not compile and do something useful when it runs it will not earn any
credit.
If a program is plagiarized, it will not earn any credit.
If a program uses a bstsort.h file without permission it will not earn any credit.
10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 4/10
Criteria Ratings Pts
2 pts
2 pts
5 pts
2 pts
2 pts
Zip File named FirstNameLastNameA1.zip using
the student name.
2 pts
Meets
Requirements
Submission
file named
exactly as
specified.
1 pts
Minor Errors
Submission file has
extra spaces,
underscores or
characters in the
name
0 pts
Needs
Improvement
Submission
file not as
specified.
Makefile named Makefile. 2 pts
Meets
Requirements
Makefile named
correctly with
proper
capitalization.
1 pts

Systems Programming Binary Search Assignment

Minor Errors
Makefile spelled
with a lower
case m as in
makefile
0 pts
Needs
Improvement
No Makefile
included.
Typing make at the command line should create
executable named bstsort.
5 pts
Meets
Requirements
Typing make
at the
command line
creates an
executable file
name bstsort
3 pts
Minor Errors
Typing make at
the command line
creates an
executable named
anything close to
bstsort
0 pts
Needs
Improvement
Typing make at
the command
line creates an
executable
named anything

Systems Programming Binary Search Assignment

else.
Make file should include a clean target which
removed .o files.
2 pts
Meets
Requirements
A clean target
is included in
the Makefile.
1 pts
Minor Errors
The clean target is
included, but it does
not remove the
needed files.
0 pts
Needs
Improvement
The clean
target is not
included.
There should be no warnings during compile on
ocelot.
2 pts
Meets
Requirements
There were no
warnings when
compiling on
ocelot.
1 pts
Minor Errors
Program has
1-2 warnings
when running
on ocelot.
0 pts
Needs
Improvement
Program has 3 or
more warnings
when running on
ocelot.
10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 5/10
Criteria Ratings Pts
2 pts
2 pts
2 pts
2 pts
2 pts
2 pts
Only bstsort.c and Makefile are included in the
input unless permission is given for any other
files. This includes additional directories.
Extracting all files from your zip file should show
only those listed files.
2 pts
Meets
Requirements
Only the
requested files
were included.
1 pts
Minor Errors
Other files of
folders were
included.
0 pts
Needs
Improvement
Not submitted
as directed.
Comment at the top of the file needs student
name
2 pts
Meets
Requirements
Student name
was included.
0 pts
Minor Errors
Student name was
not included.
0 pts
Needs
Improvement
N/A
Comment at the top of the file needs the
affirmation of Originality
2 pts
Meets
Requirements
Affirmation of
originality was
included.
0 pts
Minor Errors
Affirmation of
originality was
not included.
0 pts
Needs
Improvement
N/A
Comment at the top needs a program description 2 pts
Meets
Requirements
A good
program
description
was included.
1 pts
Minor Errors
A description was
included, but it was
not detailed enough.
0 pts
Needs
Improvement
No program
description
was included.
Program should have consistent indentation.
Consistent indentation with curly braces lined up
in either of the two standard formats. They can
be lined up right above each other or the opening
curly brace can be on the right end of the line
above with the block begins.
2 pts
Meets
Requirements
The program was
indented well and
curly braces were
consistent.
1 pts
Minor Errors
Indentation
not consistent
in one or two
places.
0 pts
Needs
Improvement
Indentation not
consistent in
three or more
places.

Systems Programming Binary Search Assignment

Program should have good comments
throughout the body and describing each
function.
2 pts
Meets Requirements
Good comments are
included throughout the
program in the body of
the functions and at the
top of each function.
1 pts
Minor
Errors
Some
comments
are
included,
but more
0 pts
Needs
Improvement
No comments
are included.
10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 6/10
Criteria Ratings Pts
2 pts
5 pts
2 pts
4 pts
2 pts
are
needed. Code should be readable with good variable and
function names.
2 pts
Meets
Requirements
Variable and
function names
are well thought
out.
1 pts
Minor Errors
Variable and
function names
have minor
problems.
0 pts
Needs
Improvement
Variable and
function
names are not
good.
No use of break or continue statements except in
a switch.
5 pts
Meets
Requirements
There were no
break or a
continue
statements
other than
breaks in a
switch
statement.
2 pts
Minor Errors
A break or a
continue
statement was
used in the
program other
than in a switch
statement.
0 pts
Needs
Improvement
More than one
break or
continue
statements
were used or
not submitted
as requested.
Program must exit with a return code of 0 on
success and an error code in other cases.
2 pts
Meets
Requirements
Program exits
with a 0 on
success and
an error code
for other cases.
1 pts
Minor Errors
Program exits
with a 0 on
success, but
not a good error
code on failure.
0 pts
Needs
Improvement
Program does not
exit with a 0 on
success and an
error code for
other cases.
The program used getopt to parse the command
line.
4 pts
Meets
Requirements
The program used
getopt using the
sample code
provided.
2 pts
Minor Errors
The program
used getopt
incorrectly.
0 pts
Needs
Improvement
The program
did not use
getopt.
Whenever an error occurs on the command line
the user is given the usage statement and an
appropriate error message if needed.
2 pts
Meets
Requirements
The usage
statement was
included
wherever
needed.
1 pts
Minor Errors
The usage
statement is
included only
some times.
0 pts
Needs
Improvement
The usage
statement is not
included when
needed.
10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 7/10
Criteria Ratings Pts
2 pts
2 pts
2 pts
2 pts
2 pts
The call to getopt had the correct parse string. 2 pts
Meets
Requirements
Parse string
was correct.
1 pts
Minor Errors
Parse string had a
minor error.
0 pts
Needs
Improvement
Parse string
was wrong.
A node structure is included. It should include the
string, and the left and right pointers to child
nodes.
2 pts
Meets
Requirements
Good node
structure is
included.
1 pts
Minor Errors
Node structure is
included, but it is not
complete or has
errors.
0 pts
Needs
Improvement
Node
structure is
incorrect.
The program must dynamically allocate the
memory for the nodes.
2 pts
Meets
Requirements
Used malloc or
calloc to
dynamically
allocate memory
for the nodes.
1 pts
Minor Errors
Used malloc or
calloc wrong to
dynamically
allocate the
nodes.
0 pts
Needs
Improvement
Did not use
dynamic
memory
allocation for
the nodes.
The program must dynamically allocate the
memory for the strings inside the nodes.
2 pts
Meets
Requirements
Used malloc or
calloc to
dynamically
allocate memory
for the strings
inside the nodes.
1 pts
Minor Errors
Used malloc or
calloc wrong to
dynamically
allocate the
strings inside
the nodes.
0 pts
Needs
Improvement
Did not use
dynamic
memory
allocation for
the strings
inside the
The program mus nodes. t free the strings after the
output is completed.
2 pts
Meets
Requirements
Strings are freed
after they are not
needed.
1 pts
Minor Errors
Strings are
not freed
properly.
0 pts
Needs
Improvement
Strings are
not freed.

Systems Programming Binary Search Assignment

10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 8/10
Criteria Ratings Pts
3 pts
6 pts
3 pts
5 pts
3 pts
The program must free the nodes after the output
is completed.
3 pts
Meets
Requirements
Nodes are freed after
they are not needed.
1 pts
Minor Errors
Nodes are
not freed
properly.
0 pts
Needs
Improvement
Nodes are not
freed.
If the -c option is used the program will sort the
data in upper case. If the -l option is used the
program will sort the data in lower case. This
must be done with your own comparison
function, not the builtin ones strcmp() or
strcasecmp() or any similar ones.
6 pts
Meets
Requirements
The -c and -l options
to compare strings
work properly with a
user written compare
function.
3 pts
Minor Errors
The -c and -l
options to
compare
strings do not
work
properly.
0 pts
Needs
Improvement
The -c and -l
options to
compare
strings do not
work at all.
If the -o option is used the output will go to a file
named as specified without changing the
filename at all otherwise it will go to stdout.
3 pts
Meets Requirements
The -o option is used
properly with the output
going to a file otherwise
it goes to stdout.
1.5 pts
Minor
Errors
The -o
option
runs with
minor
errors.
0 pts
Needs
Improvement
The -o option
does not
work.
If the input file is included it is used (without
changing the name) for input otherwise input
comes from stdin.
5 pts
Meets
Requirements
An input file is used
properly without
changing the name
or input comes from
stdin.
2.5 pts
Minor Errors
An input file is
not used
properly or
stdin is not
used properly
for input.
0 pts
Needs
Improvement
Input does
not work as
specified.
Execution of the program will end with a blank
line for input from stdin, or an EOF from an input
file.
3 pts
Meets Requirements
Execution of the
program ends with a
blank line from stdin or
an EOF from an input
file.
1.5 pts
Minor
Errors
There were
some
errors with
ending the
input.
0 pts
Needs
Improvement
Ending the
input did not
work as
specified.
10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 9/10
Criteria Ratings Pts
3 pts
3 pts
3 pts
3 pts
3 pts
3 pts
bstsort (Input from the keyboard, output to the
screen, case insensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.
bstsort -c (Input from the keyboard, output to the
screen, case sensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.
bstsort -l infile1 (Input from file called infile1,
output to screen, case insensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.
bstsort -c infile1 (Input from file called infile1,
output to screen, case sensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.
bstsort -o outfile1 (Input from the keyboard,
output to file called outfile1, case insensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.

Systems Programming Binary Search Assignment

bstsort -l -o outfile2 (Input from the keyboard,
output to file called outfile2, case sensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.
10/23/21, 11:47 AM BST Assignment 1
https://fiu.instructure.com/courses/120412/assignments/1444750?module_item_id=4554401 10/10
Total Points: 100
Criteria Ratings Pts
3 pts
3 pts
3 pts
3 pts
bstsort -l -o outfile3 infile1 (Input from file called
infile1, output to file called outfile3, case
insensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.
bstsort -c -o outfile4 infile1 (Input from file called
infile1, output to file called outfile4, case
sensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.
bstsort -o outfile5 infile2 (Input from file called
infile2, output to file called outfile5, case
insensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.
bstsort -c -o outfile6 infile2 (Input from file called
infile2, output to file called outfile6, case
sensitive)
3 pts
Meets
Requirements
Test case works
as expected.
2 pts
Minor Errors
Test case works
with minor errors.
0 pts
Needs
Improvement
Test case did
not work.

Place your order
(550 words)

Approximate price: $22

Calculate the price of your order

550 words
We'll send you the first draft for approval by September 11, 2018 at 10:52 AM
Total price:
$26
The price is based on these factors:
Academic level
Number of pages
Urgency
Basic features
  • Free title page and bibliography
  • Unlimited revisions
  • Plagiarism-free guarantee
  • Money-back guarantee
  • 24/7 support
On-demand options
  • Writer’s samples
  • Part-by-part delivery
  • Overnight delivery
  • Copies of used sources
  • Expert Proofreading
Paper format
  • 275 words per page
  • 12 pt Arial/Times New Roman
  • Double line spacing
  • Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Our guarantees

Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

Money-back guarantee

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read more

Zero-plagiarism guarantee

Each paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read more

Free-revision policy

Thanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read more

Privacy policy

Your email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read more

Fair-cooperation guarantee

By sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more

Order your essay today and save 30% with the discount code GRADE