====== Informatica 3 ======

__**[[teaching:info3:blog|News]]**__

The Informatica 3 course is held in three parallel sections (lecturers: G. Agosta, A. Campi, M. Matera).

Course contents and programs are identical across the sections, and the written exam is held on the same exam tests.

The course is roughly divided in two parts. In the first, we cover programming language design, while in the second we study the design of efficient algorithms and data structures.

The course is composed of 30 lecture hours and 20 hours of exercises.
[[http://compilergroup.elet.polimi.it/doku.php?id=people:pelosi:start|Gerardo Pelosi]] is the lecturer for the latter part.


===== Course program: Programming Language Design =====

  - Programming language: generalities and classification; history of programming languages 
  - Syntax and semantics
  - Data structures
  - Control structures
  - Modularization
  - Object-oriented languages
  - Interpreted languages

===== Course program: Algorithms and Data Structures =====

  - Computational Complexity
  - “Big Theta” and related notations
  - Abstract data types
  - Fundamentals of data structures and algorithms
  - Search and sort algorithms
  - Tree and their implementation
  - Tree visit and management algorithms
  - B-trees
  - Graphs, representation and management
  - Stacks, queues, and hash tables
  - Applications (seminars on cryptography and other applications)

===== Courseware =====
We adopt the following two books:

  * For the programming language design part: Ghezzi C., Jazayeri M.: //Programming language concepts//, 4th edition, John Wiley & Sons, 2002.
  * For the algorithm and data structures part: C.A.Shaffer: //A practical Introduction to data structures and algorithm analysis//.

The latter can be replaced by T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: //Introduction to Algorithms and Data Structures 2/ed//.

This second book is more of a reference text, and covers parts of algorithmics not explored in the course. It more closely fits the style of my version of the course, but has a more theoretical (and formal) approach to the topic.

You can also refer to the [[http://webspace.elet.polimi.it/lanzi/?page_id=14|slides]] adopted in the other sections, as well as to the  [[http://people.cs.vt.edu/~shaffer/Book/|material]] associated to Shaffer's book (or the same type of material for the Cormen //et al.// book) for the second part of the course.

Finally, the classic book by David Harel, "Algorithmics: The Spirit of Computing", gives a gentler introduction to the topics of the course.

=== Python ===
During lectures, algorithms will be presented in the [[http://www.python.org|Python]] programming language (the exercises will be run mostly in Java, to provide a more traditional implementation of the algorithms presented in the lectures).

You can (actually, you need, since Python is used in the exam as well) download and install the Python interpreter from the above link, both for Linux and for Windows.
If you use Linux, you already have a Python interpreter installed in your system.

To learn Python, you can rely on the following (freely available) books:
  * Mark Pilgrim, [[http://diveintopython.org/|Dive Into Python]]: a very complete survey of the language;
  * Allen B. Downey, Jeffrey Elkner and Chris Meyers [[http://www.openbookproject.net/thinkcs/python/english/|How to Think Like a Computer Scientist - Learning with Python]]: an introduction to programming, using Python; only useful if you have doubts on the basics of programming;
  * Bruce Eckel, [[http://www.mindview.net/Books/TIPython|Thinking in Python]]: //not// an introductory book; it's the Python version of the classic //Thinking in Java//.







===== Calendar =====

**Not yet updated, refer to the Italian version for the scheduled dates**

Here is the course calendar and notes. The notes for future lectures can change, since they come from the 2007/2008 edition. 

^ Topic                  ^  Date ^ Type ^
| [[teaching:info3:introduzione|Syntax and semantics]] |  29/9 | L |
| [[teaching:info3:semantica_operazionale_delle_chiamate_a_funzione|Function calls]] |  6/10 | L |
| [[teaching:info3:python|Python]] | 8/10 | L |
| [[http://home.dei.polimi.it/agosta/files/Esercizi_SIMPLESEM.pdf|Operational Semantics]] | 15/10 | E |
| [[teaching:info3:concorrenza_threading|Concurrency and Threading]] | 20/10 | L |
| [[teaching:info3:mutex_threading|Threading & Mutual Exclusion]]  | 22/10 | L |
| [[teaching:info3:liste_pile_e_code|Lists, stacks and queues]] | 27/10 | L |
| [[teaching:info3:iteratori_generatori_e_coroutine|Iterators, generators and coroutines]] | 29/10 | L |
| [[teaching:info3:complessita_computazionale|Computational complexity]] | 5/11 | L |
| {{teaching:thread_task.pdf|Parallelism and Threads}} | 10/11 | E |
| {{teaching:cuda.pdf|Seminar: parallel programming on NVIDIA GPUs}} | 10/11 | S |
| [[teaching:info3:Notazioni_O,_Ω_e_Θ|O, Ω e Θ notations]]   | 12/11 | L |
| [[teaching:info3:complessita_induzione_e_ricorrenze|Induction and recurrences]] | 24/11 | L |
| [[teaching:info3:algoritmi_di_ordinamento|Sorting algorithms]] |  26/11 | L |
| {{teaching:internal_sorting_array.pdf|Sorting algorithms}} | 1/12 | E |
| [[teaching:info3:alberi_binari|Binary Trees]], part 1 | 1/12 | L |
| [[teaching:info3:alberi_binari|Binary Trees]], part 2; [[teaching:info3:binary_search_tree_e_heap|Binary Search Trees]] | 3/12 | L |
| {{teaching:bt-bst-heap_cpp-java.pdf|Trees}} | 10/12 | E |
| [[teaching:info3:b-tree|B-Tree]], [[teaching:info3:binary_search_tree_e_heap|Heaps]] | 15/12 | L |
| [[teaching:info3:esercitazione_b-tree|B-Tree]] | 7/01 | E |
| [[teaching:info3:grafi|Graphs]] | 12/01 | L |
| {{teaching:graphs.pdf|Graphs}} | 14/01 | E |
| [[teaching:info3:hash|Hash & Huffman code]] | 19/01 | L |
| Seminar: Cryptographic algorithms | 19/01 | S |
| {{teaching:hashing.pdf|Hash}} e {{teaching:riepilogocomplessita.pdf|Exercises on Complexity and Induction}} | 21/01 | E |
| Pre-exam exercises, part 1 | 26/01 | E |
| Pre-exam exercises, part 2 | 28/01 | E |