ENGR30003: Numerical Programming for EngineersAssignment 1August 25, 2019Marks: This assignment is worth 25% of the overall assessment for this course.Due Date : Friday, 13 September 2019, 5:00pm, via submit on dimefox. You will losepenalty marks at the rate of 10% per day or part day late, and the assignment will notbe marked if it is more than 5 days late.Learning OutcomesThis project requires you to demonstrate your understanding of dynamic memory, linkedlists and basic numerical computation. The key objective of this assignment is to solve aset of tasks which involve processing of flow around a flat plate.Flow Around a Flat PlateIn the field of Fluid Mechanics, flow around a flat plate perpendicular to the flow directionis still an active area of research. With advent of high performance computing andsupercomputers, it has now become possible to look at this simple case with a greaterdeal of accuracy. The problem consists of a flat plate that is perpendicular to the mainflow direction as shown in Figure 1 (left). The blue arrows indicate the direction of theflow while the shaded object is the flat plate. This generates a wake behind the flat plateand exerts a pressure force on the plate, similar to the force you feel when you hold yourhand out in a moving car. At a given instant the flow behind the flat plate is extremelycomplex and a snapshot of the flow domain is shown in Figure 1 (right).Working with the DataFor this assignment, you will process the wake data from a flat plate case. The data hasbeen provided to you in a CSV format file (flow data.csv) with the following form:rho ,u,v,x,y0.951,1.05,0,-15,-200.951 ,1.05 ,0.00155 , -14.6 , -200.951 ,1.05 ,0.00273 , -14.2 , -200.95 ,1.05 ,0.00366 , -13.8 , -200.95 ,1.05 ,0.00434 , -13.4 , -200.95 ,1.05 ,0.00467 , -13.1 , -200.95 ,1.05 ,0.00462 , -12.7 , -20Each line corresponds to a point in the flow domain with coordinates (x,y). The densityrho and velocities at that given point in x and y are given by u and v respectively.1yxFigure 1: (left) Schematic of problem domain (right) Instantaneous flow field behind aflat plate superposed on the gridPositive value of u indicates velocity direction is along the x direction while negative uindicates velocity direction is along -x. Similarly for the v velocity sign.Processing TasksThis assignment consists of four processing tasks which will be assessed independently.For each task you are to measure the run time it takes to complete the described taskusing your program (see program output below). Each of the four tasks must notrequire more than 60 seconds to run on dimefox using valgrind. This means, inorder to complete the task within this time limit, you may need to focus on the efficiencyof your solution for each problem. Overall you have to write a single program, performingeach of the four tasks sequentially. For each task you have to write your results to a fileon the disk. Details on using valgrind is available in the “Implementation” section ofthis assignment.Task 1: Maximum Flux Difference [2/25 Marks]It is sometimes helpful to understand what’s the range of velocities in the flow. Forthe first task, you must compute the maximum flux difference, i.e., rho*u and rho*vafter coordinate x = 20. Specifically, you must output first the two points in the domainwhere the magnitude of the rho*u flux difference is maximum followed by the two pointsin the grid where the magnitude of the rho*v flux difference is maximum. For each set ofpoints, the point with the maximum of the given flux must be first followed by the pointwith the minimum flux. The output should be to the file called task1.csv and shouldbe formatted as below. There must be no blank spaces between the values and aroundthe commas. Each value must be written to 6 decimal places.It is imperative that you write it out the way described above and shownbelow otherwise comparing your output to the solution would result in anerror and you would lose marks.2rho ,u,v,x,y1.2438621 ,1.007986 , -0.001002 ,40.512346 , -19.5953871.0148121 ,0.850117 ,0.0005807 ,66.899192 , -0.7290561.1438621 ,0.852483 ,0.0004275 ,69.552467 , -0.7290561.1386456 ,0.838355 , -0.0006330 ,60.961891 ,0.442134The above is an example of what the file should look like and is not the actual solution.Also note that the data provided in flow data.csv is not in any chronological order andyou must efficiently look only at points where the value of x is greater than 20. You canuse file io.c to understand how to output data to a file.Task 2: Mean Velocities on a Coarser Grid [5/25 Marks]Each line in the file flow data.csv is a point location in the domain. These pointswhen joined together will create a mesh (also called a grid). For this task, you will mapthese points onto a coarser grid, computing the new average coordinates (x,y) and thecorresponding mean density rho and velocities (u,v). The flow domain can be thought asdivided into a two-dimensional grid such that each cell of the grid would contain multiplepoints, the number of which would depend on the cell upper and lower dimensions andthe coordinates of the points. You would compute the average coordinates, density andvelocities for each cell using the formula below for all points k within a given cell (this isfor the x coordinate; same formula to be used for y, u, v, rho):xav =Σk−1i=0 xikWhile computing the averages, you must ignore any data points that lie on the coarse cellboundaries, i.e., only consider contribution of points that are wholly contained within thegiven cell. The resulting averaged values of the given cell can be obtained from a scoreS, computed byS = 100√u2av + v2av√x2av + y2avFinally, you must output the results of the averaged values and the score to task2.csvin descending order based on the score for each cell. An example of what the outputshould look like is shown below. There must be no blank spaces between the values andaround the commas. Any float value must be written to 6 decimal places as shown:rho ,u,v,x,y,S1.191265 ,0.831445 ,0.019688 ,69.842187 ,5.861905 ,1.1866241.236148 ,0.874429 , -0.001291 ,79.552381 ,9.923571 ,1.0907341.234881 ,0.868093 , -0.003071 ,79.552381 ,5.861905 ,1.0882781.236199 ,0.861106 , -0.001160 ,79.552381 , -9.886786 ,1.0741771.236118 ,0.864510 ,0.000087 ,79.552381 ,14.017391 ,1.070231The size of the grid (number of cells in each direction) must be an input parameter,allowing the code to run different grid sizes. Your implementation would be checked forthe grid resolution of 10 i.e. 10 cells in x and 10 cells in y. The domain extent for thiscoarse grid in x and y is -15 to 85 units and -20 to 20 units respectively. An example ofthe coarse grid is shown in Figure 2 (left). The 10 cells in x direction would span from-15 to 85 units while the 10 cells in y direction would span -20 to 20 units. Also shown isan example of a cell within this grid. As can be seen, the cell is of width ∆x and height∆y and the black dots show the points in the original grid. Once you do the averagingfor all these points, you will end up with one average point (shown in red).3-1585∆x∆yFigure 2: (left) Example of coarse grid with minimum and maximum extent shown bythe coordinates (right) Example of a given cell where the black dots show the originalpoints and the star shows the location of the averaged pointTask 3: Searching in Data Structures [8/25 Marks]For this task, you will implement three data structures: an array, a linked list and aperfectly balanced binary search tree. The data contained in these data structures will bethe same, with the aim to perform a search operation and output the time taken to searchfor each case. The data required for this task is a subset of the data in flow data.csv.First, you must pull out the data points at the domain centreline, i.e. points where y =0.0. You should store these points in an array. Next, you must sort the data points inascending order of the streamwise flux rho*u. Then, you must insert the sorted valuesinto a linked list and in a perfectly balanced BST. Finally, you must search for the datapoint in all the data structures whose rho*u value is clos
est to 40% of the maximum rho*uflux. You must first find out the exact value which is closest to the 40% of maximumrho*u in the array and then search for this exact value in the remaining data structures.The following outputs are required in the file task3.csv:1. Linear search on the array to find the value. You must output all rho*u valuesupto and including the value that is being searched for.2. Binary search on the array to find the value. You must output all rho*u valuesupto and including the value that is being searched for.3. Linear search on the Linked List to find the value. You must output all rho*uvalues upto and including the value that is being searched for.4. Search on the balanced BST for the value. You must output all rho*u values uptoand including the value that is being searched for.A sample output for the task3.csv file is shown below, where each line (total of 4 lines)corresponds to the cases in the order shown above:3.614885 ,3.564577 ,3.562721 ,3.544763 ,3.542255 ,3.489632 ,3.48872943.614885 ,3.564577 ,3.544763 ,3.542255 ,3.4887293.614885 ,3.564577 ,3.562721 ,3.544763 ,3.542255 ,3.489632 ,3.4887293.614885 ,3.564577 ,3.544763 ,3.542255 ,3.488729The values above do not correspond to any data values but are provided only as a ref-erence. The search time for all four cases must be written to standard output, in theformat described in the Program output section. Here, perfectly balanced refers to nearlyperfectly balanced i.e. there may be uneven leaf nodes but the length of these nodes mustnot be greater than other nodes by more than 1 depth. The search algorithm in all casesmust terminate when the exact value is identified and the last value written out must bethis value.Task 4: Computing the vorticity [5/25 Marks]One of the quantities of interest for engineers to study is vorticity, which represents therotation of the velocities about an axis. The vorticity for the given data can be definedas follows:ω =(∂v∂x− ∂u∂y)(1)To compute the vorticity, there are several steps you have to follow. Since each line ofthe total n ∗m lines of the data in flow data.csv represents a point in the domain, youwould first have to arrange these datapoints into a grid representation such that accessingany point in the domain is done through two indices, similar to a 2D array representation.It is important that the arrangement of the datapoints is consistent with the domain.So, if as an example, the u datapoints were put into a 2D array U of shape n×m, then,increasing i in U[i][j] for a given j represents increasing x values and increasing j inU[i][j] for a given i represents increasing y values. Once, this is done, you can thencompute the vorticity using the following formula:ω[i][j] =(V [i+ 1][j]− V [i][j]X[i+ 1][j]−X[i][j] −U [i][j + 1]− U [i][j]Y [i][j + 1]− Y [i][j])(2)Here, ω, U, V, X and Y are defined as 2D arrays containing values of ω, u, v, x and y inthe 2D domain. The indices in the above formula for i go from 0 : n − 2 and for j gofrom 0 : m− 2. For datapoints with indices n− 1 or m− 1, the value of vorticity will begiven by:ω[n− 1][j] =(V [n− 1][j]− V [n− 2][j]X[n− 1][j]−X[n− 2][j] −U [n− 1][j + 1]− U [n− 1][j]Y [n− 1][j + 1]− Y [n− 1][j])ω[i][m− 1] =(V [i+ 1][m− 1]− V [i][m− 1]X[i+ 1][m− 1]−X[i][m− 1] −U [i][m− 1]− U [i][m− 2]Y [i][m− 1]− Y [i][m− 2])ω[n− 1][m− 1] =(V [n− 1][m− 1]− V [n− 2][m− 1]X[n− 1][m− 1]−X[n− 2][m− 1] −U [n− 1][m− 1]− U [n− 1][m− 2]Y [n− 1][m− 1]− Y [n− 1][m− 2])Once you’ve obtained the values of ω, you must report the number of datapoints thathave the absolute ω values within a certain threshold. Thus, you must report the numberof datapoints in the following format to the file task4.csv:5threshold ,points5 ,1000010 ,2000015 ,5000020 ,500025 ,2500The number of points shown are only for reference and do not refer to the solution. Thethresholds here mean 10,000 points have absolute ω between 0 and 5, 20,000 points haveω between 5 and 10 and so on. You may assume the data in flow data.csv is sorted inascending order in y followed by ascending order in x.Implementation [5/25]The implementation of your solution is extremely important and your implementationshould be based on the provided skeleton code. A total of [3/25] marks are allocated tothe quality of your code:• Program compiles without warning using gcc -Wall -std=c99 on dimefox• Exception handling (check return values of functions such as malloc or fscanf )• No magic numbers i.e. hard coded numbers in your code (use #define instead)• Comments and authorship for each file you submit are important (top of the file)• General code quality (use code formatters, check for memory leaks)• No global variablesThere is a coding etiquette we are enforcing for this assignment, which is concerned withthe comments in the code. Every code snippet must be provided with sufficient comments,i.e., what does the following block of code do. This is imperative in case your output isincorrect; as it makes it easier for the grader to assess if your implementation was correct.The quality of comments are allocated a total of [2/25] marks. The following sectionsdescribe the required command line options and program output of your program.Command-Line OptionsWhen running on dimefox your program should support the following command-lineoptions:terminal: gcc -Wall -std=c99 *.c -o flow -lmfor the compilation andterminal: valgrind ./flow flow data.csv 10for the execution, where flow data.csv is containing the flow related data and 10 is thegrid resolution.6Program OutputWhen running on dimefox the program should only output the following information tostdout in addition to the csv files for each task:terminal: valgrind ./flow flow data.csv 10TASK 1: 200.63 millisecondsTASK 2: 14063.82 millisecondsTASK 3 Array Linear Search: 30.4 microsecondsTASK 3 Array Binary Search: 40.5 microsecondsTASK 3 List Linear Search: 100.21 microsecondsTASK 3 BST Search: 50.1 microsecondsTASK 3: 209.46 millisecondsTASK 4: 221.16 millisecondsNote the units of time in the output for the tasks. For each task, output the time, inrelevant units, taken to perform all computation associated with each task. This can beachieved by adopting the gettimeofday.c code available in the resource for Week 2. Af-ter the program is executed, the files task1.csv , task2.csv, task3.csv and task4.csvcontaining the results for the different tasks should be located in the current directory.A total of [1/15] marks is allocated for correct implementation of the out-put format in terms of console output and output written to the result filegenerated by each task.Provided CodeThe following files are provided to you for this assignment:• main.c, where the parsing of data from command line is to be done and timing foreach task implemented.• tasks.c, where you would implement four functions maxfluxdiff(), coarsegrid(),searching() and vortcalc(), for each task.• tasks.h, which need not be changed and acts as a header file to link the C file tothe main file.You are free to use guide programs provided during the lectures on the LMS and adaptthem for your use. This could be any of the files like file io.c, linkedlist.c, bst.cand more. You may also use the header files if needed. Remember to fill in your detailsin each file you write, such as the student name and student number.Points to consider• Only use type int and double for integers and floating point numbers respectively.When writing out a float to output make sure the format restricted to a 6 decimalplace number. Writing to file needs to be done according to the format given in theassignment to be marked correct by the system. If there are multiple numbers ona line separated by a comma, leave no space in between.7• Each task is independent of the other so you can work on each task individuallyand test it out. Make sure you adhere to the formatting and output file headers asshown in the Assignment.• Read the data into an appropriate data structure for each task. You may choose toread it in once and reuse this structure
for all tasks but the task functions mightneed to be modified.• Write the header for each file as described in the assignment. Your solution wouldbe marked wrong by the system even if you have the right solution if you get yourheaders wrong.• Your code should not contain any magic numbers. Examples include but are notlimited to using malloc(1000 * sizeof(int)) or for (i = 0 ; i < 20; i++).Use #define at the top of the file to define 1000 and 20.• Remember to free your data structure and any other structure you allocate dynam-ically. Statically allocated structures are not allowed.SubmissionYou need to submit your program for assessment. Submissions will not be done via theLMS; instead you will need to log in to the server dimefox and submit your files usingthe command submit . You can (and should) use submit both early and often toget used to the way it works, and also to check that your program compiles correctly onour test system, which has some different characteristics to the lab machines. Only thelast submission will be marked. The submission server may be very slow towards thedeadline as many students are submitting. Therefore, please do not wait until the lastfew minutes to make the first attempt of submission. If you make a submission attempta few minutes before the deadline but the submission was completed after the deadline,your submission will be treated as a submission AFTER the deadline.All submissions must be made through the submit program. Assignments submittedthrough any other method will not be marked. Transfer your code files to the home driveon dimefox. Check the transfer was successful by logging into dimefox and using the lscommand on the terminal. Perform the following set of commands on the terminal fromyour home location on dimefox (making the right folders and transfering the files in theright location):mkdir ENGR30003cd ENGR30003mkdir A1cd A1cp ../../*.c .cp ../../*.h .cp ../../flow data.csv .Here you’re making the A1 folder within the ENGR30003 folder and then moving to the A1folder. From this folder, you move the files transferred from the home to the A1 folder.Remember to check the A1 folder contains only the .c or .h files (if you use multiple c8files and h files) you need for the assignment and the CSV data file. Then try compilingyour code and executing it to see if it works without errors. Once you’re satisfied withyour files, you can submit the files (only the c and h files, not the csv) via the submitsystem on dimefox as follows:submit ENGR30003 A1 *.c *.hWait for a few minutes and then carry out the verify and check steps:verify ENGR30003 A1 > feedback.txtnano feedback.txtLook through this feedback text file to check (a) your program compiled (b) it exe-cuted without error. Please read man -s1 submit on dimefox for confirmation abouthow to use submit, especially how to verify your submission. No special considerationwill be given to any student who has not used submit properly.You must also check that you have no memory leaks in your code as loss of memoryfrom your implementation will result in deductions. Your submissions will be assessedvia valgrind on submit. To use valgrind to check your implementation, you mustexecute the compiled file using:valgrind ./flow flow data.csv 10Since valgrind is a memory error detector, it will be used to assess your submissions forpotential memory misuse. A well-implemented code will have the following output:==3887== HEAP SUMMARY:==3887== in use at exit: 0 bytes in 0 blocks==3887== total heap usage: 53 allocs, 53 frees, 56,921,168 bytes allocated==3887== All heap blocks were freed — no leaks are possibleIt must be pointed out we are not using a small data file so valgrind will take longertime to run compared with the normal execution. Plan your submission accordingly.Incase your submission fails to pass the memory check, you will lose marks. There aretwo potential areas where you can lose marks: runtime error messages and heap/leaksummary. Examples of runtime error messages include:1. Use of uninitialised value of size X: Happens when you use a variable thathas not been defined or does not exist anymore or initialised.2. Conditional jump or move depends on uninitialised value(s): Happens whenusing an uninitialised variable to perform operations3. Invalid read/write of size X: Happens when trying to scan or write to file avariable to memory which you do not have access to.4. Process terminating with default action on signal 11: Happens when theerror is so severe, your code is terminated automatically.9Examples of heap/leak summary errors are:1. total heap usage: 2,686 allocs, 29 frees, 152,138,664 bytes allocated2. ==6504== LEAK SUMMARY:==6504== definitely lost: 0 bytes in 0 blocks==6504== indirectly lost: 0 bytes in 0 blocks==6504== possibly lost: 0 bytes in 0 blocks==6504== still reachable: 16,912,796 bytes in 2,657 blocks==6504== suppressed: 0 bytes in 0 blocksYou may discuss your work during your workshop, and with others in the class, butwhat gets typed into your program must be individual work, not copied from anyoneelse. So, do not give hard copy or soft copy of your work to anyone; do not “lend”your “Uni backup” memory stick to others for any reason at all; and do not ask othersto give you their programs “just so that I can take a look and get some ideas, I won’tcopy, honest”. The best way to help your friends in this regard is to say a very firm“no” when they ask for a copy of, or to see, your program, pointing out that your“no”, and their acceptance of that decision, is the only thing that will preserve yourfriendship. A sophisticated program that undertakes deep structural analysis of C codeidentifying regions of similarity will be run over all submissions in “compare every pair”mode. Students whose programs are so identified will be referred to the Student Center.See https://academichonesty.unimelb.edu.au for more information.Getting HelpThere are several ways for you to seek help with this assignment. First, go throughthe Assignment 1 Important Notes in the LMS. It is likely that your questionhas been answered there already. Second, you may also discuss the assignment onthe Assignment 1 Questions discussion board. However, please do not post anysource code on the discussion board. Finally, you may also ask questions to yourtutors during the workshops and if it is still unresolved, contact either the lecturerThomas Christy ([email protected]) or the head tutor Chitrarth Lav([email protected]) directly.10
