30540  COMPUTER SCIENCE  MODULE 2 (COMPUTING THEORY AND ALGORITHMS)
Department of Computing Sciences
Course taught in English
Go to class group/s: 27
Course Director:
LUCA TREVISAN
LUCA TREVISAN
Lezioni della classe erogate in presenza
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 proofbased 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
 Divideandconquer algorithms and the solution of recurrence equations with the Master Theorem. Example will include mergesort, randomized lineartime medianfinding, 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, allpairs 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. MaxFlow / MinCut theorem, FordFulkerson methodology, EdmondsKarp analysis, Karger's randomized algorithm for global mincut, reduction of bipartite matching to Max Flow
 Linear Programming. Formulating optimization problems as linear programming, duality, simplex algorithm
 NPcompleteness. Cook's theorem and some examples of NPcomplete problems
 Heuristic algorithms for NPcomplete 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 divideandconquer, 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 NPcompleness
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 NPcompleteness results
Teaching methods
 Facetoface lectures
 Online lectures
 Exercises (exercises, database, software etc.)
DETAILS
Online lectures will be developed as needed if facetoface 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  


x  x  

x 
ATTENDING AND NOT ATTENDING STUDENTS
The final grade will come 40% from a written partial exam, 55% from a written general exam, and 5% from the evaluation of individual assignments. Exams and assignments 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, McGrawHill
Additional lecture notes will be posted on bboard and on the class website
Last change 15/02/2023 11:28