COMP 2013-Sec. 1 Spring 2018 Homework 3 Your third lab will focus on graph and sorting which includes the following tasks: 1. a. Using C++, represent the following graph using adjacency matrix, and implement depth first searching (DFS) by stack (define it with class) to traverse the graph. 0 6 2 4 b. If starting with node 2, when node 7 is printed, what numbers are in the stack (for DFS)? Please draw the stack step by step to show how the numbers are pushed into and popped out of it. 2. a. Given a set of integer numbers as int Al]- (12, 8, 51, 0, 3, 7, 19,6, 4,21), please write down the divide and conquer procedure of quick sort (step by step), include all left and right positions adjustment, and overwriting. b. Using CIC++, define two integer arrays; each has 30 integers within [0, 99]. Use and rand to assign random integers to the arrays; then implement Selection and Insertion and Quick sort algorithms to sort the two arrays in ascending order, respectively (i.e. using selection to sort the 1t, and quick to sort the 2nd). For each array, print all array elements after sorting to verify the results. loop c. based on 2.b and the sorted array, define a function of the Binary Search algorithm, then input a number in main0 and call the binary search function to search a number in the sorted array and output the result (Note, search in one of the two sorted arrays will be enough) The following specifications will be expected for each programming project in this class: 1. An empty project file must be created at the beginning, and then you will create/add new source files and header files. 2. Add comments at the beginning of the program, and add description for each function, loop, etc. Turn in both the hardcopy and softcopy of your source code, including all.cpp and h file Your name, your ID number and lab number should be written on the upper right-hand corner of the top sheet of the hardcopy. Submit the soft copy through eCourse assignment link. Date Due: Wednesday, November 28th, 2018