Federal University of Rio Grande do Norte

This is the repository for the Algorithms and Data Structures II course, offered by the Department of Computer Engineering and Automation (DCA) of the Technology Center (CT) at the Federal University of Rio Grande do Norte (UFRN).

The DCA aims to train professionals capable of designing and developing computer systems for industrial automation, embedded systems, software systems, distributed systems, computer networks, and information systems. The CT offers undergraduate and graduate courses in Engineering. This course is part of the curriculum of the Computer Engineering program at DCA/UFRN.

• 📚 Coscia, Michele. The Atlas for the Aspiring Network Scientist
• 📚 Newman, Mark. Networks

Week 01

• Course Outline: Provides an overview of the course structure and topics covered.
  • 🎉 GitHub Education Benefits
    • GitHub Education Pro: Get access to the GitHub Education Pro pack by visiting GitHub Education
  • 📖 Learning Resources
    • GitHub Learning Game: Check out the interactive Git learning game at GitHub Learning Game

Week 02

• From Real-World Systems to Networks: Learn how real-world systems can be modeled as networks. We introduce the basic elements of a graph, explore different types of networks, and discuss applications involving social networks, transportation, temporal networks, and knowledge graphs.
  • Hands-on — Modeling Networks with NetworkX: Build, inspect, and manipulate graphs in Python. Practice graph representations, node and edge attributes, directed graphs, multigraphs, degree and neighborhood analysis, connectivity, and modeling decisions through guided examples and exercises.
  • 📚 Further Reading & Practice:
    • Chapters 2, 3, 6, and 7 of The Atlas for the Aspiring Network Scientist.
    • NetworkX Documentation
• Network Fundamentals II: Extended graphs, density and sparsity, subnetworks, degree, degree distribution, and network representation.
  • Exploring graph types, multilayer networks, density, subnetworks, degree, and adjacency matrices using NetworkX.
  • 📚 Further reading: chapters 7, 8, and 9 of the book The Atlas For The Aspiring Network Scientist.

Week 03

• Small-World Networks and Graph Traversal: Introduction to the small-world phenomenon through classical examples such as Milgram's experiment, the Erdős number, and the Oracle of Bacon. The lecture connects these concepts to graph traversal and shortest-path reasoning, with particular emphasis on Breadth-First Search (BFS) and Depth-First Search (DFS).
  • Case Study — Wikipedia Network: Construction and structural analysis of a directed network of Wikipedia pages using a snowball sampling strategy.
    • Compare BFS and DFS in terms of exploration strategy, frontier size, memory requirements, and path discovery.
    • Construct a directed network from Wikipedia pages starting from a predefined seed node.
    • Collect pages through a BFS-based snowball sampling process and analyze the growth of successive network layers.
    • Preprocess the network by handling duplicate nodes, self-loops, and sampling artifacts.
    • Examine the degree distribution and distinguish the network core from its low-degree fringe.
    • Analyze node relevance through indegree and outdegree and discuss the impact of the sampling strategy on the observed network structure.
    • Wikipedia Network — BFS-Based Sampling and Structural Analysis