Federal University of Rio Grande do Norte

Technology Center

Department of Computer Engineering and Automation

Algorithms and Data Structure II (DCA3702)

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.

References

• 📚 Coscia, Michele. The Atlas for the Aspiring Network Scientist
• 📚 Newman, Mark. Networks
• 📚 Grimmer, Justin; Roberts, Margaret E.; Stewart, Brandon M. Text as Data: A new framework for Machine Learning and the Social Sciences
• 📚 Knickerbocker, David. Network Science with Python

Tool	Link
😃 Networkx	networkx.org
⚙️ Gephi	gephi.org
🚀 OSMnx	github.com/gboeing/osmnx
💾 Dataset	snap.stanford.edu/data

Lessons

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
    • Basic Python: Enhance your Python skills through the Kaggle Python course.
• Network Fundamentals I: Outline, applications, math and graph theory.
  • Network elements using networkx tool.
  • 📚 Further reading: chapters 2, 3, 6 and 7 of the book The Atlas For The Aspiring Network Scientist.

Week 02

• Network Fundamentals II: Probability, extended graphs, matrices, degree and representation.
  • Extended graphs and representation using networkx tool.
  • 📚 Further reading: chapters 7, 8, 9 of the book The Atlas For The Aspiring Network Scientist.

Week 03

• Project: Authorship Temporal Network Analysis

Week 04

• Small World: This week’s content focuses on core concepts such as Small World Networks, Homophily, and Assortativity. You will analyze how these properties shape the topology and dynamics of real-world networks.
  • Hands on assortativity: A hands-on notebook for computing and interpreting assortativity in real datasets.
  • The art of seeing networks: Explore key NetworkX functionalities for analyzing and visualizing complex networks.
  • 📚 Further reading: chapters 30 to 31 from The Atlas For The Aspiring Network Scientist, including the exercises.

Week 05

• Project unit 01

Week 06

• Small World Cont.: Paths, Distances, Connected Components, Clustering Coefficient, Social Distance and Six Degrees of Separation
  • Paths, Walks and Distances
  • Connected Components
  • Clustering Coefficient
• Classical Algorithms: Dijsktra: Shortest path algorithm
  • You will learn: a) Explain how the Dijkstra algorithm works. b) Understand the algorithm’s time complexity.
  • Ready to practice?
    • : Dijsktra: Implement the algorithm both with and without path reconstruction.
    • : Min-Heap: an implementation of Dijkstra's algorithm using a min-heap, with and without path reconstruction.

Week 07

• U2T1 Evaluating Algorithms for the Shortest Path in Urban Graphs

Week 08

• Heap Structures and Time Complexity: This lesson explores Min-Heap data structures, focusing on their array representation and the behavior of the main operations such as insert, remove, and peek.
  • Topics covered include:
    • Properties of a Min-Heap and array-based implementation
    • Understanding parent and child index calculations
    • Explanation of siftDown and siftUp mechanisms
    • Efficient heap construction from unsorted arrays using buildHeap
• MinHeap Implementation and Testing: Interactive Jupyter Notebook that includes the full implementation of a Min-Heap class in Python, along with detailed unit tests to validate correctness and ensure that the min-heap property is preserved after each operation.

Week 09

• A* Algorithm: Introduction to the A* algorithm, combining Dijkstra's search with heuristic-based guidance. Key concepts:

  • Combines Dijkstra (guarantees cheapest path) and Greedy search (guides exploration).
  • Heuristics:
    • Euclidean: for local planar maps.
    • Great-circle: for large geographical distances.
    • Manhattan: for grid-like networks.
  • A* process:
    1. Start at source node.
    2. For each neighbor, compute:
       • ( g ): actual cost.
       • ( h ): heuristic estimate.
       • ( f = g + h ).
    3. Use priority queue (lowest ( f ) first).
    4. Repeat until reaching the goal.
  • Visual flow:
    Start → [g + h] → expand node → update queue → repeat → Goal

• A* Implementation: Jupyter Notebook with A* implementation using NetworkX and OSMnx, applying different heuristics to real urban graphs.

Weeks 10 and 11

• U2T2 Evaluating A-Star Algorithm

Week 12

• Classical Algorithms - Kruskal: Minimum Spanning Tree

  • You will learn: a) Explain how the minimum spanning tree Kruskal's algorithm works. b) Understand the algorithm’s time complexity.
  • Ready to practice?
    • : Kruskal: Implement the minimum spanning tree algorithm.
    • : OSMnx example: A practical example using mst and OSMnx.

• U2T3: Applying Kruskal's Algorithm to Points of Interest in Natal's Urban Graph.

  • : Kruskal-POI: reference to be considered in the project.

Week 13

• Hubs: key centrality metrics and illustrative case studies.
  • Eccentricity, Diameter, Periphery, Radius, and Center
  • Degree, Closeness, Betweenness, and Eigenvector Centrality
  • Centrality distributions and interpretation
  • Core decomposition and its relevance
• Hands on: practical exploration of centrality measures

Week 14

• Directed networks: case study of Wikipedia pages

  • Building a networking from Wikipedia pages
  • Collecting data from a snowballing process
  • Truncate and eliminate duplicates
  • Exploring the network data
  • Wikipedia pages network

• Gephi: The Open Graph Viz Platform

  • A brief overview about Gephi
  • Quick start
  • Using layouts
  • Node and network measures
  • Visualize and filtering nodes and communities
  • Renderize, export the network, and highlight a community
  • Deploy the network into an HTML page
  • Another way to publish your network to the web using Retina and Gephisto

• Final Project

  • Notebook with the final project description and source code to generate the network under study.
  • Nodes file
  • Edges file