First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Engineering
COMPUTER ENGINEERING
Course unit
DATA STRUCTURES AND ALGORITHMS 2
IN14112348, A.A. 2017/18

Information concerning the students who enrolled in A.Y. 2017/18

Information on the course unit
Degree course Second cycle degree in
COMPUTER ENGINEERING
IN0521, Degree course structure A.Y. 2009/10, A.Y. 2017/18
N0
bring this page
with you
Number of ECTS credits allocated 9.0
Type of assessment Mark
Course unit English denomination DATA STRUCTURES AND ALGORITHMS 2
Department of reference Department of Information Engineering
E-Learning website https://elearning.dei.unipd.it/course/view.php?idnumber=2017-IN0521-000ZZ-2017-IN14112348-N0
Mandatory attendance No
Language of instruction Italian
Branch PADOVA
Single Course unit The Course unit can be attended under the option Single Course unit attendance
Optional Course unit The Course unit can be chosen as Optional Course unit

Lecturers
Teacher in charge GEPPINO PUCCI INF/01

ECTS: details
Type Scientific-Disciplinary Sector Credits allocated
Educational activities in elective or integrative disciplines INF/01 Computer Science 2.0
Core courses ING-INF/05 Data Processing Systems 7.0

Course unit organization
Period First semester
Year 1st Year
Teaching method frontal

Type of hours Credits Teaching
hours
Hours of
Individual study
Shifts
Lecture 9.0 72 153.0 No turn

Calendar
Start of activities 25/09/2017
End of activities 19/01/2018
Show course schedule 2019/20 Reg.2009 course timetable

Examination board
Board From To Members of the board
9 A.A. 2017/2018 01/10/2017 15/03/2020 PUCCI GEPPINO (Presidente)
PIETRACAPRINA ANDREA ALBERTO (Membro Effettivo)
BILARDI GIANFRANCO (Supplente)
FANTOZZI CARLO (Supplente)
VANDIN FABIO (Supplente)
7 A.A. 2016/2017 01/10/2016 15/03/2018 PUCCI GEPPINO (Presidente)
PIETRACAPRINA ANDREA ALBERTO (Membro Effettivo)
FANTOZZI CARLO (Supplente)
VANDIN FABIO (Supplente)

Syllabus
Prerequisites: Introductory programming; Data structuires; Elements of cominatorics; Theory of computation.
Target skills and knowledge: Problem-solving abilities. Ability to face the solution of a computational problem with rigorous tools based on general algorithmic paradigms. Knowledge of widespread algorithmic primitives. Ability to prove the intractability of a problem.
Examination methods: - Two-part written exam: a) theory and b) problem solving

- (Discretionary) oral exam
Assessment criteria: The written test evaluates both acquaintance with the material covered during the lectures and the acquired capability to apply the techniques learned to new contexts.
Course unit contents: - Algorithmic paradigms: design and analysis

- Case studies

- Computational intractability
Planned learning activities and teaching methods: 1. Introduction and review: probelm, algorithm, cost model, pseudocode

2. Divide-and-conquer paradigm: general characteristics and techniques for the analysis
- Case studies:
- Integer Multiplication (Karatsuba)
- Matrix Multiplication (Strassen)
- Polynomial Multiplication (FFT)

3. Dynamic Programming paradigm: general characteristics; overlapping subproblems and solution techniques;
- Case studies:
- Matrix-chain multiplication;
- String problems: Longest Common Subsequence

4. Greedy paradigm: Problems solvable with the greedy approach and solution techniques;
- Case studies:
- Activity selection problem
- Huffman codes for data compression
Additional notes about suggested reading: As a complement to the texbook, the course web page http://www.dei.unipd.it/~geppo/DA2 offers supplemental material and solved exercises.
Textbooks (and optional supplementary readings)
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein.,, Introduction to Algorithms (Third Edition).. Boston: MIT Press, 2009. Cerca nel catalogo