


Politecnico di Torino  
Academic Year 2011/12  
02MNOOA, 02MNONZ Algorithms and Programming 

1st degree and Bachelorlevel of the Bologna process in Computer Engineering  Torino 1st degree and Bachelorlevel of the Bologna process in Telecommunications Engineering  Torino 





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 worstcase 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 implementationinterfaceclient  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, multilists, '  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 (RBtrees)  Btrees  Hash tables  Graph algorithms (8 h)  Depthfirst and breadthfirst 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, AddisonWesley T.H.Cormen, C.E.Leiserson, R.L.Rivest, 'Introduction to Algorithms', MCGraw Hill Deitel & Deitel,' Corso completo di programmazione C', Apogeo 
