Maze Problem
Description
In this section you need to complete a program satisfying following requirements. First, the
program reads a string that can have two inputs, random or defined. When the input is random ,
the program first needs to randomly generate a maze with both length and width of 10, which can
be represented by a two-dimensional array. The position of the number 0 represents the road in
the maze, and the number 1 represents the wall. The exit position of the maze must be at the
edge, represented by the number 3. Randomly set a possible position in the maze to the player's
initial position, replace the original 0 with 2, and print the array of maze to the screen. The
program then manipulates the player in the maze to the exit of the maze, and finally returns a
string representing the player's movements. Each character in the string represents the direction
of each movement of the player, with E, S, W and N representing the four directions of right,
down, left and up on the plane. When defined is entered, the program needs to read a ".txt" file
that defines the maze condition as described above. The program then needs to go through the
maze and eventually return the movement direction string.
Submission Requirements
You will need to hand in the source code and the generated ".exe" file as well as a report. In your
report, you will need to explain your ideas and key techniques, and you will need to show
examples of mazes that your program outputs and strings that it returns.
Maze Example
1 1 1 3 1
1 0 0 0 1
1 1 1 0 1
1 0 2 0 1
1 1 1 1 1
Output Example
ENNN
Communication Channel
Consider the following communication graph example where the nodes hold different
information at each time slot and can communicate with their neighbors to exchange the
information. When a node sends its information, we say it is active.
They satisfy the following communication rules:
1) Each node can broadcast its information to its neighbors, (e.g., node sends its information to
nodes and ).
2) Each node can receive information from one of its neighbors at one slot. (e.g., when node
receives node ‘s information, it cannot receive node 's information at the same time.)
3) At each time slot, nodes only 'receive' or 'broadcast' and cannot do both. (e.g., when node
broadcasts its information, it cannot receive other information.)
4) Each pair of nodes (connected by a link) cannot be active at the same time. (e.g., when node
broadcasts, nodes and cannot broadcast. And node or node can be active.)
If we set a sequence of 'active nodes' and 'receiving nodes', all nodes can receive all the
information from their neighbors after some finite slots. This process is called an iteration. After
one iteration, nodes continue communication and exchange new information. Note that the two
iterations can overlap each other, i.e., some slots belong to two consecutive iterations (This will be
elaborated in the following example).
Example
Given the above graph, we can set the following rules in the first iteration:
Here and are active nodes, receive 's information and receives 's.
# time slot 1:
A -> B,E
D -> C
# time slot 2:
B -> C,D
E -> A
# time slot 3:
C -> B
E -> D
can receive 's information, but it makes no sense because one iteration haven't finished yet.
Here the first and the second iterations overlap with each other. Of course the rules in each
iteration can be different to each other.
Task
You will be given a graph with 8 nodes and 100,000 time slots in total. You need to find an
efficient communication strategy over 100,000 slots to maximize the number of iterations and
record this strategy. The output contains the average slots per iteration. The graph is shown as
below,
Submit
You need to submit a .zip file which contains
1) your source code
2) an .exe file
3) code report: explanation of your code, the average slots per iteration.
4) a .txt file: recording your communication strategy
# time slot 4:
D -> B,E
# time slot 5:
B -> A,D
# time slot 6:
C -> D ; (the first iteration completed)
A -> B,E (the second iteration starts)
Remark
There will not be optimal strategy in this work. We will compare the 'average slots per iteration' of
all the students and score your code according to it. (Less average slots lead to higher score.)
File Compression
Design a program to fulfill two functions.
1. Read multiple files and generate a compressed file with Huffman code. Please name the
compressed file as "package.zip"
2. Read file "package.zip" and decompress it.
Make sure the decompressed files are the same as the original ones. The number of files is less
than or equal 10 and their total size is smaller than available memory.
Control the function of the program through different parameters. You can take the following
cods as an template:
Commands
The following command compress file1~3
The following command (with no extra parameter) decompress file"package.zip"
Submit
Please compile your code and submit the zip file to OJ, which contains 1) your source code, 2) the
.exe file and 3) the code report.
int main(int argc, char* argv[]) {
if (argc == 1) {
// if there is no extra parameter, read file "package.zip" and
decompress it
decompress("package.zip")
}
else {
// if there are extra parameters, read corresponding files and
compressed them
File* files[10];
int file_nb = argc - 1;
for (int i=0; i