CTEC2909: Analysis of Data Structures and Algorithms Assignment

This assignment delves into the realm of data structures and algorithms, focusing on edge-weighted digraphs and graph representations. The student explores the concept of shortest paths in digraphs, considering assumptions and complexities, and chooses graphs as the primary data structure. The solution elaborates on the components of a graph, including vertices, edges, and adjacency, and selects an adjacency matrix for implementation. It provides real-world examples of graph applications, such as in urban planning, circuit systems, and project management. Furthermore, it includes algorithms for printing all paths from a source to a destination and counting the number of ways to a given destination. The assignment concludes with a detailed list of references.

Data structures
Student’s Name:
Institution Affiliation:

1. a)
An edge-weighted digraph is a digraph where we associate weights or costs with each edge. A
shortest path from vertex s to vertex t is a directed path from s to t with the property that no other
such path has a lower weight(Moir, Luchangco, Herlihy, & Oracle America Inc, 2015).
Assumptions
Ways are coordinated. A briefest way should regard the heading of its edges.
The loads are not really separates. Geometric instinct can be useful, however the edge loads may
speak to time or cost(Chatzistergiou, Cintra, & Viglas, 2015).
Not all vertices need be reachable. On the off chance that t isn't reachable from s, there is no way by
any means, and in this way there is no most brief way from s to t.
Negative loads present complexities. For the occasion, we expect that edge loads are sure (or zero).
Most brief ways are regularly straightforward. Our calculations overlook zero-weight edges that
structure cycles, with the goal that the most brief ways they find have no cycles.
Most limited ways are not really one of a kind. There might be numerous ways of the most minimal
load starting with one vertex then onto the next; we are substance to locate any of them.
Parallel edges and self-circles might be available. In the content, we expect that parallel edges are
absent and utilize the documentation v->w to allude to the edge from v to w, yet our code handles
them without trouble(Kruus, Ungureanu, Xia, NEC Corp, 2016).
1. b)

I choose graphs data structure. graphs give a definitive in information structure adaptability. A chart
comprises of a lot of hubs, and a lot of edges where an edge associates two hubs. Trees and records
can be seen as exceptional instances of diagrams. A chart G=(V,E) comprises of a lot of vertices V
and a lot of edges E, with the end goal that each edge in E is an association between a couple of
vertices in V. [1] The quantity of vertices is composed |V|, and the quantity of edges is composed |
E|. |E| can extend from zero to a limit of |V|2−|V|. We are going to choose adjacency matrix(David,
Guerraoui, & Trigonakis, 2015, March).
Vertex- Every hub of the diagram is spoken to as a vertex. In the accompanying model, the named
circle speaks to vertices. Along these lines, A to G are vertices(Belazzougui, Cunial, Gagie, Prezza,
& Raffinot, 2015, June). We can speak to them utilizing an exhibit as appeared in the
accompanying picture. Here A can be distinguished by file 0. B can be distinguished utilizing list 1,
etc(Torre, Dinn, & Red Hat Inc, 2018).
Edge- Edge speaks to a way between two vertices or a line between two vertices. In the
accompanying model, the lines from A to B, B to C, etc speaks to edges. We can utilize a two-
dimensional cluster to speak to an exhibit as appeared in the accompanying picture. Here AB can be
spoken to as 1 at line 0, section 1, BC as 1 at line 1, segment 2, etc, keeping different mixes as
0(Bhattacharya, Henzinger, & Italiano, 2018).

Adjacency- Two hub or vertices are contiguous in the event that they are associated with one
another through an edge. In the accompanying model, B is neighboring A, C is adjoining B, etc.
Paath- Way speaks to a succession of edges between the two vertices. In the accompanying model,
ABCD speaks to a way from A to D(Cao, Jia, Zhu, & International Business Machines Corp,
2019).
1. c)

2.
In maps that draw urban areas/states/locales as vertices and nearness relations as edges.
When we have a chart of a specific idea, they can be effectively utilized for finding most brief
ways, venture arranging, and so on.
In circuit systems where purposes of association are drawn as vertices and segment wires become
the edges of the chart.
In vehicle systems where stations are drawn as vertices and courses become the edges of the chart.
Charts are likewise used to draw movement system graphs. These graphs are widely utilized as a
venture the executives device to speak to the associated connections between gatherings, steps, and
undertakings that significantly affect the task.
In program stream examination where strategies or modules are treated as vertices and calls to these
methods are drawn as edges of the graph.In program stream investigation where methodology or
modules are treated as vertices and calls to these systems are drawn as edges of the diagram.
In state progress graphs, the hubs are utilized to speak to states and the edges speak to lawful moves
from one state to the next.
In flowcharts or control-stream diagrams, the announcements and conditions in a program are
spoken to as hubs and the progression of control is spoken to by the edges
3. Examples

(I) Printing all ways of the departure from source to a destination. The idea is to do Depth First
Traversal of given facilitated graph. Start the traversal from source. Keep securing the visited
vertices in a bunch say 'path[]'. If we touch base at the objective vertex, print substance of path[].
The huge thing is to check current vertices in path[] as visited in like manner, with the objective that
the traversal doesn't go in a cycle.
(ii) Counting of the quantity of ways to a given destination.
Approach
To find all of the manners in which involvement with any rate one stepped (cell containing - 1). If
we find the manners in which that don't encounter any of the stepped cells and all the potential ways
from (0, 0) to (n-1, m-1) by then we can find all of the ways that involvement in any occasion one
of the engravings cells.

References
Belazzougui, D., Cunial, F., Gagie, T., Prezza, N. and Raffinot, M., 2015, June. Composite
repetition-aware data structures. In Annual Symposium on Combinatorial Pattern Matching (pp. 26-
39). Springer, Cham.
Bhattacharya, S., Henzinger, M. and Italiano, G.F., 2018. Deterministic fully dynamic data
structures for vertex cover and matching. SIAM Journal on Computing, 47(3), pp.859-887.
Cao, Y., Jia, H.J. and Zhu, X.Z., International Business Machines Corp, 2019. Node controllers for
hierarchical data structures. U.S. Patent Application 10/223,463.
Chatzistergiou, A., Cintra, M. and Viglas, S.D., 2015. Rewind: Recovery write-ahead system for in-
memory non-volatile data-structures. Proceedings of the VLDB Endowment, 8(5), pp.497-508.
David, T., Guerraoui, R. and Trigonakis, V., 2015, March. Asynchronized concurrency: The secret
to scaling concurrent search data structures. In ACM SIGARCH Computer Architecture News (Vol.
43, No. 1, pp. 631-644). ACM.
Kruus, E., Ungureanu, C. and Xia, W., NEC Corp, 2016. Bucketized multi-index low-memory data
structures. U.S. Patent 9,471,500.
Moir, M.S., Luchangco, V.M. and Herlihy, M., Oracle America Inc, 2015. Obstruction-free data
structures and mechanisms with separable and/or substitutable contention management
mechanisms. U.S. Patent 9,052,944.
Torre, M. and Dinn, A., Red Hat Inc, 2018. Generating an adjacency graph from a series of linear
linked data structures. U.S. Patent Application 10/003,510.