Skip to content
Snippets Groups Projects
Select Git revision
  • main default protected
1 result

algo-bsc

  • Clone with SSH
  • Clone with HTTPS
    • user avatar
    lab 8
    Romain Vuillemot authored
    c75be6d8
    History
    user avatar c75be6d8
    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 - Trees

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

    Lab 8 - Exercises

    Lecture 9 - Graphs

    • Introduction to graphs (vertices and edges)
    • Types of graphs (directed, weighted)
    • Graphs data structures (adjacency matrix, adjacency list)
    • Graph properties (connectivity, cycles)
    📖

    Lab 9 - Exercises

    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 - 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: