Federal University of Rio Grande do Norte

Technology Center

Department of Computer Engineering and Automation

Algorithms and Data Structure II

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

• 📚 Newman, Mark. Networks
• 📚 Menczer, Filippo; Fortunato, Santo; Davis, Clayton A. A First Course in Network Science
• 📚 Zinoviev, Dmitry. Complex Network Analysis in Python
• 📚 Coscia, Michele. The Atlas for the Aspiring Network Scientist
• 📚 Knickerbocker, David. Network Science with Python
• 📚 Grimmer, Justin; Roberts, Margaret E.; Stewart, Brandon M. Test 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
• 🚀 Instant Coding with Codespaces
  • Learn how to start coding instantly using GitHub Codespaces
• 📖 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.

Week 02

• Review: topics covered include Recursion, Binary Search Trees (BST), and AVL Trees.
• 🎯 Week Goals
  • Your main goal for this week is related to following subjects: recursion, binary and avl trees. By the conclusion, you'll have the ability to distinguish between iteration and recursion, learn how to construct and query datasets using Binary Search Trees (BST) and get acquaninted with AVL trees.
• Recursion: dive into recursion and explore the implementation and analysis of the Merge Sort algorithm.
• Binary Trees: build and analyze the performance of a Binary Search Tree.
• AVL Trees: learn the mechanics behind AVL trees, self-balancing binary search trees, and their implementation.

Week 03

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

• 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.
• Challenges: Complexity of different operations in Binary Search Tree.
  • : Challenge 01: Find Closest Value.
  • : Challenge 02: Find Kth Largest Value.

Week 05

• Network Fundamentals I: Outline, applications, math and graph theory.
• Network Fundamentals II: Probability, extended graphs, matrices, degree and representation.
  • Basic Definitions
  • Extended Graphs
  • Density, Sparsity and Subnetworks
  • Degree and Network Representation
  • ⏳ Estimated time: 2h
• 🛠 Hands on
  • Network elements using networkx
  • 📚 Further reading: chapters 1 to 6 of the book The Atlas For The Aspiring Network Scientist