Politecnico di Torino
Politecnico di Torino
   
Login  
it
Politecnico di Torino
Academic Year 2011/12
02MNOOA, 02MNONZ
Algorithms and Programming
1st degree and Bachelor-level of the Bologna process in Computer Engineering - Torino
1st degree and Bachelor-level of the Bologna process in Telecommunications Engineering - Torino
Teacher Status SSD Les Ex Lab Tut Years teaching
Camurati Paolo Enrico ORARIO RICEVIMENTO PO ING-INF/05 60 20 20 80 10
SSD CFU Activities Area context
ING-INF/05 10 B - Caratterizzanti Ingegneria informatica
Subject fundamentals
This course is characterizing for the Bachelor Degree in Computer Engineering, and it is held at the first and second semester of the second year. The course deepens the knowledge and skills for advanced programming, considered as a problem solving tool.
The main goal is to guide the student from analysis to program design skills. Algorithmic solutions to 'classical' problems are introduced, together with their theoretical foundations, and the implementations in C language. The student has the opportunity to analyze practical examples, describing solutions to complex problems, and the related algorithmic paradigms. Most of the knowledge and programming skills are experienced through practical exercises and laboratories.
Expected learning outcomes
- Knowledge of techniques for memory allocation and usage of pointer
- Programming skills in C language, using pointers and dynamic data structures
- Knowledge og basic notions about complexity analysis
- Knowledge of sorting algorithms
- Skills to evaluate algorithm complexity and improve efficiency in terms of execution time and/or memory allocation
- Knowledge of complex data structures and ADTs (linked lists, queues, heaps, trees, hash tables and graphs) and related algorithms
- Knowledge of simple strategies for mudular programs in C
- Knowledge of paradigms of recursive and programming, greedy approaches, dynamic programming and memoization
- Skills to exploit tools for program development
- Skills of problem solving, based on design of data structures and algorithms
- Skills on recursive programming techniques
Prerequisites / Assumed knowledge
- Knowledge of elementary computer systems (Von Neumann model) architecture
- Knowledge of C language syntax, basic data types and constructs
- Basic programming skill in C language, using conditional and iterative constructs, scalar and aggregate data, standard I/O, text files and functions
- Skills on elementary (algorithmic) problem solving
Contents
- Algorithm analysis (8 h)
- Asymptotic analysis and worst-case complexity; 0, Q, W notations; recurrence equation
- Sorting algorithms: quadratic sorting (selection sort, insertion sort), linear sorting (counting sort) linearithmic sorting (quicksort, heapsort, mergesort);

- Static and dynamic data structures and their implementation in C (6 h)
- Memory representation/allocation of data and runtime memory management
- Pointers (references to objects);
- Static memory al location, stack and dynamic al location;
- Linked data structures;
- Strategies for data structure choice and design

- Modular programs and modular implementation of algorithms and data structures (4 h)
- The modular model implementation-interface-client
- C language implementation of a program based on multiple source and header files
- Introduction to program development tools: e.g. make, gdb, cvs, '

- Recursion and recursive programs (4 h)
- Recursive reasoning
- Recursive mathematical functions
- Simple recursive procedures
- backtrack and implementation of recursion

- Discrete mathematics (2 h)
- Sets, relations, functions
- Graphs and trees

- Abstract objects, collections of objects and ADTs (6 h)
- Examples of modular composite data structures: e.g. arrays of lists, multi-lists, '
- Linked lists, stack, FIFO, generalized queues, priority queues, heaps

- Algorithmic paradigms (6 h)
- Divide and conquer
- The greedy paradigm
- Dynamic programming and recursion with memoization

- Problem solving (4 h)
- Data structure and algorithm analysis and design strategies
- Research and optimization problems

- Data structures for symbol tables (6 h)
- Binary Search trees
- Bilance trees (RB-trees)
- B-trees
- Hash tables

- Graph algorithms (8 h)
- Depth-first and breadth-first visits
- Applications of visits
- Shortest paths
- Minimum spanning trees
Delivery modes
- Practice (22 h)
- Pointers and dynamic memory allocation
- Modular programs and program development tools
- Recursive programming
- Problem solving and algorithmic paradigms
- Application examples from gaming theory: 8 queens, Hanoi tower, ruler, labyrinth
- Data structures and ADTs

- Laboratory practice (24 h)
- Pointers and dynamic memory al location: dynamic arrays and matrices, linked lists
- Modular programs and progeam development tools: make, gdb, cvs
- Recursive programming with backtrack
- Problem solving and algorithmic paradigms
- Data structuresm ADTs and symbol tables: stack and FIFO, BSTs, hash tables
- Graph algorithms
Texts, readings, handouts and other learning resources

R. Sedgewick, 'Algoritmi in C', III edizione, Addison-Wesley

T.H.Cormen, C.E.Leiserson, R.L.Rivest, 'Introduction to Algorithms', MC-Graw Hill

Deitel & Deitel,' Corso completo di programmazione C', Apogeo

Programma definitivo per l'A.A.2011/12
Back



© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)
Contatti