Insegnamento a.a. 2022-2023

20602 - COMPUTER SCIENCE (ALGORITHMS)

Department of Computing Sciences

Course taught in English
Go to class group/s: 31
DSBA (6 credits - II sem. - OP  |  FIS/02)
Course Director:
LAURA SANITA'

Classes: 31 (II sem.)
Instructors:
Class 31: LAURA SANITA'


Suggested background knowledge

To feel comfortable in this course you should have a good knowledge of calculus, linear algebra, 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 be able to use them as building blocks in their own work. In particular, they will see combinatorial and graph algorithms, optimization algorithms, approximation algorithms and the fundamentals of NP-completeness.

CONTENT SUMMARY

Basic Notions and Theoretical Background

  • Introduction to the course

  • Algorithmic efficiency 

  • Asymptotic Notation

  • Class P and NP

 

Combinatorial and Graph Algorithms

  • Greedy Algorithms and Spanning trees

  • Dynamic Programming

  • Shortest Path and Network Flows

  • Matchings and Generalizations

 

Optimization Algorithms

  • Linear Programming and Integer Progamming
  • Simplex algorithm
  • Branch and Bound algorithm 
  • Stochastic Optimization
  • Algorithms for large scale optimization 

 

NP-Completeness and Approximation Algorithms

  • NP-Completeness reduction
  • Approximation algorithms 


 


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 and various design paradigms
  • Develop an intuition about which problems are amenable to which kind of programming paradigm and relate this to common computational tasks
  • Analyze the structure of advanced algorithmic schemes
  • Understand combinatorial structures 
  • Understand graph and optimization algorithms
  • 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 problems
  • Show which problems cannot admit effiicient solutions

Teaching methods

  • Face-to-face lectures

DETAILS

Lectures.


Assessment methods

  Continuous assessment Partial exams General exam
  • Written individual exam (traditional/online)
    x
  • Individual assignment (report, exercise, presentation, project work etc.)
x    

ATTENDING AND NOT ATTENDING STUDENTS

There will be a written exam and two homework assignments. The homework assignments are not mandatory. The final grade will be calculated by taking for each student the best outcome out of the following two ones:
(a) Final written test contributes 70% of the final grade, and homework assignments contribute 30%.
(b) Final written test contributes 100% of the final grade.

 

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 formulate optimization problems with linear/integer programming models, and apply the most suitable algorithm to solve them.

 


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.
  • 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.
  • W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver. Combinatorial Optimization. Wiley-Interscience, 1997.
  • Lecture notes and slides by the instructor.
Last change 13/12/2022 01:44