VictorNGomes/datastructure

Repository for DCA0209, an undergraduate course about Data Structure and Algorithms

Federal University of Rio Grande do Norte

Technology Center

Department of Computer Engineering and Automation

Algorithms and Data Structure II

References

• 📚 Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. Data Structures and Algorithms in Python [Link]
• 📚 Mark Newman. Networks [Link]
• 📚 Menczer, Filippo; Fortunato, Santo; A. Davis, Clayton. A First Course in Network Science [Link]
• 📚 Dmitry Zinoviev. Complex Network Analysis in Python [Link]
• 📚 Coscia, Michele. The Atlas for the Aspiring Network Scientist [Link]

Tools

• Networkx [Link]
• Graph-Tool [Link]
• Gephi [Link]
• OSMnx [Link]

Lessons

Week 01: Course Outline

• Python for Data Engineering: Fundamentals Part I
  • You'll learn the fundamentals of programming with Python for data engineers: a) Processing numerical data and text data, b) Performing basic Python operations such as creating variables and lists, c) Analyzing data using for loops, d) Writing conditional statements and using comparison operators.
  • ⏳ Estimated time: 6h
• Git and Version Control
  • You'll learn how to: a) organize your code using version control, b) resolve conflicts in version control, c) employ Git and Github to collaborate with others.
  • 👊 getting a git repository.
  • ⏳ Estimated time: 5h
• Complementary materials
  • Google Colab Introduction
  • Google Colab Cont. [optional]
  • ⏳ Estimated time: 2h

Week 02: A brief introduction to data structure in Python

• Python for Data Engineering: Fundamentals Part II
  • You will see: a) refining fundamental Python knowledge for data engineering; b) introducing basic Python concepts like dictionaries, functions, and default arguments; c) building proficiency in the use of Jupyter Notebook; d) practical application of your newly acquired data skills in a data project for your portfolio.
  • ⏳ Estimated time: 10h
• Object Oriented Programming (OOP) introduction
  • ⏳ Estimated time: 3h
• OOP practice problems
  • ⏳ Estimated time: 1.5h

Week 03: Complexity Algorithm I

• Exercises
  • Part I
  • Part II
• Challenge template
• Complementary notebook
• Time Complexity of Algorithms
  • you will learn how: a) measure the execution time of a algorithm; b) generate random inputs for an algorithm; c) model the execution time of an algorithm.
  • ⏳ Estimated time: 1h
• Constant Time Complexity
  • you will learn: a) Identify constant time operations; b) Identify how computers manage memory; c) Refine computing time complexity models; d) Identify hidden function calls in Python. e) Identify how lists and strings are stored in memory.
  • ⏳ Estimated time: 2h
• Case Studies

Week 04: Complexity Algorithm II

• Big $O$, $\Theta$ , $\Omega$ notations
  • Big $O$ notation
  • Big $\Omega$ notation
  • Big $\Theta$ notation
  • ⏳ Estimated time: 1h
• Logarithmic time complexity
  • Binary search algorithm
  • Crash course about Logarithmic time complexity
    • you will learn: a) explain logarithms and logarithmic complexity; b) apply the binary search algorithm to find elements in sorted lists.
    • ⏳ Estimated time: 1h
• Sorting Algorithms Complexity
  • Selection Sort
    • you will learn: a) apply a sorting algorithm; b) identify the time complexity of sorting in Python.
    • ⏳ Estimated time: 1h

Week 05, 06: Project I

Week 07: Network Elements I

• Part 01
• Part 02
  • Basic Definitions
  • Extended Graphs
  • Density, Sparsity and Subnetworks
  • Degree and Network Representation
  • ⏳ Estimated time: 2h
• Hands on
  • Network elements using networkx and graph-tool

Week 08: Network Elements II

• Exercise
  • ⏳ Estimated time: 6h