Facebook pixel
Info
Foto sezione
Logo Bocconi

Course 2021-2022 a.y.

20602 - COMPUTER SCIENCE (ALGORITHMS)

DSBA
Department of Decision Sciences

Course taught in English


Go to class group/s: 31

DSBA (6 credits - II sem. - OP  |  FIS/02)

Classes: 31 (II sem.)
Instructors:
Class 31: CHRISTOPH JOHANN FEINAUER


Suggested background knowledge

To feel comfortable in this course you should have a good knowledge of calculus, statistics, probability theory and programming.


Mission & Content Summary
MISSION

The course will teach the students the fundamentals of designing and analysing algorithms. The students will learn to apply design paradigm when designing their own algorithms and will be able to estimate the computational complexity and the resource requirements of algorithms they encounter. They will be familiarized with important algorithms and data structures and be able to use them as building blocks in their own work. They will also understand algorithms on graphs, randomized algorithms, optimization algorithms and the fundamentals of NP-completeness.

CONTENT SUMMARY

Introduction: Basic Notions and Theoretical Background

  • Introduction, Turing Machines

  • Stacks and Queues

  • Array Resizing, Analysis of Algorithms, Asymptotic Notation, Exercises

 

Programming Paradigms and Data Structures

  • Sorting, Comparison Sort Limits, Quicksort

  • Master Theorem

  • Binary Heaps, Binary sort, Binary Queues

  • Binary Search Trees, Red-Black Trees

  • Hash Tables

  • Shortest Path Algorithms

  • Dynamic Programming I

  • Dynamic Programming II

  • Algorithms for large scale data 

 

NP-Completeness

 

  • NP-Completeness
  • Approximation algorithms 

 

Optimization Algorithms

  • Linear Programming
  • Simplex algorithm
  • Interior point methods
  • Network flow algorithms, max flow min cuts I
  • Network flow algorithms, max flow min cuts II
  • Online decision making I
  • Online decision making II 

 

Randomized Algorithms

  • Randomized algorithms I
  • Randomized algorithms II

Intended Learning Outcomes (ILO)
KNOWLEDGE AND UNDERSTANDING
At the end of the course student will be able to...
  • Understand the basic notions of algorithmic complexity, various design paradigms and data structures
  • Develop an intuition about which problems are amenable to which kind of programming paradigm and relate this to common computational tasks like sorting and optimization
  • Analyze the structure of advanced algorithmic schemes
  • Understand optimization algorithms and the role of randomness
  • Understand implications of NP-completeness
APPLYING KNOWLEDGE AND UNDERSTANDING
At the end of the course student will be able to...
  • Design algorithms using common paradigms and predict their scaling in terms of memory and computational resources
  • Describe algorithms (possibliy developed by the students themselves) in pseudocode
  • Read literature on algorithm design
  • Develop algorithms for large scale difficult optimization problerms
  • Show which problems cannot admit effiicient solutions

Teaching methods
  • Face-to-face lectures
DETAILS

Lectures.


Assessment methods
  Continuous assessment Partial exams General exam
  • Individual assignment (report, exercise, presentation, project work etc.)
  •     x
    ATTENDING AND NOT ATTENDING STUDENTS

    The exam consists of a presentation and questions. The presentation can be either about a specific topic related to the course content, or about a project that the students complete before the exam. Several possible topics and projects will be proposed and students can also suggest their own ideas. The questions will be about the presentation and related topics that were covered in class.

     

    The exam will test the students' ability to explain algorithms using the concepts learned in class and connect these concepts to specific problem instances. It will further test if the student can describe the scaling properties of the presented algorithms in terms of the mathematical notions of complexity learned in class. Depending on the topic of the presentation, the abilities of the students in the design of algorithms will be assessed and the understanding of related topics from the course will be tested.

     

     


    Teaching materials
    ATTENDING AND NOT ATTENDING STUDENTS
    • T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST, et al., Introduction to Algorithms, MIT, 3rd edition.
    • R. SEDGEWICK., and K. WAYNE.  Algorithms. Addison-wesley professional, 4th Edition.
    • C. MOORE, S. MERTENS, The Nature of Computation, Oxford.
    • R. MOTWANI, P. RAGHAVAN, Randomized algorithms, Cambridge University Press New York, NY, USA
    • Bertsimas, Dimitris, and John N. Tsitsiklis. Introduction to linear optimization. Vol. 6. Belmont, MA: Athena Scientific, 1997
    • Garey, Michael R., and David S. Johnson. Computers and intractability. Vol. 174. San Francisco: freeman, 1979.
    • Lecture notes by the instructors.
    Last change 10/12/2021 11:47