Most modern operating systems (UNIXTM  based OS, Windows, etc.) were written in C/C++ and assembly languages. For the purpose of learning in this class, you are required to do all           programming assignments in C or C++ language.

Based on the official CS 480 class notes “Instructors will evaluate students C/C++ proficiency     level in the first week of the semester and make appropriate recommendations to students for the course.”, this first assignment is designed for you to demonstrate necessary skills and

proficiency in C/C++ programming to continue for this class. You are strongly advised to drop from the class if your code does NOT score 100% for the auto-grading part, as all future

assignments will demand more advanced C/C++ programming skills than this first one.

You must do this assignment on your own. A single programmer affidavit of academic honesty (refer to Canvas) will need to be submitted along with your code.

Start on this assignment and ask questions early. If you wait until due date to ask questions, do NOT expect they will be answered by TAs or instructor.

This assignment is applicable to the currently enrolled students as well as the waitlisted students. We need to give all waitlisted students a fair chance to enroll.

Note for waitlisted students who choose to do this assignment and pass the auto-grading, you will be added to the class only if spots are opened after some enrolled students drop. Please    also note it is a mandate from the university and the CS department to keep class size to be     within a manageable size to make sure we can support all students.

NO Late Submission

As this assignment is used for evaluating your enrollment eligibility, for the fairness and           uniformity of grading, NO LATE submission will be accepted for this assignment. There will be NO extension to this submission. All students (currently enrolled and waitlisted) must submit this assignment by due time.

Task

Tree, a hierarchical data structure, is often used in representing OS entities (such as the              organization of a file system, Unix-style process trees, etc.), and in implementing various OS      algorithms (such as multi-level paging table for memory management, multi-level indexed files, etc.).

In this assignment, you will use C or C++ to implement a tree for storing a vocabulary, and write test code for searching and counting words in the vocabulary tree:

1)   You MUST implement the pointer tree data structure (see dictionaryTreeSpec.pdf).

2)   Tree operations:

a.    Insert a word to the tree.

b.    Count all words in the tree that start with a specific prefix.

3)   Test code (see program execution and required output below):

a.    Read words from a dictionary text file and insert them to a dictionary tree.

b.    Read words from another text file, and for each word read in: search, count, and print the number of words in the dictionary tree that start with it.

Implementation Requirements:

•   This first assignment is intended to test your proficiency in using C/C++, particularly the pointers, you MUST follow the implementation requirements specified in the                  dictionaryTreeSpec.pdf. Violating any one of them will result in a ZERO score on the      autograding part.

Compilation and Execution:

1)   You must create and submit a Makefile for compiling your source code. Makefiles are  program compilation specifications. See below (also refer to the Programming page in Canvas) for details on how to create a makefile. A makefile example is also provided to you.

2)   The make file must create the executable with a name as countprefix.

3)   The executable requires two command line arguments :

a.    The first argument specifies the file path to the source vocabulary text file that provides the words for building the dictionary tree .

i.   Use vocabulary.txt file as the source vocabulary text file for testing.

b.   The second argument specifies the file path to the text file that provides the words to be searched in the dictionary tree.

i.   Two files testfile1.txt and testfile2.txt are given for your testing.

ii.   Auto-grading on gradescope will use all or part of testfile1.txt and

testfile2.txt.

•   Test case 1 uses testfile1.txt, test1CorrectOutput.txt has the correct output for execution using testfile1.txt (see below)

•   Test cases 2, 3 and 4 use different portions of testfile2.txt

c.    Your program should have minimal error checking on whether the command line arguments are provided from execution, fail gracefully when there is a      wrong number of arguments, or a file does not exist.

4)   Program execution and required output:

a.    Using the following command line as an example:

i.    ./countprefix vocabulary.txt testfile1.txt

b.   Your program would first read the words from the vocabulary.txt and insert them to a dictionary tree.

c.    It would then read the words from testfile1.txt, in the order of how they appear in the file, and for every word read in from testfile1.txt:

i.   search and count the number of words in the dictionary tree that start with this word,

ii.   and print this word and the count from i. above (separated by a space) to the standard output ONE line per word, in the exact format as:

hour 10

‘hour 10’ here means for the ‘hour’ read from testfile1.txt, there are 10 words in the dictionary tree that start with ‘hour’ .

iii.   More examples:

•    If the dictionary tree has bat, batch, batman words inserted;   there should be three words starting from ‘bat’, your program

shall

print:

bat 3

•    If the dictionary tree has education, educate, edition words  inserted; there should be three words starting from ‘ed’, but there should be 0 words starting from ‘editor’, your program

shall

print:

ed 3

editor 0

iv.   Note the same word can appear multiple times from the test file. For   example, the word ‘hour’ appears many times in testfile1.txt, your       program would need to do the i. and ii. above every time it reads in an ‘hour’ word.

d.   See test1CorrectOutput.txt for the correct output from this execution. Using the same command line arguments, your program should print the output to the standard output exactly as what is contained in test1CorrectOutput.txt.

e.  REMEMBER: Do NOT print the output to a file, print to the standard output; otherwise, autograding will fail.

Programming and testing:

•    Please refer to C/C++ programming in Linux / Unix page.

•    You may use C++ 11 standard for this assignment, see appendix below and the sample Makefile.

•    We strongly recommend you set up your local development environment under a Linux environment (e.g., Ubuntu 18.04 or 20.04, or CentOS 8), develop and test your code       there first, then port your code to Edoras (e.g., filezilla or winscp) to compile and test to verify. The gradescope autograder will use a similar environment as Edoras to compile   and autograde your code.

Turning In to Gradescope

Make sure that all files mentioned below (Source code files and Makefile) contain your name and Red ID! Do NOT compress / zip files into a ZIP file and submit, submit all files separately.

•    Source code files (.h, .hpp, .cpp, .c, .C or .cc files, etc.)

•    Makefile

•    A sample output (in a text file) from a test of your program. (use > to export standard output to a file, e.g., ./countprefix vocabulary.txt testfile1.txt > testoutput.txt)

•    Single Programmer Affidavit with your name and RED ID as signature, use Single Programmer Affidavit.docx from Canvas Module Assignments.

•    Number of submissions:

a.    Please note the autograder counts the number of your submissions. For this      assignment, you will be allowed 99 submissions, but future assignments will be limited to around 10 submissions. As stressed in the class, you are supposed to do the testing in your own dev environment instead of using the autograder for testing your code. It is also the responsibility of you as the programmer to sort  out the test cases based on the requirement specifications instead of relying on the autograder to give the test cases.

If you are a waitlisted student, please email TAs for gradescope entry code, then enroll yourself to the gradescope course for submission.

Grading

Passing 100% autograding may NOT give you a perfect score on the assignment. The structure, coding style, and commenting will also be part of the rubrics for the final grade (see Syllabus   Course Design - assignments). Your code shall follow industry best practices:

•    Be sure to comment your code appropriately. Code with no or minimal comments are automatically lowered one grade category.

•    Design and implement clean interfaces between modules.

•    NO global variables.

•    NO hard code – Magic numbers, etc.

•    Have proper code structure between .h and .c / .cpp files, do not #include .cpp files.

Test data including one correct program output are given to you, any hardcoding to generate  the correct output without implementing the dictionary tree will automatically result in a zero grade of the assignment.

Academic honesty

Posting this assignment to any online learning platform and asking for help is considered academic dishonesty and will be reported.

An automated program structure comparison algorithm will be used to detect code plagiarism.

•   The plagiarism detection generates similarity reports of your code with your peers as well as from online sources. It would be purely based on similarity check, two              submissions being similar to each other could be due to both copied from the same   source, whichever that source is, even the two students did NOT copy each other.

•    We will also include solutions from the popular learning platforms (such as Chegg,  github, etc.) as well as code from ChatGPT (see below) as part of the online sources used for the plagiarism similarity detection. Note not only the plagiarism detection checks for matching content, but also it checks the structure of your code.

•    If plagiarism is found in your code, you will be automatically disenrolled from the class. You will also be reported for plagiarism.

•    Note the provided source code snippets for illustrating proposed implementation would be ignored in the plagiarism check.

Recently, the Center for Teaching & Learning and Instructional Technology Services also shared information concerning the rapidly evolving impact of artificial intelligence (AI) within academia — specifically, ChatGPT, the chatbot released at the end of last year.

SDSU’s Center for Student Rights and Responsibilities have officially added plagiarism policies of using ChatGPT for academic work, as put below:

•    “Use of ChatGPT or similar entities [to represent human-authored work] is considered academic dishonesty and is a violation of the Student Code of Conduct. Students who utilize this technology will be referred to the Center for Student Rights and                    Responsibilities and will face student conduct consequences up to, and including,         suspension.”

Appendix

Makefile

a.    A Makefile is for compiling and linking C/C++ code to generate an executable file.   The sample Makefile provided is for compiling and linking C++. Suppose you have   dictionary.h and dictionary.cpp for dictionary tree implementation, and                    countprefix.cpp having the main function that drives the dictionary population and

word •

•

counting.

CXX is the variable specifying the C++ compiler as g++ (note autograder uses g++ compiler version 7, Edoras has g++ 4.8.x installed)

CXXFLAGS (-std=c++11 -Wall -g3 -c) specifies compilation flags to the             compiler specified by CXX, instructs the compiler to use the ISO 9899             standard C++ implementation published in 2011 (commonly called c++11,    c11 for C), c++11 and c11 have functionality that is desirable (e.g., the bool  type in C and the type safe nullptr in C++). -g3 adds debugging information   to the executables. Debugging information lets the use of the GNU symbolic