cs211 Programming assignment 2 (150 points)
Programming assignment 2 (150 points)
Start Assignment
Due Friday by 10pm Points 150 Submitting a file upload File Types tar Available Feb 12 at 12am – Mar 3 at 11:59pm
Stacks, Queues, Trees, Graph algorithms in C (150 points, approximately 12.5% of course grade)
Prof. Yipeng Huang Rutgers University 2023 Spring
0. Introduction and setup Learning goals
You will practice programming more complicated C programs. This includes using header files to organize your source code, using and building data structures, and using recursive function calls. At the same time, you will review and learn about important data structures and graph algorithms found throughout computer science.
Get started early! As with all programming assignments, you will have to go through several cycles of getting stuck, seeking resources, and debugging before you can complete the assignment in full. Starting early allows you to identify what you don’t know with enough time to figure it out. There are many resources to turn to offered by this class and by the department:
1. Post questions to Piazza (https://piazza.com/class/lcs2fx0sqqa2xu) so your classmates, the TAs, and the instructor can answer you collaboratively.
https://rutgers.instructure.com/courses/210629/assignments/2449058 1/18
2023/2/23 23:22 Programming assignment 2 (150 points)
2. Ask questions during recitation and during office hours (https://rutgers.instructure.com/courses/210629/pages/recitation-and-office-hour-information) .
3. The computer science student space, CAVE, is available to help you in this class and your other CS classes. The CAVE page is up to date (https://resources.cs.rutgers.edu/docs/rooms- equipment/cave/ (https://resources.cs.rutgers.edu/docs/rooms-equipment/cave/) (https://resources.cs.rutgers.edu/docs/rooms-equipment/cave/) )
4. Please avoid emailing the TAs and instructors directly as you won’t get as quick of a response, and your fellow students would not be able to learn from your questions.
Academic integrity
You can discuss the assignment with your classmates, but you cannot copy code from your classmates.
You can use the internet to research the mechanics of the C programming language, the documentation for useful C functions, and to search about error messages you encounter, but you cannot use websites that offer ready-made answers specific to this assignment and this class. Consider citing any sources that you use in your research; such a citation can be as simple as providing a link to a webpage in a code comment.
We will be checking the assignments for identical and/or plagiarized code using automated tools.
It is not acceptable to share or post any course materials online without explicit permission from the instructor.
https://www.cs.rutgers.edu/academics/undergraduate/academic-integrity-policy (https://www.cs.rutgers.edu/academics/undergraduate/academic-integrity-policy) https://www.cs.rutgers.edu/academics/undergraduate/academic-integrity- policy/programming-assignments (https://www.cs.rutgers.edu/academics/undergraduate/academic- integrity-policy/programming-assignments)
The instruction staff takes the Rutgers University Academic Integrity Policy seriously. Please review it at: https://nbprovost.rutgers.edu/academic-integrity-students (https://nbprovost.rutgers.edu/academic-integrity-students) . We will report all violations.
The autograder script for this assignment needs two Python packages that you can easily install. Once you are logged into ilab, run the following command in any directory; this command may take a couple minutes to complete:
pip install networkx scipy
If you do not already have access to ilab, activate your account here:
https://services.cs.rutgers.edu/accounts/activate/activate
https://rutgers.instructure.com/courses/210629/assignments/2449058 2/18
2023/2/23 23:22 Programming assignment 2 (150 points)
(https://services.cs.rutgers.edu/accounts/activate/activate) .
For information on how to access the ilab Linux machines using ssh or x2go from a Windows or Mac machine, see: https://resources.cs.rutgers.edu/docs/new-users/beginners-info/ (https://resources.cs.rutgers.edu/docs/new-users/beginners-info/) .
Access the programming assignment files for this assignment by cloning this Github repository:
git clone https://github.com/yipenghuang0302/2023_0s_211.git
Since you should already have the 2023_0s_211 directory in your iLab home directory, you can run this command from 2023_0s_211 to get new directories and files from the Github repository:
The files for this assignment are in the directory 2023_0s_211/pa2/.
1. bstLevelOrder: breadth-first level order traversal of a binary search tree using a queue (easy) (20 points)
Your task in this part of the assignment is to write a C program that constructs a binary search tree from a list of input numbers, and then print out the binary search tree in a level order, left-to-right, traversal of the tree. You may find it helpful to review the properties of a binary search tree, and the various flavors of tree traversal order. In a binary search tree, the key in each node is greater than all keys in its left subtree, and is lesser than all keys in its right subtree.
Your program should take as a command line input the path to an input file:
./bstLevelOrder tests/test0.txt
Each line of the input file lists a number to be inserted into the binary search tree. If a number has already been inserted, you can ignore the duplicate insertion. Since we are not performing tree balancing, everyone should arrive at the same binary search tree structure for any given input sequence. For example, an input sequence of 8,3,6,1,10,4,14,7,13 would lead to this unique binary search tree (image credit wikimedia):
https://rutgers.instructure.com/courses/210629/assignments/2449058 3/18
2023/2/23 23:22 Programming assignment 2 (150 points)
Once the binary search tree is constructed, your program should print out the nodes in a level-order, left- to-right, traversal of the tree. Such a traversal of the example tree above would return the numbers in this order: 8, 3, 10, 1, 6, 14, 4, 7, 13
The corresponding expected outputs are in the answers directory: answers/answer0.txt.
How to compile, run, and test your code
First, you should rename bstLevelOrder_provided.c to bstLevelOrder.c by entering:
mv bstLevelOrder_provided.c bstLevelOrder.c
Your program should be written in the file bstLevelOrder.c. To compile your source code bstLevelOrder.c, you can type:
gcc -g -Wall -Werror -fsanitize=address -std=c99 -o bstLevelOrder bstLevelOrder.c
We’ve provided in that command several important useful compiler flags.
Alternatively, to build the executable, you can type:
Once your program is successfully compiled, you can run your program:
./bstLevelOrder tests/test0.txt
https://rutgers.instructure.com/courses/210629/assignments/2449058 4/18
2023/2/23 23:22 Programming assignment 2 (150 points)
You should make sure your C program returns EXIT_SUCCESS or 0 indicating successful program termination.
To use the autograder script to test your program, you can type:
./autograder
python3 autograder.py
We will be automatically building, testing, and grading your assignment. Make sure that we can build your assignment by just using the Makefile and that we can run the program by invoking our autograder. Make sure to follow the required output format; any extraneous output such as debugging statements will confuse the grading program. You can check if you have accidentally modified your autograder:
git diff autograder.py
2. edgelist: Loading, representing, and printing an undirected unweighted graph (easy) (20 points)
Graphs are fundamental data structures. A graph consists of nodes and edges connecting pairs of nodes. A basic kind of graph is an undirected, unweighted graph, meaning that the edges are not directional, and each edge doesn’t have any additional properties. Here is an example of an undirected, unweighted graph G=(V,E), V={0,1,2,3}, E={(0,1),(0,2),(0,3),(1,3)} of four nodes and four edges:
https://rutgers.instructure.com/courses/210629/assignments/2449058 5/18
2023/2/23 23:22 Programming assignment 2 (150 points)
There are several important ways to represent graphs.
The first graph representation is an adjacency matrix (https://en.wikipedia.org/wiki/Adjacency_matrix) . The adjacency matrix of the above graph is:
The 0, 1, 1, 1 in the first row of the matrix indicates the 0th node is connected to the 1st, 2nd, and 3rd nodes, and so on.
The second graph representation is an adjacency list (https://en.wikipedia.org/wiki/Adjacency_list) . For a graph consisting of N nodes, the adjacency list data structure is an array of N separate linked lists for each node p, where each link in the linked list records a node q if the edge (p,q) exists. For example, the adjacency list representation of the above graph is:
The ->/ indicates a null pointer terminating the linked list.
0 111 1 001 1 000 1 100
0->1->2->3->/
1->0->3->/
3->0->1->/
https://rutgers.instructure.com/courses/210629/assignments/2449058 6/18
2023/2/23 23:22 Programming assignment 2 (150 points)
The third graph representation is by listing the edges of the graph. For example, the edge list of the above graph is:
In this part of the assignment, you will write a program that:
1. Loads an adjacency matrix representation of an undirected unweighted graph, 2. Holds that graph representation as a adjacency list data structure,
3. Prints out the edge list representation of the graph.
An important C header file, graphutils.h, is provided to you in 2023_0s_211/pa2/graphutils.h. This file offers ready-to-use functions for loading a adjacency matrix, creating an adjacency list data structure, and freeing the adjacency list. You should call these functions to simplify your code.
Input format
Your program should take a single command line argument specifying the path to an input file. Test cases for your program are in the tests/ directory. In each test case, the first line records the number of nodes N in the graph. Then, the adjacency matrix is recorded in the subsequent N rows of the file.
Output format
Expected outputs from your program for each test case are in the answers/ directory. You should print one line for each edge of the graph; each line should list the pair of nodes (separated by a space) constituting a graph edge.
This is an undirected graph, so the order of the nodes does not matter. The autograder will recognize re- ordering of the nodes as correct. The ordering of which edges are printed first also does not matter. The autograder will recognize re-ordering of the edges as correct.
3. isTree: Determining whether an undirected graph is a tree using depth-first search (medium) (20 points)
An undirected graph is a tree if and only if the graph contains no cycles. For example, this is a tree because it contains no cycles:
02 03 01 13
https://rutgers.instructure.com/courses/210629/assignments/2449058 7/18
2023/2/23 23:22 Programming assignment 2 (150 points)
While this graph contains cycles and therefore is not a tree:
https://rutgers.instructure.com/courses/210629/assignments/2449058 8/18
2023/2/23 23:22 Programming assignment 2 (150 points)
In this part of the assignment, you will write a depth-first search through a graph to determine whether the graph contains cycle. A cycle is detected when depth-first search find a graph node that was already visited.
Input format
Your program should take a single command line argument specifying the path to an input file. Test cases for your program are in the tests/ directory. In each test case, the first line records the number of nodes N in the graph. Then, the adjacency matrix is recorded in the subsequent N rows of the file.
Output format
You should print “yes” if the graph is a tree, “no” if the graph is not a tree. Expected outputs from your program for each test case are in the answers/ directory.
https://rutgers.instructure.com/courses/210629/assignments/2449058 9/18
Computer Science Tutoring
2023/2/23 23:22 Programming assignment 2 (150 points)
4. solveMaze: Finding the shortest path through a maze
with cycles using breadth-first search (medium) (20
In this third part of the assignment, you will write a program to find a shortest path in a graph from a source node to a destination node using breadth-first search. The graph representing the maze may contain cycles, so it is important avoid revisiting nodes that have already been visited.
Many important problems in artificial intelligence, robotics motion planning, and self-driving cars boil down to solving mazes on graphs. In classes such as AI and robotics, you will learn about advanced algorithms for solving mazes using heuristics (or informed guesses) that minimize search time.
Input format
Your program should take TWO command line arguments. The first argument specifies the path to an input file describing a graph like previous portions of this assignment. The second argument specifies the path to an input file describing a query. The first line of the query file specifies the source node where you begin your search. The second line of the query file specifies the target node you want to reach.
Output format
You should print a list of edges that, taken together, connect the source node to the target node in the graph. Again, the ordering of the nodes in each edge does not matter. The ordering of the edges does not matter. The autograder will check to see if you give a minimal set of edges that connect the source and target nodes.
5. mst: Finding the minimum spanning tree of a undirected weighted graph (medium) (20 points)
A weighted graph is a graph that has a numerical weight property on each edge. The minimum spanning tree (MST) of an undirected weighted graph is a tree that connects all nodes in the graph, and at the same time minimizing the sum of the weights of the tree’s edges. Many important problems in computer
https://rutgers.instructure.com/courses/210629/assignments/2449058 10/18
2023/2/23 23:22 Programming assignment 2 (150 points)
networking and operations research boil down to finding MSTs on graphs. As an example, this is a undirected weighted graph:
And this is its MST:
https://rutgers.instructure.com/courses/210629/assignments/2449058 11/18
2023/2/23 23:22 Programming assignment 2 (150 points)
The edges (0,1) and (1,2) connects all nodes in the graph, and picking these edges minimizes the total weight of the tree. If all the weights in an undirected weighted graph are unique, then the MST is also unique, meaning everyone will find the same MST for a given graph.
In this part of the assignment, you will write a program implementing another example of a greedy algorithm to find the MST. Several algorithms solve this problem, but Prim’s algorithm (https://en.wikipedia.org/wiki/Prim%27s_algorithm) is likely the easiest to implement.
Input format
Your program should take a single command line argument specifying the path to an input file. Test cases for your program are in the tests/ directory. In each test case, the first line records the number of nodes N in the graph. Then, the adjacency matrix is recorded in the subsequent N rows of the file. This time, the adjacency matrix contains floating point numbers. 0.0 indicates no edge between two nodes. Any other value indicates an edge with the given value as the edge weight.
Output format
https://rutgers.instructure.com/courses/210629/assignments/2449058 12/18
程序代写 CS代考 加微信: cstutorcs
2023/2/23 23:22 Programming assignment 2 (150 points)
Expected outputs from your program for each test case are in the answers/ directory. You should print a list of edges that, taken together, form the MST of the input graph. Again, the ordering of the nodes in each edge does not matter. The ordering of the edges does not matter.
6. findCycle: Finding a cycle in a directed graph using depth-first search (hard) (25 points)
A directed graph is a graph where edges are directional; that is, edges (p,q) and (q,p) are distinct. An important class of directed graphs are directed acyclic graphs (DAGs), which have broad applications in programming languages and compilers. A DAG is any directed graph with no cycles. For example, this is a directed graph:
The above graph is not a DAG because it contains cycles. The cycles are:
By extension, these rotated versions are also valid cycles of the above graph (and they are all such possible rotations):
https://rutgers.instructure.com/courses/210629/assignments/2449058 13/18
2023/2/23 23:22 Programming assignment 2 (150 points)
In this final part of the assignment, you will bring together ideas you have used throughout this assignment to find and print a cycle in a directed graph. If no cycles are found, your program will report that the graph is a DAG. You can use any algorithm for this task; either the DFS or the BFS approaches you have used in this assignment so far can be useful.
Input format
Your program should take a single command line argument specifying the path to an input file. Test cases for your program are in the tests/ directory. In each test case, the first line records the number of nodes N in the graph. Then, the adjacency matrix is recorded in the subsequent N rows of the file. This time, the adjacency matrix represents a directed graph.
Output format
You should print a single line of nodes (separated by spaces) that forms a cycle in the input directed graph. For example, for the example directed graph above you can print any one of the seven cycles listed above. This time, the ordering of the nodes does matter as this is a directed graph. If no cycles were found, your program should print “DAG”, meaning the graph is acyclic. The known cycles for each test case are in the answers/ directory. You can print out rotated versions of the known cycles; the autograder will see that rotated cycles are equivalent.
Suppose you enter the graph from 0, and find a cycle by following the path
0->7->4->5->7
Upon seeing 7 again, you know you have detected a cycle. You have to carefully determine where the cycle begins and ends in the path you have traversed.
7. matChainMul: Multiply a chain of matrices with an
optimal number of multiplication operations (hard) (25
https://rutgers.instructure.com/courses/210629/assignments/2449058 14/18
2023/2/23 23:22 Programming assignment 2 (150 points)
Dynamic programming algorithms are an important class of algorithms where a complex optimization problem is divided into subproblems, and the subproblems are tackled recursively. They have many applications throughout computer science such as computer networks and also in genome sequencing.
Here we will study how dynamic programming is used to optimally multiply a chain of matrices such that the fewest number of multiplication operations are needed. (https://en.wikipedia.org/wiki/Matrix_chain_multiplication) The matrix chain multiplication problem is to multiply at least three matrices, such as A*B*C*D. Because matrix multiplication is associative, one can perform this multiplication in one of several orders of operation:
1. A(B(CD)) 2. A((BC)D) 3. (AB)(CD) 4. (A(BC))D 5. ((AB)C)D
Depending on the dimensions of the matrices A, B, C, and D, the number of multiplications needed may vary greatly depending on how you parenthesize the matrix chain multiplication problem.
The dynamic programming approach to find the parenthesization that needs the fewest multiplication operations is to break the problem into subproblems, recursively find the cost of each subproblem, and then select among the subproblems for the most optimal approach. To be more concrete, suppose we want to perform that matrix chain multiplication of ABCD. For the first decision we would select among three ways to partition the problem:
1. A(BCD) 2. (AB)(CD) 3. (ABC)D
Now, the minimum cost of calculating BCD cannot be determined directly, so we have to recursively determine the cost of calculating B(CD) vs. (BC)D in order to determine the true cost of option 1.
Likewise, the minimum cost of calculating ABC cannot be determined directly, so we have to recursively determine the cost of calculating A(BC) vs. (AB)C in order to determine the true cost of option 3.
Input format
In the matChainMul/tests/ directory you have six given input test cases. In each test case file the format is as follows:
1. The first line is the number matrices in the chain.
https://rutgers.instructure.com/courses/210629/assignments/2449058 15/18
2023/2/23 23:22 Programming assignment 2 (150 points)
2. The second line is the row and column dimensions of the first matrix, separated by a space.
3. The subsequent several lines are the contents of the first matrix, one row per line, and each column
element separated by a space in each line.
4. After the first matrix is complete, the second matrix begins with a single line describing the row and
column dimensions of the second matrix, and so on.
For example, this input:
3 32 02 02 11 21 1
Describes the matrix chain multiplication:
Your program
You should write a C program that takes as a command line input the path to the test case file:
./matChainMul tests/test0.txt
Then, you should use a dynamic programming algorithm to calculate the product while using as few multiplication operations as possible.
You should use as a reference the provided example codes for dynamic programming and for matrix (non-chain) multiplication.
You are provided two key pieces of provided code for this assignment.
The matChainMul_provided.c code
In 2023_0s_211/pa2/matChainMul/matChainMul_provided.c you are given a working example of a C program that calculates the optimal cost of performing matrix chain multiplication. This code does not perform the actual matrix multiplication to find the product. Your task is to complete the program in matChainMul/ to calculate the matrix chain multiplication product.
https://rutgers.instructure.com/courses/210629/assignments/2449058
2023/2/23 23:22 Programming assignment 2 (150 points)
The pa2/matMul/matMul.h code
In 2023_0s_211/pa2/matMul/matMul.h you are given an implementation of matrix multiplication that calls a special function mul() to perform multiplication. The function also tallies all the scalar multiplications performed as part of matrix multiplication. Upon program exit, the program writes a file called mul_op_count.txt which reports the number of scalar multiplications that took place as part of program execution.
Expected output format
In the answers/ directory you have a file which records the expected number of operations and also the expected product matrix. You should print the product matrix only, one row per line, each column element separated by a space. For example, the answer.txt to the example above is:
Which means that 12 multiplications are needed at minimum, and the matrix product is:
You should print the matrix product. As a side of effect of using the using the matMul function in matMul.h, your program will also write a file called mul_op_count.txt which reports the number of scalar multiplications invoked to multiply the matrix chain. The autograder will check to see you used the expected number of scalar multiplication operations.
How to submit
From the pa2/ directory, you can check on the outputs of our autograder script. ./assignment_autograder.py
python3 assignment_autograder.py
12 46 46 46
https://rutgers.instructure.com/courses/210629/assignments/2449058
2023/2/23 23:22 Programming assignment 2 (150 points)
When you are ready to submit, from the 2023_0s_211/pa2/ directory, you should run these commands to make sure you are in the correct working directory:
should report you are in the directory 2023_0s_211/pa2.
should list at least these files and
subdirectories: assignment_autograder.py, quickselect/, editDistance/, and balanced/. Once you are sure you are in the right directory, run:
tar cvf pa2.tar ./
The assignment_autograder can check and grade the generated tar file:
./assignment_autograder.py pa2.tar
Make sure the tar file passes this test and returns the grade you expect. We will not accept or regrade empty tar files or tar files containing the wrong organization. Upload the file pa2.tar here on Canvas. By submitting your assignment, you are agreeing to the Rutgers Honor Pledge: “On my honor, I have neither received nor given any unauthorized assistance on this assignment.” We will not be accepting late assignments. The Canvas submission site will close to enforce the deadline, so be sure to submit early. If anything is not clear, reach out to your classmates and the instructors on the class Piazza!
https://rutgers.instructure.com/courses/210629/assignments/2449058
Programming Help