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

Tool	Link
😃 Networkx	networkx.org
💡 Graph-Tool	graph-tool.skewed.de
⚙️ Gephi	gephi.org
🚀 OSMnx	github.com/gboeing/osmnx
💣 ChatGPT	chat.openai.com
💾 Dataset	snap.stanford.edu/data

Lessons

Week 01

• Course Outline: Provides an overview of the course structure and topics covered.
  • 🎯 Week Goals
    • Your main goal for this week is to create a personal repository for tracking your progress and coursework.
    • Feel free to explore these resources and engage with the course material. If you have any questions or need assistance, please don't hesitate to reach out.
    • Happy coding! 💻🚀
  • 🎉 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.
    • AI Python for Beginners: Learn Python programming fundamentals and how to integrate AI tools for data manipulation, analysis, and visualization. Andrew Ng
• Network Fundamentals I: Outline, applications, math and graph theory.
  • 🛠 Hands on
  • Network elements using networkx
  • 📚 Further reading: chapters 1 to 4 of the book The Atlas For The Aspiring Network Scientist, including the exercises.

Week 02

• Network Fundamentals II: Probability, extended graphs, matrices, degree and representation.
  • 📚 Further reading: chapters 5 to 6 of the book The Atlas For The Aspiring Network Scientist, including the exercises.

Week 03

• Small World: This week, we explore key concepts such as Small World Networks, Homophily, and Assortativity. You will investigate how these concepts influence the structure and behavior of real-world networks.
  • Hands on assortativity
  • The art of seeing networks
  • 📚 Further reading: chapters 26 to 27 of the book The Atlas For The Aspiring Network Scientist, including the exercises.

Week 04

• Small World Cont.: Paths, Distances, Connected Components, Clustering Coefficient, Social Distance and Six Degrees of Separation
  • Paths, Walks and Distances
  • Connected Components
  • Clustering Coefficient

Week 05

• Hubs: the most important metrics and case studies.
  • Eccentricity, Diameter, Periphery, Radius and Center
  • Degree, Closeness, Betweenness and Eigenvector Centrality
  • Centrality Distributions
  • Core Decomposition
• Hands on centralities measures

Week 06

• 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

Week 07

• 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

Week 08

• Complexity of Algorithms I: Fundamentals and notations, time and constant complexity.
  • Let's Practice!
    • : Two numbers sum challenge.
  • How to Calculate the Complexity of the Most Common Use Cases Algorithms: Linear, quadratic, and constant complexity.
    • Fundamentals of Algorithms Complexity I
    • Fundamentals of Algorithms Complexity II
    • ⏳ Estimated time: 30min
  • Notations: Linear, quadratic, and constant complexity.
    • Big O Notation
    • Big Ω Notation
    • Big Θ Notation
    • ⏳ Estimated time: 30min
• Let's Practice (homework)!
  • Time Complexity of Algorithms
    • 👊 Skills You'll Gain: You will learn how to a) measure the execution time of an algorithm; b) generate random inputs for an algorithm; c) model the execution time of an algorithm.
    • : Time Complexity of Algorithms.
    • : Constant Time Complexity.

Week 09

• Complexity Algorithm II: Logarithmic time complexity
  • You will learn: a) explain logarithms and logarithmic complexity; b) apply the binary search algorithm to find elements in sorted lists.
  • : Guided Project: Code interview challenge.
  • Let's Practice, it is challenge time.
    • : Find closest value in BST: Write a function that takes in a Binary Search Tree (BST) and a target integer value and returns the closest value to that target value contained in the BST.
    • : Find kth largest value in BST: Write a function that takes in a Binary Search Tree (BST) and a positive integer k and return the kth largest integer contained in the BST.
    • : Benchmark: Compare the performance of the algorithms.

Week 10

• 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.

Week 11

• 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.

Week 12

• References for unit 2 project.
  • : Dijsktra: dijsdktra algorithm implementation modified to use min heap.
  • : Kruskal: A practical example using mst and OSMnx with a real-world network of streets in Natal-RN.