Course 2021-2022 a.y.

30540 - COMPUTER SCIENCE - MODULE 2 (COMPUTING THEORY AND ALGORITHMS)

Department of Decision Sciences

Course taught in English
Go to class group/s: 27
BAI (8 credits - II sem. - OB  |  INF/01)
Course Director:
LUCA TREVISAN

Classes: 27 (II sem.)
Instructors:
Class 27: LUCA TREVISAN


Suggested background knowledge

Students should have some familiarity with programming in an imperative programming language such as Java, C++ or Python, and be able to translate an algorithm formulated in pseudocode into working code in one such language. Students should be familiar with basic data structures such as lists, queues and binary trees, and with basic algorithms such as sorting and graph traversal. This course will emphasize the rigorous analysis of algorithms, and hence it will be helpful to possess the mathematical maturity that comes from having taken a proof-based mathematical course.

Mission & Content Summary

MISSION

Students will learn how to apply algorithm design techniques to new problems, and how to design an efficient algorithm, rigorously prove its correctness, and rigorously analyze the way in which the running time and memory requirements scale with the size of the input.

CONTENT SUMMARY

  • Divide-and-conquer algorithms and the solution of recurrence equations with the Master Theorem. Example will include mergesort, randomized linear-time median-finding, and fast multiplication of large integers
  • Review of graph algorithms. Introduction to directed and undirected graphs, notions of paths and connectivity. DFS exploration and use of DFS to find connected components in an undirected graph, to find topological sort of directed acyclic graphs, and find the strongly connected components of a general directed graph
  • Shortest paths algorithms. Dijkstra's alorithm
  • Dynamic programming. Examples will include shortest paths in graphs with negative edge weights, all-pairs shortest paths, knapsack and subset sum, edit distance and string alignment
  • Greedy algorithms. Examples will include minimum spanning trees and Huffman codes
  • Flow and cut problems. Max-Flow / Min-Cut theorem, Ford-Fulkerson methodology, Edmonds-Karp analysis, Karger's randomized algorithm for global min-cut, reduction of bipartite matching to Max Flow
  • Linear Programming. Formulating optimization problems as linear programming, duality, simplex algorithm
  • NP-completeness. Cook's theorem and some examples of NP-complete problems
  • Heuristic algorithms for NP-complete problems. Overview of techniques for the design of approximation algorithms

Intended Learning Outcomes (ILO)

KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • Master a number of algorithmic techniques, including divide-and-conquer, greedy, dynamic programming, graph traversal, and reduction to linear programming
  • Reason about the correctness of algorithms
  • Reason about the running time and the memory use of algorithms
  • Master the concept of NP-compleness

APPLYING KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • Design algorithms for problems that they have never seen before
  • Prove correctness of algorithms of their design
  • Analyze running time and memory use of algorithms of their design
  • Identify flaws in proposed algorithms that are not correct
  • Prove NP-completeness results

Teaching methods

  • Face-to-face lectures
  • Online lectures
  • Exercises (exercises, database, software etc.)

DETAILS

Online lectures will be developed as needed if face-to-face lectures cannot be attended by some or all students.

 

Exercises will be given, but not graded, throughout the course, for students to test their understanding of the material


Assessment methods

  Continuous assessment Partial exams General exam
  • Written individual exam (traditional/online)
  x x

ATTENDING AND NOT ATTENDING STUDENTS

The final grade will come 40% from a written partial exam and 60% from a written general exam. Exams include questions that test the students' understanding of the basic concepts presented in the course, and questions that require the design and analysis of an algorithm for a new problem.


Teaching materials


ATTENDING AND NOT ATTENDING STUDENTS

The recommended textbook is: 

  • Dasgupta, Papadimitriou, Vazirani Algorithms 2006, McGraw-Hill

 

Additional lecture notes will be posted on bboard and on the class website

Last change 21/12/2021 14:00