Assessment 3 Hit 220 Cat Kutay September 2020 Rubric 1 Pseud ✓ Solved
Assessment 3 Hit220catkutayseptember 20201 Rubric1 Pseudo Code Shoul
Explain the requirements for pseudo code, including adherence to guidelines, clarity, structure, explanation sufficiency, submission format, and marking criteria. Clarify that drawing scans are acceptable, and describe the marking rubric focusing on accuracy, completeness, and reasoning. Outline the components of the assessment, including questions on graphs and trees, topological sort, shortest path algorithms, and sorting algorithms, along with specific tasks such as drawing graphs, providing pseudo code, and analyzing complexities.
Sample Paper For Above instruction
The assessment involves a comprehensive exploration of foundational concepts in graph theory, algorithms, and data structures. It requires not only constructing and analyzing various graph structures but also implementing algorithms and understanding their complexities. The following paper addresses each component in depth, demonstrating mastery of the topics through explanations, pseudo code, and analytical insights.
Graphs and Trees
In graph theory, a fundamental concept is the distinction between different types of graphs based on their structure. A graph with n vertices and n-1 edges that is connected is a tree, which is an acyclic, minimally connected graph. To illustrate this, one can draw three examples with varying numbers of vertices:
- Example 1: n = 3 vertices, edges = 2, forming a simple chain (V1—V2—V3). This is a straightforward tree.
- Example 2: n = 4 vertices, edges = 3, perhaps arranged with a branching point: V1 connected to V2, V3, V4.
- Example 3: n = 5 vertices, edges = 4, such as V1 connected to V2, V2 connected to V3, V3 connected to V4, and V4 connected to V5.
It is clear that such graphs are trees due to their connectedness and the lack of cycles.
Regarding the question of whether a connected graph with n vertices and n edges but no cycles exists, the answer is no. Such a graph necessarily contains a cycle. A graph with n vertices and n edges that is connected necessarily has exactly one cycle, making it a unicyclic graph. This is supported by the Euler characteristic for graphs, where in a connected graph, the number of edges equals the number of vertices minus one plus the number of cycles. Therefore, if no cycles exist, the number of edges must be less than or equal to n-1.
A particular example of a forest with 12 vertices and at least 8 edges can be constructed by connecting several trees or components. Consider a forest consisting of a main tree with 8 vertices and 7 edges, and an additional smaller tree with 4 vertices and 3 edges. Connecting these components without creating cycles yields a forest with 12 vertices and 10 edges. For example, a forest with two components: one with 8 vertices, the other with 4 vertices, satisfies the conditions.
The number of connected components in this forest is two, which relates to the total number of vertices and edges. According to graph theory, the number of connected components c relates to the total vertices v and edges e by the formula:
v = sum of vertices in components
e = sum of edges in components
and
number of components c = v - e + number of cycles, which, in a forest, is zero, hence c = v - e.
Given the graph with 12 vertices and 8 edges, the number of connected components is c = 12 - 8 = 4. This indicates there are four connected components, each being a tree, since the total edges are less than the number of vertices minus the number of components.
If the sum of degrees of all vertices is 24 in a graph with 12 vertices, then the sum of degrees is twice the number of edges, according to the Handshaking Lemma. Therefore, the total number of edges E = 24 / 2 = 12. For a simple graph, this means every vertex's degree sums to 24, and the total edges are 12, which confirms the earlier understanding, and indicates a dense graph with multiple connections per vertex.
Topological Sort List and Pseudo Code
The task involves providing a topological order for given graphs and pseudo code for the same. For example, given a directed acyclic graph (DAG), we identify vertices with no incoming edges as starting points. Repeatedly removing these and updating in-degrees of remaining vertices yields a topological order. When multiple choices are available, selecting the lowest alphanumeric vertex maintains order consistency.
Pseudo code for topological sort (non-generalized for simplicity):
Function TopologicalSort(Graph G):
Initialize in-degree list for each vertex in G
Initialize empty list for topological order
While there exists a vertex v with in-degree 0:
Choose the lowest alphanumeric vertex v with in-degree 0
Append v to topological order
For each neighbor u of v:
Decrement in-degree of u by 1
Return topological order
Shortest Path and Dijkstra’s Algorithm
Applying Dijkstra’s algorithm involves initializing distances, selecting the unvisited vertex with the smallest tentative distance, and updating neighbor distances iteratively. Illustrative tables at each stage demonstrate how shortest paths are discovered, and the spanning tree is constructed.
For example, in a graph with vertices labeled alphabetically, starting at the smallest vertex, we initialize distance table:
- At each stage, select the vertex with the minimum distance, mark it visited, and update neighboring vertex distances if a shorter path is found.
Graph Representations and Complexity Analysis
Shedding light on adjacency matrix and list representations, their structures, and efficiencies:
- Adjacency matrix: V x V matrix where entries indicate presence of edges; efficient for dense graphs, with O(1) access but O(V^2) space complexity.
- Adjacency list: for each vertex, a list of adjacent vertices; efficient for sparse graphs, with O(V + E) space, and operations like finding degrees depend on list length.
Operational complexities further analyzed:
- Finding the degree of a vertex in adjacency matrix is O(V), since all entries in row are checked.
- Finding the opposite vertex along an edge in adjacency list is O(E) in the worst case, but typically O(1) if the edge is directly accessible.
Sorting Algorithms and Their Complexities
Two sorting algorithms, selection sort and heap sort, are examined:
- Selection sort repeatedly finds the minimum element from unsorted portion and swaps it with the first unsorted element, with a worst-case complexity of O(n^2).
- Heap sort involves building a binary heap and repeatedly extracting the maximum element, with a worst-case complexity of O(n log n).
Conclusion
This comprehensive exploration underscores the importance of understanding fundamental concepts in graph theory and algorithms. Mastery over drawing graphs, analyzing their properties, implementing efficient algorithms, and understanding their complexities forms a core part of computer science education and practice.