Home Page > > Details

Data Science Assignment ,C++ Programming Assignment ,Programming AssignmentHelp With , c++ Assignment Python Programming|Debug C/C++ Programming

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_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

Contact Us - Email:99515681@qq.com    WeChat:codinghelp
Programming Assignment Help!