


Politecnico di Torino  
Academic Year 2016/17  
03MNOOA Algorithms and Programming 

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





Subject fundamentals
The course allows the student to acquire adequate knowledge and skills in algorithms, data structures and their implementation in C to solve complex problems. The student should gradually evolve from more analytic to more designoriented skills. Algorithmic solutions to 'classical' problems are introduced, together with their theoretical foundations, and the implementations in C language. Advanced aspects of C are considered, like pointers, dynamic memory allocation, modularity and Abstract Data Type implementation. The student has the opportunity to analyze practical examples, describing solutions to complex problems, and the related algorithmic paradigms. Knowledge and programming skills are applied during lab sessions.

Expected learning outcomes
• Knowledge of techniques for memory allocation and use of pointers
• Programming skills in C language, using pointers and dynamic data structures • Knowledge of basic complexity analysis • Knowledge of sorting algorithms • Ability to evaluate algorithm complexity and improve efficiency in terms of execution time and/or memory use • Knowledge of complex data structures and ADTs (linked lists, queues, stacks, heaps, trees, hash tables and graphs) and related algorithms • Knowledge of simple strategies for modular programming in C • Knowledge of recursive and greedy problemsolving paradigms • Skills in problem solving, based on design of data structures and algorithms • Skills in recursive programming techniques • Skills to exploit tools for program development 
Prerequisites / Assumed knowledge
Due to the incremental nature of the course with respect to the first year class "Computer Science", there are several strict prerequisites in terms of programming skills and programming language knowledge, with particular emphasis on the following topics:
• Elementary computer systems architecture (Von Neumann model) • Syntax of C, basic data types and constructs • Basic programming skills in C, using conditional and iterative constructs, scalar and aggregate data, standard I/O, text files and functions • Skills in elementary (algorithmic) problem solving 
Contents
• Review of basic language construct and basic problem solving (11h)
• Algorithm analysis (5h) o Asymptotic worstcase complexity analysis o O, , notations o Recurrence equations • Sorting algorithms (8h) o Iterative sorting (bubble sort, selection sort, insertion sort, shell sort, counting sort) o Recursive sorting (mergesort, quicksort, heapsort) • Static and dynamic data structures and their implementation in C (15h) o Data representation in memory and runtime memory management o Pointers (or references to objects) o Static, on stack and dynamic memory allocation o Linked structures o Strategies for data structure selection • Modularity and modular implementation of algorithms and data structures (10h) o The implementationinterfaceclient model o Implementation in C of programs with multiple source and header files o Basic use of development and debug tools, like make, gdb, cvs • Recursion and recursive programs (10h) o The notion of recursion o Mathematical recursive functions o Simple recursive procedures o Backtrack and implementation of recursion • Discrete mathematics (4h) o Sets, relations, functions o Lists, graphs and trees • Abstract objects, collections of objects and ADTs (10h) o Modular examples of composed structures, like arrays of lists and multilists o Linked lists, stacks, FIFO queues, generalized queues, priority queues, heaps • Algorithmic paradigms (8h) o Divide and conquer o Greedy • Problem solving (14h) o Analysis and definition of strategies for data structures and algorithms o Search and optimization problems o Techniques to explore the state space based on combinatorics • Data structures for symbol tables (10h) o Binary search trees o Hash tables • Graph theory (15h) o Graph representation o Depthfirst and breadthfirst search and their applications o Shortest paths o Minimum spanning trees. 
Delivery modes
Lectures (80h) include practice lessons. Lectures and lab sessions (20h) are extended with 20 additional hours in class or lab to consolidate what the student has learned. Selected lab sessions may be ranked and contribute a bonus (max 2/30).

Texts, readings, handouts and other learning resources
Textbooks (in Italian):
• Deitel & Deitel, ‘Corso completo di programmazione C’, Apogeo, 2010 • P. Camurati, S. Quer, ‘Algoritmi e Programmazione: richiami di teoria con esercizi svolti’, CLUT, III edizione, 2016 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Dal problema al programma: introduzione al problemsolving in linguaggio C’, Apogeo, II edizione, 2016 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Ricorsione e problemsolving: strategie algoritmiche in linguaggio C’, Apogeo, 2015 • G. Cabodi, P. Camurati, P. Pasini, D. Patti, D. Vendraminetto, ‘Puntatori e strutture dati dinamiche: allocazione della memoria e modularità in linguaggio C’, Apogeo, 2016 Other suggested readings: • R. Sedgewick, ‘Algoritmi in C’, IV edizione, Pearson, 2015 (in Italian) • T.H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein, ‘Introduzione agli Algoritmi e alle Strutture Dati’, III edizione, McGraw Hill, 2010 (in Italian) • P. Crescenzi, G. Gambosi, R. Grossi, ‘Strutture di dati e algoritmi’, Pearson AddisonWesley 2006 (in Italian) • R. Sedgewick, K. Wayne, ‘Algorithms Part I & II’, www.coursera.org (in English) • A. Bertossi, A. Montresor, ‘Algoritmi e strutture di dati’, Città Studi edizioni, 2014 (in Italian) Teaching material available on the Web: • Lecture transparencies • Exercises and solutions • Videolectures 
Assessment and grading criteria
The exam consists in:
• a written part (maximum duration 2h30) • an oral exam. The written part includes: • exercises/questions on theoretical aspects, maximum 12 points, maximum duration 50min • a programming part, maximum duration 1h40, available in 2 alternative modes: • design and development of a program in C to solve a problem, the emphasis being on problemsolving and design skills (max 18 points) • guided development of the solution to a problem, with less emphasis on design and problemsolving skills and more on the ability to use advanced C features (pointers, dynamic allocation, recursion) and on the knowledge of basic data structures and algorithms (max 12 points). Both modes require the same approach to the subject. Material available during the written part: • C manual: KernighanRitchie, Deitel & Deitel, or similar • Header files for standard functions/ADTs unless explicitly forbidden • NO other books, notes, transparencies etc. • NO electronic communication tools (cell phones, tablets, laptops, etc.) Each student must : • make a copy of the program at the end of the written part (using carbon copy paper, cell phones, cameras etc) • verify the correctness of the program • upload on the course webpage within 3 working days: a report (max 3 pages) describing the solution (data structures, algorithm, etc) and a copy of the working program, showing the changes with respect to the version handed in for ranking. In case the above material is not uploaded, the written exam will not be ranked. Students whose mark in the written part is 15/30 are entitled to sit for the oral exam. The oral exam consists in: • questions on all the topics of the course, the goal being to rank the grade of theoretical knowldege • programs in C to evaluate skills related to the implementation and manipulation of data structures by means of advanced C programming constructs and to the implementation of variants of standard algorithms • questions on uploaded lab exercises. The final mark integrates partial results and is not a mere average. Lab bonusses are not added to, rather they are included in the final mark. 
