Data Science代写、C++程序设计代写、Programming代做、代写c++语言

日期：2020-05-25 11:04

Programming Assignment 2

(take 20% in the final grade)

Data Science

United International College

Rubrics

• Refer to the Rubrics for programming on iSpace

• You will get full mark for Function test if

• Your code produces correct output for all our test inputs (hidden).

• The test inputs are not provided to you.

• Try your code against all possible inputs (that you can think of) to test correctness

• No memory leak is found in any case

• Program Structure refers to

• Reasonable file structure in the project

• Reasonable placement of function declarations and implementations

• Code style includes

• Reasonable naming of identifiers

• Reasonable indentation

• Code neatness

Data Structures and Algorithms 2

Task1: Building a binary tree (10 pts)

Data Structures and Algorithms 3

• Write a program to build a binary tree given the following input file format

• Input file format:

• Input file is a txt file (e.g. with name “my_test_tree.txt” ) with multiple lines

• Each line has three keys, the first is the parent and followed by the left and right children

• The first key in the first line is the root

• All keys are positive integers

• -1 means the child is empty

• For example:

• Submit a Build_tree.cpp file with main function

• After compiling, run the program in the following way should print the tree on the screen, you can use the “print_tree” functions in previous labs

> Build_tree my_test_tree.txt

Task2: Check if the input tree is a binary search tree (BST) (10 pts)

Data Structures and Algorithms 4

• Write a program to test whether a binary tree built from the input is

a binary search tree or not

• Input file format, the same as task 1

• Output: Yes (the tree is BST) or No (the tree is not BST)

• Submit:

1. check_bst.cpp, after compiling, run

➢check_bst my_test_tree.txt

Should output “Yes (the tree is BST)” or “No (the tree is not BST) “

2. Two sample input files composed by yourself, each contains a binary tree with at least three levels:

“my_test_tree1.txt” and “my_test_tree2.txt”, one is bst and the other is not

Task3: Build a BST(10 pts)

Data Structures and Algorithms 5

• Write a program to build a binary search tree using the input keys from the input

trees in task 2

• Input file format, the same as task 1 & 2

• Output:

• Yes, the tree is already BST or

• No, the input tree is not BST, and we re-build it as a BST

• Submit:

1. build_bst.cpp, after compiling, run

➢ build_bst my_test_tree.txt

Should output “Yes, the tree is already BST” or “No, the input tree is not BST, and we re-build it as a BST “

For both case, please print the BST you build

2. Two sample input files composed by yourself, each contains a binary tree with at least three levels:

“my_test_tree1.txt” and “my_test_tree2.txt”, one is BST and the other is not

Task4: Build an AVL tree without rotation(20 pts)

Data Structures and Algorithms 6

• Write a program to build an AVL tree without rotation

• Input file format: the input is a sequence of keys you need to insert into the AVL

tree, however, if you insert the keys in the given order in the sequence, you

might need to rotate to make the tree an AVL tree

• Output format: print out on the screen a sequence that contain all the keys in

the input, however, the sequence of the keys need to be adjusted such that if

you insert the keys in an AVL tree following the new output sequence, no

rotation is needed

• For example

• Input “2, 1, 3” -> output “2, 1, 3”

• Input “2, 4, 1, 3, 5, 6, 7” -> output “4, 2, 6, 1, 3, 5, 7”

Task4: Build an AVL tree without rotation

Data Structures and Algorithms 7

• Submit:

1. avl_no_rotate.cpp, after compiling, run

➢avl_no_rotate my_test_sequence.txt

Should output a new sequence

Task5: Breadth First Search (15 pts)

• Write a program to read the graph information from the file and traverse

the graph using BFS algorithm as introduced in lecture.

• The input for each algorithm is an undirected unweighted connected graph

stored in a local file using an adjacency list.

• Following is the example of the input file (graph.txt) and the graph

• First line is the number of nodes.

• Start from second line, the first integer is the node number and remaining numbers

forms the adjacency list of this node).

Task5: Breadth First Search

• The traversal requirements are:

1. Your traversal needs to start from the node with maximum degree (if there are multiple

nodes with same degree, start with the node with largest number).

2. If a node has several neighbors, visit the neighbors in decreasing order.

3. Output the traverse sequence as the result.

Submit:

1. bfs.cpp, after compiling, run

➢ bfs my_test_graph.txt, and the output should be the traverse sequence.

2. Two sample input files composed by yourself, each contains a graph:

“my_test_graph1.txt” and “my_test_graph2.txt”.

Task6: BFS Tree or Forest (15 pts)

• In this task, you need to implement graph traversal using BFS on

directed unweighted graph.

• The input format for graph is same with task5.

• The traversal requirements are same with task5 except that each BFS will start

from the node with maximum out-degree.

• You may encounter the scenario that during one BFS, the queue is empty, but

there are still nodes in graph that are unvisited. In this case, you need to

repeat the BFS on remaining nodes, until all nodes are visited.

• In such case, the paths found by BFS is no longer a single tree, instead are

multiple trees - BFS forest.

• Output the traversal sequence and indicate whether the traversal results in

BFS tree or BFS forest.

Task6: BFS Tree or Forest

Submit:

1. bfstree_forest.cpp, after

compiling, run

➢ bfstree_forest my_test_graph.txt,

and the output should be the traverse

sequence and BFS tree or BFS forest.

2. Two sample input files composed

by yourself, each contains a graph:

“my_test_graph1.txt” and

“my_test_graph2.txt”, one result is

bfs tree and another result is bfs

forest.

Task 7: Topological Sort (20 pts)

• Write a program to read the Directed Acyclic Graph from the file and perform topological

sort on the graph:

• Output the sorting result if topological sorting is possible.

• Otherwise, output “Topological sort is impossible”.

• Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such

that for every directed edge (u, v), vertex u comes before v in the ordering (topological

Sorting for a graph is not possible if the graph is not a DAG). The pseudocode for

topological sort is:

Repeat:

Find a vertex with no incoming edges (if multiple nodes,

return the node with maximum number )

Remove it from graph

Put it at beginning of list

Until graph is empty

Task 7: Topological Sort

graph.txt

Sample Input and Output:

Output:

graph.txt

Output:

Topological sort is

impossible

Submit:

1. toposort.cpp, after compiling, run

➢ toposort my_test_graph.txt, and the output

should be the sorting result or “topological sort

is impossible”.

2. Two sample input files composed by yourself,

each contains a graph:

“my_test_graph1.txt” and

“my_test_graph2.txt”, one graph exist a

topological sort and another graph not.

Submission

1. Put the complete set of source files with your test input files for

each problem into a folder named with the problem ID.

• For example, the code set (.h and .cpp files) for Task 1 should be in folder 1.

2. Compress all the folders into a zip with name: PA2_<your student

id>.zip

3. Submit the .zip file to iSpace.

Data Structures and Algorithms 14

Plagiarism Policy

• You are encouraged to collaborate in study groups.

• But, you cannot copy or slightly change other students’ solutions or codes.

• We will check between everyone’s submission.

• We will check with online solutions.

• If copies are found, everyone involved gets ZERO mark.

Data Structures and Algorithms 15