ENGG1340 / COMP2113, Assignment 2 Solved

ENGG1340 / COMP2113, Assignment 2


If you have any questions, please post to the Moodle discussion forum on Assignment 2.

 General Instructions

Problem 1: (C++) Inner Matrix Rotation (15 marks)

Problem 2: (C++) Isolated Bounding Boxes (20 marks)

Problem 3: (C++) Word Search (20 marks)

Problem 4: (C) Character Counter (20 marks)

Program 5: (Makefile, C++) Number System Conversion (20 marks)

Total marks: 100 marks

 

General Instructions
Read the instructions in this document carefully.

In this assignment you will solve 5 tasks and a tester would automatically test your submitted program. So if your submitted files and program outputs do not conform to our instructions given here, your programs cannot be evaluated and you will risk losing marks totally.

Sample test cases are provided with each task in this document. Note that the test cases may or may not cover all boundary cases for the problem. It is also part of the assessment whether you are able to design proper test cases to verify the correctness of your program. We will also use additional test cases when marking your assignment submission.

Input and output format
Note carefully whether your C/C++ programs should read from the standard input, command line input or file input. Also, unless specified otherwise, your answer should be printed through the standard output. If you failed to follow the instructions, the tester may not able to give a score for your program. Additionally, you should strictly follow the sample output format (including space, line breaker, etc.), otherwise, your answer might be considered as wrong.

How to use the sample test cases
Sample test cases in text file formats are made available for you to check against your work. Here's how you may use the sample test cases. Take Problem 2 test case 3 as an example. The sample input and the expected output are given in the files

  input2_3.txt  and  output2_3.txt , respectively. Suppose that your program is named "2", do the followings at the command prompt of the terminal to check if there is any difference between your output and the expected output.

./2 < input2_3.txt myoutput.txt diff myoutput.txt output2_3.txt 

Testing against the sample test cases is important to avoid making formatting mistakes. The additional test cases for grading your work will be of the same formats as given by the sample test cases.

Coding environment
You must make sure that your program can compile, execute and generate the required outputs on our standard environment, namely, the gcc C/C++11 environment we have on the CS Linux servers (academy*). As a programmer/developer, you should always ensure that your code can work perfectly as expected on a target (e.g., your client's) environment, not only on yours.

While you may develop your work on your own environment, you should always try your program (compile & execute & check results) on our standard environment before submission.

For Problems 1,2,3 and 5 on C++ programming, make sure the following compilation command is used to compile your programs:

 

For Problem 4 on C programming, make sure the following compilation command is used to compile your program:

 

Submission
  Name your C/C++ programs as the following table shows and put them together into one directory. Make sure that the folder contains only these source files ( *.cpp / *.c / *.h / Makefile ) and no other files. Compress this directory as a  [uid].zip file where [uid] is your university number and check carefully that the correct file have been submitted. We suggest you to download your submitted file from Moodle, extract them, and check for correctness. Resubmission after the deadline is not allowed.

A maximum of 5 marks will be deducted if you fail to follow the submission instructions strictly.

Note that code templates for Problems 1 to 5 are provided, and you should base your work on them.

Problem
Code files provided
Files to Submit
1
  1.cpp 
  1.cpp 
2
  2.cpp 
  2.cpp 
3
  3.cpp 
  3.cpp 
4
  4.c 
  4.c 
5
  d2boh.h , d2boh.cpp 
  d2boh.cpp , main.cpp , Makefile 
Late submission

If submit within 3 days after the deadline, 50% deduction. After that, no mark.

Evaluation
Your code will be auto-graded for technical correctness. In principle, we use test cases to benchmark your solution, and you may get zero marks for not being able to pass any of the test cases. Normally partial credits will not be given for incomplete solution, as in many cases the logic of the programs are not complete and an objective assessment could be difficult. However, your work may still be considered on a case-by-case basis during the rebuttal stage.

Academic dishonesty
We will be checking your code against other submissions in the class and from the Internet for logical redundancy. Please be reminded that no matter whether it is providing your work to others, assisting others to copy, or copying others will all be considered as committing plagiarism and we will follow the departmental policy to handle such cases. Please refer to the course information notes for details.

Discussion forum
You are not alone! If you find yourself stuck on something, post your question to the course forum. We want this assignment to be rewarding and instructional, not frustrating and demoralizing. But we don’t know when or how to help unless you ask.

Please be careful not to post spoilers. Please don’t post any code that is directly related to the assignments. However you are welcome and encouraged to discuss general ideas on the discussion forums. If you have any questions about this assignment you should post them in the discussion forums.

 

Problem 1: (C++) Inner Matrix Rotation
  The completed program will read the dimension  dim  and the elements of a  dim  x  dim  matrix, and then display the elements of its inner  dim-2  x  dim-2  matrix rotated clockwise through 90 degrees.

You should start working from the  1.cpp  provided. The  main()  function has been completed for you and your task is to write definitions of functions  read_matrix()  and  display_inner_cw_rotated()  to satisfy the following specifications:

    read_matrix() : reads  dim , an integer supplied by the user, into the variable passed as the second argument, where  dim  is guaranteed to be in {3, 4, ...,10}. It then reads values of elements of a  dim  x  dim  square matrix of integers, each separated by whitespace. The values are supplied by the user row by row and are read into the 2D array passed as the first argument. The size of the array is  MAXDIM  x  MAXDIM , where  MAXDIM  is a global constant and thus is available for use in your function definitions.  MAXDIM  is initialized with a value of 10 and, therefore, the array is large enough to hold the maximum number of values that the user will supply.

   display_inner_cw_rotated() : takes as a first argument a 2D array containing a square matrix and, as a second, the dimension,  dim , of that matrix. It displays the values of a  dim-2  x  dim-2  matrix formed by deleting the outermost rows and columns of the original matrix (that is, those that form its outer perimeter) and then rotating that reduced matrix clockwise through ninety degrees. The elements of the resulting matrix are displayed row by row with a trailing space after each element (check carefully your outputs against the given sample outputs using  diff ).

Sample Test Cases
User inputs are shown in blue.

1_1:

 

1_2:

 

1_3:

 

 

Problem 2: (C++) Isolated Bounding Boxes
This problem builds on top of Problem 5 of Assignment 1 (A1P5). Your C++ program will accept the same input as in A1P5, but this time your program should compute the axis-aligned boungind boxes (AABBs) for each of the input 2D geometries, and also identify the isolated AABBs which do not overlap with any other AABBs. (Note: Two AABBs are said to overlap if they share a common point in the 2D plane).

 You are provided with a template program  2.cpp .

Input: Each line of the user input begins with a character indicating the type of geometry, followed by some parameters of the geometric object. The input line can be one of the followings:

 R  x y width height 
where  R  represents an input rectangle, x, y are floating-point numbers for the x-, y-coordinates of the rectangle center, width and height are floating-point numbers for the rectangle size along the x- and y-axes, respectively.

 C  x y radius 
where  C  represents an input circle, x, y are floating-point numbers for the x-, y-coordinates of the circle center, and radius is a floating-point number for the radius of the center

 P  n x1  y1  x2  y2  … xn  yn  
 where  P  represents an input point set, n is an integer indicating the number of points in the set, and xi , yi , i = 1,…,n are floating point numbers for the x-, y-coordinates of the n points

 #  indicates end of input

Output:

A line

    AABB **: xmin xmax ymin ymax  for EACH of the input geometries (in the same order of the input), where  **  is a 2-digit ID (left padded with zeros) indicating which geometry this AABB corresponds to. The ID is given by the input order of the geometry, it should be  00 for the first input geometry,  01  for the second, and so on.

   then a line  Isolated AABBs:  followed by the ID of the isolated AABBs on each subsequent line, in increasing order of the IDs.

Example:

     Take sample test case  2_4  as an example. There are four input geometries, a circle (r = 0.5), a rectangle, a circle (r = 1.6), a point set, and they will have IDs  00 ,  01 ,  02 ,  03 , respectively. The first four lines of output give the AABBs (x, y, width, height) of the four geometries, and the last two lines of the output tell that each of the AABBs  00  and  03  do not overlap with the AABBs of any other geometries.

 Task 1: Complete the member functions  ReadRectangle()  and  ReadCircle()  of  struct AABB . These function are called by  main()  to read the input geometries and compute the AABBs. You may take the completed member function

 ReadPointSet()  as reference.

  Task 2: The  main()  function has already read in the geometries and stored the AABBs of the geometries in an array  boxes . Write your code to display the information of the AABBs for all input geometries by running through  boxes .

 Task 3: Complete the function  IsOverlap()  which determines whether two AABBs overlap with each other.

Task 4: In  main() , write your code to identify the isolated AABBs and display their IDs in the output formats specified above.

Note:

 You may assume that the maximum number of input geometries is 20.

  Use the  setw()  and  setfill()  functions provided by the header  <iomanip  to achieve zero padding.

(http://www.cplusplus.com/reference/iomanip/setfill/)

You may add your own functions wherever appropriate for better program modularity.

Sample Test Cases
User inputs are shown in blue.

2_1

 

2_2

 

2_3

 

2_4

 

 

Problem 3: (C++) Word Search
Write a C++ program that searches a word from multiple files, and output the number of lines that the word appears and the total number of occurrences of the word in each file.

 You are provided with a template program  3.cpp .

Input:

The program accepts command line argument as input. The command line of the program is given by:

 <program_name <word_to_search <file1 <file2 <file3  

E.g., if your program is named  wordsearch , then the following command at the command prompt

    ./wordsearch abc t1.txt t2.txt t3.txt  will ask your program  ./wordsearch  to search for the string  abc  in the files  t1.txt ,  t2.txt ,  t3.txt . Command line arguments in C/C++ are implemented by having input paramters for the  main()  function:

 int main(int argc, char* argv[])  

 Read the comments in the provided template to see the usage of the paramaters  argc  (an integer) and  argv  (an array of C-strings).

 The  main()  body has been completed for you, which means that command line argument parsing has been done for you. But you should read the code and understand how it works, as you may need to deal with command line arguments in your later courses too.

Output:

  A line for each file specified in the command line arguments: first the filename, then the number of lines the word appears in the file ( n1 ), followed by the number of total occurrences of the word in the file ( n2 ):

 <filename: <n1 <n2  

or if there is any error accessing the file:

 <filename: error opening file Requirements:

You should start working from the  3.cpp  provided.

Complete the function

    int SearchWord(string word, string fileName, int &nLines, int &total)  which search for a  word  in a file named  fileName , and stores the number of lines that  word  appears in the file in  nLines  and the number of total occurrences in  total . The function returns  0  if file operation is successful and  1  if otherwise.

The matching of word is case-insensitive.

Note:

 The  main()  function has been completed for you, and you do not need to make any change to it. Read the code in  main()  and understand what it does before you start working.

You may add your own functions wherever appropriate for better program modularity.

Sample Test Cases
Sample text files  t1.txt ,  t2.txt ,  t3.txt ,  t4.txt  are provided.

 We show only the contents of  t1.txt ,  t2.txt ,  t3.txt  here:

t1.txt
t2.txt
t3.txt
 Cab AbB CAB Ab CaB ABc aBb AB cAb caB aBcAB CAB ABcAb AbcAb aBCAB AB ABcAb aBCaB ABCAB Abb aBC abC AbC ABCAB abCab ABC aBCAB ABcAB AB cAb
 ab abcab Ab abc aBCAB AbCAb abC AbC ab abcab aBc aBc ab abcAB 

Abc aBC ab abC ab aB AbCAB AbcaB 

Ab ab ABc aBcab abC ABc AbCab ABcAb
 app THe Elf DeEd keep SHe DEED dEEd aPP Ab sheeP Cde THe sHe ElF CDE sHe KeEP aB eLF An CaT sHE hE KEeP he SHE dEED ab she
 Commands entered by the users at the command line prompt "" to run your program are shown in blue, assuming that your program name is  wordsearch .

Note that since there is no user input from the standard input, here's how you should test your output against the sample output (e.g., for test case 3_1) to check for correctness:

 

3_1

 

3_2

 

3_3

 

 

Problem 4: (C) Character Counter
Write a C program to count the number of occurrences of each character in an input string.

Input: A string (that does not contain any space characters).

  You may assume that the string is of at most 50 characters.

Output: The number of occurrences for each character.

 Uppercase and lowercase of a character would be considered as the same.

The output order of the characters should be in the same order of their occurrences in the original string. (See sample cases.)

Output characters should be in lowercase.

Requirements.

 Use the command  gcc -pedantic-errors -std=c11 4.c -o 4  to compile your program. (Or specify  -pedantic-errors -std=c11  as the compiler flags in the ATOM editor.)

Sample Test Cases
User inputs are shown in blue.

4_1

 

4_2

 

4_3

 

 

Problem 5: (Makefile, C++) Number System Conversion
In this question, let us implement a simple converter to convert a given integer in the range [1, 100] to its binary, octal and hexadecimal representation.

To allow other programs to reuse our program code for decimal-to-binary, decimal-to-octal and decimal-to-hexadecimal conversions, let us put the code in a separate file.

Let us first define the header file “d2boh.h” as follows:

 

The interfaces of the functions are explained below:

  decimal_to_binary :

Parameter 1: An input integer (1 – 100) in decimal form

Parameter 2: An integer array to hold the binary representation of the input integer. For example, if the input integer is 10, the array will contain {1, 0, 1, 0}.

Return value: An integer to represent the number of digits in parameter 2. Using the above example, the return value will be 4.

  decimal_to_octal :

Parameter 1: An input integer (1 – 100) in decimal form

Parameter 2: An integer array to hold the octal representation of the input integer. For example, if the input integer is 10, the array will contain {1, 2}.

Return value: An integer to represent the number of digits in parameter 2. Using the above example, the return value will be 2.

  decimal_to_hexadecimal :

Parameter 1: An input integer (1 – 100) in decimal form

Parameter 2: An integer array to hold the hexadecimal representation of the input integer. For example, if the input integer is 10, the array will contain {A} (one single element).

Return value: An integer to represent the number of digits in parameter 2. Using the above example, the return value will be 1.

The skeleton of the implementation file “d2boh.cpp” is given below:

 

Requirements

 

 “d2boh.cpp” in your main program.

  d2boh.o : which depends on  d2boh.cpp  and  d2boh.h  

 main.o : which depends on  main.cpp  and  d2boh.h  

 main : which depends on  d2boh.o  and  main.o  

 You should assume that there can be a file named “clean” in the folder and you need to make sure that running  make clean will not cause any conflict.

  Upon  Makefile  is created appropriately, you should be able to compile all programs by issuing the command  make main and cleaning all object files by issuing the command  make clean .