1. Homepage
  2. Programming
  3. COMP10002 Foundations of Algorithms - Assignment 2: Dynamic memory and Cellular Automaton

COMP10002 Foundations of Algorithms - Assignment 2: Dynamic memory and Cellular Automaton

Engage in a Conversation
UnimelbCOMP10002Foundations of AlgorithmsCDynamic memoryCellular Automaton

Learning Outcomes CourseNana.COM

In this project, you will demonstrate your understanding of dynamic memory and linked data structures (Chapter 10) and extend your program design, testing, and debugging skills. You will learn about cellular automata, implement a tool for performing cellular automata computations, and use this tool to solve a practical problem. CourseNana.COM

Background CourseNana.COM

A cellular automaton is a model of computation composed of cells, each in one of a finite number of states. For each cell, a set of cells called its neighborhood is defined. At the beginning of computation (time t=0), each cell is assigned a state. The states of all its cells determine the state of the automaton. The automaton progresses from its current state at time t to the next state at time t+1 by updating the states of its cells using an update rule. This rule defines a relation between the neighborhood of a cell at time t and the state of the cell at time t+1. The rule is typically deterministic and is applied for each cell in the current state simultaneously. CourseNana.COM

In an elementary cellular automaton, cells are arranged in a one-dimensional array and each cell is in 0 or 1 state denoting on and off cells, respectively. An automaton of 31 cells, with cells at positions 0, 1, 12, 15, 18, and 29 on (counting from left to right starting from zero) and the other cells off, is shown below. CourseNana.COM

                           1100000000001001001000000000010

The neighborhood of a cell in an elementary cellular automaton comprises the cell itself and its two imme- diate neighbor cells. The update rule of an elementary automaton maps such possible neighborhoods of a cell to its states in the next time step. One such update rule is depicted below. CourseNana.COM

000 001 010 011 100 101 110 111 01111000 CourseNana.COM

The top row lists all eight possible neighborhoods of a cell, with the cell in the middle being the cell of interest and the other two cells being its neighbors. For example, the 010 neighborhood denotes that the cell is on and both its immediate neighbors are off, whereas 110 is the neighborhood of an on cell with its left neighbor on and right neighbor off. The bottom row shows the state of the cell in the next time step for the corresponding neighborhoods. For instance, a cell with neighborhood 010 stays on (1) in the next step, while a cell with neighborhood 110 switches off (0) in the next step. A run of the first three computation steps of the example automaton using the example update rule is listed below; numbers at the start of each line denote time steps. CourseNana.COM

                         0:  1100000000001001001000000000010
                         1:  1010000000011111111100000000110
                         2:  1011000000110000000010000001100
                         3:  1010100001101000000111000011011

The gray background highlights eight applications of the update rule on cells at different positions at different time steps. For example, the neighborhood of the cell at position 12 at t=0 (010) determines the state of this cell at t=1 (1). As another example, the neighborhood of the cell at position 24 at t=0 (000) determines that this cell stays off at t=1 (0). When determining the neighborhoods of the edge cells (first and last cells in the array), the array is “wrapped” around. Specifically, the cell after the last one is the first cell, and the cell before the first one is the last cell. Hence, the neighborhood of the last cell at t=0 (position 30) is 101 determining that the the cell at position 30 at t=1 is off. Once cell states at time t are determined, one can compute cell states at time t+1. CourseNana.COM

There are 8 = 23 possible neighborhoods and 256 = 223 possible update rules defined for elementary cellular automata. It is convenient to refer to each rule by its code, given as a number from 0 to 255. If one traverses possible neighborhoods in order 111, 110, 101, 100, 011, 010, 001, 000 (in the descending order of the encoded binary numbers), writes out the corresponding next states in the same order, and interprets the obtained sequence of symbols as the binary representation of an integer, the resulting number is the code of the rule. For instance, the example update rule presented above results in the binary representation 00011110 of number 30. Hence, CourseNana.COM

this update rule is rule 30. Many of the 256 rules are trivially equivalent, for example, by swapping roles of 0 and 1 or by reflection via the vertical axis. There are only 88 fundamentally different update rules. CourseNana.COM

Cellular automata have many applications, including studies of complex behaviors in nature (rule 30), prime numbers (rule 90), traffic flows (rule 184), and computability (rule 110). Artem and Alistair need a tool to study new ways of solving computational problems using cellular automata. Your task is to implement this tool. CourseNana.COM

Input Data CourseNana.COM

Your program should read input from stdin and write output to stdout. The input will list instructions, one per input line, each terminating with “\n”, that is, one newline character. The input specifies how to configure and execute an elementary cellular automaton and to collect basic statistics about the evolution of its states. The following file test0.txt uses seven lines to specify an example input to your program. CourseNana.COM

  1. 1  31 5 0,5 CourseNana.COM

  2. 2  306 30,10 CourseNana.COM

  3. 3  **..........*..*..*..........*. 7 CourseNana.COM

  4. 4  10 CourseNana.COM

Lines 1–3 in the test0.txt file specify a configuration of the automaton. Line 1 defines the size of the au- tomaton, that is, the number of cells in the array. Line 2 specifies the code of the update rule, whereas line 3 encodes the cell states, with “*” encoding on states and “.” encoding off states. Hence, line 3 specifies the example automaton discussed in the Background section. Line 4 specifies the number of time steps to evolve the automaton in Stage 1 of the program. Finally, lines 5 and 6 are instructions to analyze the evolution of states of cells at specific positions in the automaton in Stages 1 and 2 of the program, respectively. CourseNana.COM

The input will always follow the proposed format. You can make your program robust by handling inputs that deviate from this format. However, such extensions to the program are not expected and will not be tested. CourseNana.COM

Output CourseNana.COM

The output your program should generate for the test0.txt input file is in the test0-out.txt file and below. CourseNana.COM

  1. 1  ==STAGE 0============================ CourseNana.COM

  2. 2  SIZE: 31 CourseNana.COM

  3. 3  RULE: 30 CourseNana.COM

  4. 4  ------------------------------------- CourseNana.COM

  5. 5  000 001 010 011 100 101 110 111 CourseNana.COM

  6. 6  01111000 CourseNana.COM

  7. 7  ------------------------------------- CourseNana.COM

  8. 8  0: **..........*..*..*..........*. CourseNana.COM

  9. 9  ==STAGE 1============================ CourseNana.COM

  10. 10  0: **..........*..*..*..........*. CourseNana.COM

  11. 11  1: *.*........*********........**. CourseNana.COM

  12. 12  2: *.**......**........*......**.. CourseNana.COM

  13. 13  3: *.*.*....**.*......***....**.** CourseNana.COM

  14. 14  4: ..*.**..**..**....**..*..**..*. CourseNana.COM

  15. 15  5: .**.*.***.***.*..**.******.**** CourseNana.COM

  16. 16  6: .*..*.*...*...****..*......*... CourseNana.COM

  17. 17  7: *****.**.***.**...****....***.. CourseNana.COM

  18. 18  8: *.....*..*...*.*.**...*..**..** CourseNana.COM

  19. 19  9: .*...******.**.*.*.*.*****.***. CourseNana.COM

  20. 20  10: ***.**......*..*.*.*.*.....*..* CourseNana.COM

  21. 21  ------------------------------------- CourseNana.COM

  22. 22  #ON=3 #OFF=3 CELL#0 START@5 CourseNana.COM

  1. 34  18: .*.*.*.*.*.*.*......*..*.*.*.*. CourseNana.COM

  2. 35  19: ..*.*.*.*.*.*.*......*..*.*.*.* CourseNana.COM

  3. 36  20: *..*.*.*.*.*.*.*......*..*.*.*. CourseNana.COM

  4. 37  21: .*..*.*.*.*.*.*.*......*..*.*.* CourseNana.COM

  5. 38  22: *.*..*.*.*.*.*.*.*......*..*.*. CourseNana.COM

  6. 39  23: .*.*..*.*.*.*.*.*.*......*..*.* CourseNana.COM

  7. 40  24: *.*.*..*.*.*.*.*.*.*......*..*. CourseNana.COM

  8. 41  ------------------------------------- CourseNana.COM

  9. 42  RULE: 232; STEPS: 15. CourseNana.COM

  10. 43  ------------------------------------- CourseNana.COM

  11. 44  24: *.*.*..*.*.*.*.*.*.*......*..*. CourseNana.COM

  12. 45  25: .*.*....*.*.*.*.*.*...........* CourseNana.COM

  13. 46  26: *.*......*.*.*.*.*............. CourseNana.COM

  14. 47  27: .*........*.*.*.*.............. CourseNana.COM

  15. 48  28: ...........*.*.*............... CourseNana.COM

  16. 49  29: ............*.*................ CourseNana.COM

  17. 50  30: .............*................. CourseNana.COM

  18. 51  31: ............................... CourseNana.COM

  19. 52  32: ............................... CourseNana.COM

  20. 53  33: ............................... CourseNana.COM

  21. 54  34: ............................... CourseNana.COM

  22. 55  35: ............................... CourseNana.COM

  23. 56  36: ............................... CourseNana.COM

  24. 57  37: ............................... CourseNana.COM

  25. 58  38: ............................... CourseNana.COM

  26. 59  39: ............................... CourseNana.COM

  27. 60  ------------------------------------- CourseNana.COM

  28. 61  #ON=10 #OFF=20 CELL#30 START@10 CourseNana.COM

  29. 62  ------------------------------------- CourseNana.COM

  30. 63  10: ***.**......*..*.*.*.*.....*..* CourseNana.COM

  31. 64  AT T=10: #ON/#CELLS < 1/2 CourseNana.COM

  32. 65  ==THE END============================ CourseNana.COM

  1. 23  ==STAGE 2============================ CourseNana.COM

  2. 24  RULE: 184; STEPS: 14. CourseNana.COM

  3. 25  ------------------------------------- CourseNana.COM

  4. 26  10: ***.**......*..*.*.*.*.....*..* CourseNana.COM

  5. 27  11: **.**.*......*..*.*.*.*.....*.* CourseNana.COM

  6. 28  12: *.**.*.*......*..*.*.*.*.....** CourseNana.COM

  7. 29  13: .**.*.*.*......*..*.*.*.*....** CourseNana.COM

  8. 30  14: **.*.*.*.*......*..*.*.*.*...*. CourseNana.COM

  9. 31  15: *.*.*.*.*.*......*..*.*.*.*...* CourseNana.COM

  10. 32  16: .*.*.*.*.*.*......*..*.*.*.*..* CourseNana.COM

  11. 33  17: *.*.*.*.*.*.*......*..*.*.*.*.. 66 CourseNana.COM

Stage 0 – Reading, Analyzing, and Printing Input Data (10/20 marks) CourseNana.COM

The first version of your program should read the automaton configuration from input, construct a representation of the initial state of the automaton at t=0, and print basic information about the automaton to the output. The first eight lines in the test0-out.txt file correspond to the output your program should generate in Stage 0 based on the first three input lines in the test0.txt file. Line 1 of the output prints the Stage 0 header. Lines 2 and 3 print the size of the automaton and the code of the update rule, respectively. Lines 5 and 6 visualize the update rule using the principles explained in the Background section. Line 8 prints the automaton state at t=0. Use "%4d:" format specifier to printf the time step, and use “*” and “.” characters to printf on and off cell states, respectively. Finally, lines 4 and 7 print the delimiter lines of 37 “-” characters. CourseNana.COM

You should not make assumptions about the maximum number of cells requested from the input for the automaton your program should construct. Use dynamic memory and data structures of your choice, for example, arrays or linked lists, to store the history of states of the automaton. CourseNana.COM

Stage 1 – Execute Automaton (16/20 marks) CourseNana.COM

In Stage 1, your program should execute the automaton configured in Stage 0 for the requested number of time steps and print the number of on and off states a particular cell has been at in the requested period of execution. Lines 9 to 22 in the test0-out.txt file correspond to the output your program should generate in this stage based on the instructions at lines 4 and 5 in the test0.txt input file. Line 4 in the test0.txt file specifies the number of time steps the automaton should execute starting from the initial state (t=0), while line 5, using format x,y, requests to count and print the number of on and off states of the cell at position x in the automaton starting from time step t=y and to the last so far executed time step. Hence, the instructions in the test0.txt file request to evolve the initial state of the automaton for ten time steps and count the number of observed on and off states of the cell at position zero starting from time step t=5 up to and including time step t=10. CourseNana.COM

The output of Stage 1 should start with the corresponding header; see line 9 in the test0-out.txt file. The subsequent lines, lines 10 to 20 in the test0-out.txt file, print the automaton states in chronological order they were observed, starting with the initial state (t=0) to the last computed state (t=10). Again, use “*” and “.” characters to denote on and off cell states and the "%4d:" format specifier to format the output of time steps. CourseNana.COM

The output line that follows all the printed states should be the delimiter line of 37 “-” characters; see line 21 in the test0-out.txt output file. Next, your program should print the counts of on and off states of the requestedcellusingthe"#ON=%d #OFF=%d CELL#%d START@%d\n"formatspecifier;seeline22intheoutput. CourseNana.COM

You should not make assumptions neither about the maximum number of time steps that can be requested to evolve the automaton nor about the requested cell position or time step to start counting the cell states. CourseNana.COM

Stage 2 – Solve Practical Problem (20/20 marks) CourseNana.COM

Given an array of zeros and ones (bits), the density classification problem consists in deciding if the array contains more zeros or more ones. Fuks ́ [1] showed that elementary cellular automata based on rules 184 and 232 could solve this problem perfectly. Specifically, given an automaton of k cells, one should first execute the automaton for n = (k 2)/2time steps using update rule 184 and then evolve the resulting state for m = (k 1)/2steps using update rule 232; xdenotes the largest integer less than or equal to x. If all the cells of the resulting automaton are on, then the state of the original automaton has more on states. In contrast, if all the cells of the resulting automaton are off, then the state of the original automaton has more off states. Finally, if cells in the resulting automaton exhibit an alternating sequence of on and off states (regardless of the state of the cell at position zero in the array), then the state of the original automaton has the same number of on and off cells. CourseNana.COM

In Stage 2, your program should apply the procedure of Fuks ́ described above to solve the density classifica- tion problem for the state of the automaton computed for the last time step in Stage 1 (t=10 for the test0.txt input file). The output of Stage 2 should start with the corresponding header; see line 23 in the test0-out.txt file. In the subsequent lines, your program should print the evolution of the automaton using rules 184 and 232, with rules applied in the correct order for the correct number of time steps. Lines 24 to 60 in the test0-out.txt file print this output for the automaton resulting from Stage 1. Lines 24 and 42 inform about the changes in the update rule and the number of time steps the new rules are applied, while lines 25, 41, 43, and 60 are the delimiter lines of 37 “-” characters. CourseNana.COM

The subsequent line (line 61 in test0-out.txt) in the output should print the number of on and off states for the cell at position starting from the time step requested on line 6 in the test0.txt input file. Finally, CourseNana.COM

CourseNana.COM

after the delimiter line (line 62 in test0-out.txt), your program should print the automaton for which the density classification problem was solved (line 63) and the answer to the problem (line 64). As all the cells in the automaton at t=39 are off, there are more off cells than on cells in the automaton at t=10. Replace the “<” symbol in the result message (line 64) with “=” or “>”, as required by other inputs to your tool. CourseNana.COM

Stage 3 – Have Fun (no marks for fun as fun is your reward) CourseNana.COM

Search for other solutions to interesting practical problems using elementary cellular automata, implement them, and share them with the class via the discussion board.  CourseNana.COM

Get in Touch with Our Experts

WeChat (微信) WeChat (微信)
Whatsapp WhatsApp
Unimelb代写,COMP10002代写,Foundations of Algorithms代写,C代写,Dynamic memory代写,Cellular Automaton代写,Unimelb代编,COMP10002代编,Foundations of Algorithms代编,C代编,Dynamic memory代编,Cellular Automaton代编,Unimelb代考,COMP10002代考,Foundations of Algorithms代考,C代考,Dynamic memory代考,Cellular Automaton代考,Unimelbhelp,COMP10002help,Foundations of Algorithmshelp,Chelp,Dynamic memoryhelp,Cellular Automatonhelp,Unimelb作业代写,COMP10002作业代写,Foundations of Algorithms作业代写,C作业代写,Dynamic memory作业代写,Cellular Automaton作业代写,Unimelb编程代写,COMP10002编程代写,Foundations of Algorithms编程代写,C编程代写,Dynamic memory编程代写,Cellular Automaton编程代写,Unimelbprogramming help,COMP10002programming help,Foundations of Algorithmsprogramming help,Cprogramming help,Dynamic memoryprogramming help,Cellular Automatonprogramming help,Unimelbassignment help,COMP10002assignment help,Foundations of Algorithmsassignment help,Cassignment help,Dynamic memoryassignment help,Cellular Automatonassignment help,Unimelbsolution,COMP10002solution,Foundations of Algorithmssolution,Csolution,Dynamic memorysolution,Cellular Automatonsolution,