Skip to content
Snippets Groups Projects
Select Git revision
  • 405c73d0f658d7605c3c109944740d884a4ea5fa
  • main default protected
2 results

algo-bsc

user avatar
more updates
Romain Vuillemot authored
405c73d0
History
user avatar 405c73d0
History
Name Last commit Last update
assignments
books
exercises
figures
lectures
notebooks
solutions
.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

Course outline and reading list

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 - Data structures and complexity

Lecture 2 - Recursion and lists

  • Definition and principles of recursion
  • Base cases and recursive cases
  • Recursion vs. iteration
  • Tail recursion
  • Lists, Search
  • Introduction to lists (arrays vs. linked lists)
  • Operations on lists (insertion, deletion, traversal)
  • Searching algorithms (linear, binary)
📖 - 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 - Recursion and lists

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 - Stacks and queues

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 - Priority queues

Lecture 5 - Programming strategies: divide and conquer, greedy

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

Lab 5 - Programming strategies: divide and conquer, greedy

Lecture 6 - Programming strategies: dynamic programming

  • Definition and characteristics of dynamic programming
  • Memoization data structures
  • Examples (using dynamic programming): Fibonacci, Knapsack Problem
📖 - Dynamic programing

Lab 6 - Programming strategies: dynamic programming

Lecture 7 - Binary trees

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

Lab 7 - Binary trees

Lecture 8 - Trees

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

Lab 8 - Trees

Lecture 9 - Graphs

  • Introduction to graphs (vertices and edges)
  • Types of graphs (directed, undirected, weighted, unweighted)
  • Representing graphs as adjacency matrix, adjacency list
  • Graph properties (connectivity, cycles)
📖

Lab 9

Lecture 10 - Graphs algorithms (1/2)

  • Minimum spanning tree algorithms (Prim & Kruskal algorithms)
  • Topological sorting
  • Graph traversal algorithms (depth-first search, breadth-first search)
📖
  • ..

Lab 10

Lecture 11 - Graphs algorithms (2/2)

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

Lab 11

Exam

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

Books and ressources

Exercices to practice:

Other ressources: