Skip to content
Snippets Groups Projects
Select Git revision
  • main default protected
1 result
user avatar
Solutions for lab 10 and 11
Romain Vuillemot authored
53128489
History
user avatar 53128489
History
Name Last commit Last update
assignments
books
figures
labs-solutions
labs
lectures-notebooks
lectures
.gitignore
README.md
README.md

UE5 Fundamentals of Algorithms

Bachelor of Science in Data Science for Responsible Business

Instructor: Romain Vuillemot

     

Course description

  • Basics of algorithms and data structure
  • Justification of the choice of data structures
  • Calculate the complexity of an algorithm
  • Optimize algorithms
  • Write advanced programs using efficient algorithms and data structures

Course material

⚠️ The class material will be constantly updated, please download it using VS Code with GIT or using Github Desktop and update it frequently.

Course outline

Lecture 1 - Data structures and complexity

  • Introduction to data structures
  • Complexity calculation and analysis (Big O notation)
  • Data structures
  • Trade-offs between time/space complexity and different data structures
  • Empirical calculation of complexity
📖

Lab 1 - Exercises

Lecture 2 - Recursion and lists

  • Definition and principles of recursion
  • Base cases and recursive cases
  • Recursion vs. iteration
  • Tail recursion
📖 - Think Python chapter 11 (lists), chapter 12 (tuples) - Python for Everybody chapter 8 (lists) and Real Python lists - sorts. - Think Python chapter 5 (Conditionals and recursion) and Real Python recursion.

Lab 2 - Exercises

Assignment 1

Lecture 3 - Stacks and queues

  • Definition and characteristics of stacks and queues
  • Stack operations (push, pop, peek)
  • Queue operations (enqueue, dequeue, peek)
  • Applications
📖

Lab 3 - Exercises

Lecture 4 - Priority queues

  • Definition and characteristics of priority queues
  • Comparison with regular queues (FIFO) and stacks (LIFO)
  • Min/Max-priority queues
  • Binary heaps
📖

Lab 4 - Exercises

Lecture 5 - Programming strategies: divide and conquer, greedy

  • Recursive, independent problem-solving strategy
  • Application to sorting (merge sort, quick sort) and search (binary search)
  • Fibonacci
  • Knapsack Problem (greedy)
📖

Lab 5 - Exercises

Lecture 6 - Programming strategies: dynamic programming

  • Definition and characteristics of dynamic programming
  • Memoization data structures
  • Optimizing Fibonacci, Knapsack Problem using dynamic programming
📖 - Dynamic programing

Lab 6 - Exercises

Lecture 7 - Binary trees

  • Data structures (arrays, adjacency lists)
  • Convertion between tree representations
  • Tree traversal techniques (preorder, inorder, postorder, level-order)
📖

Lab 7 - Exercises

Lecture 8 and 9 - Trees

  • Data structures (arrays, adjacency lists)
  • Tree properties checks
  • Tree traversal methods (depth-first search, breadth-first search)
📖

Lab 8 and 9 - Exercises

Lecture 10 and 11- Graphs

  • Introduction to graphs (vertices and edges)
  • Types of graphs (directed, weighted)
  • Graphs data structures (adjacency matrix, adjacency list)
  • Graph properties (connectivity, cycles)
  • Graph traversal algorithms (depth-first search, breadth-first search)
📖

Lab 9 - Exercises

📖
  • ..

Lab 10 - Exercises

Lecture 11 - Graphs algorithms (2/2)

  • Shortest path algorithms (Bellman-Ford & Dijkstra algorithms)
📖
  • ..

Lab 11 - Exercises

Exam

  • Final written exam on paper
  • 2h
  • No document

Books and ressources

Exercices to practice:

Other ressources: