Tecniche di Programmazione

Prof. Giuseppe Persiano


Objectives
Tecniche di Programmazione is a class for the Laurea Magistrale in Ingegneria Informatica. We will advance our knowledge of algorithm design, data structures and programming. We will use C++.

Lectures

  1. The dictionary data structure

    1. Binary search trees: chapters 12.1, 12.2, 12.3 of [CLRS].
      Suggested exercises: 12.1-1, 12.1-5, 12.2-1, 12.2-9, 12.3-3, 12.3-5.
    2. Red-Black trees: chapters 13.1, 13.2, 13.3, 13.4 of [CLRS].
      Suggested exercises: 13.1-1, 13.1-2, 13.2-2, 13-2.4, 13.3-2
      Suggested problems: Problem 13-1: Persistent dynamic sets; Problem 13-2: Join operations on red-black trees.

    3. Augmenting Data Structures: chapters 14.1, 14.3 of [CLRS].
      Suggested exercises: 14.1-5, 14-3.6.
  2. Data structures for strings

    1. Digital tries, tries, Patricia trees, Suffix trees: chapter 17 of Algorithms in C++ by R. Sedgewick.
      This paper describes a linear algorithm for constructing the suffix tree of a string.

  3. Dynamic programming: chapters 15.2, 15.3, 15.4 of [CLRS]
    Suggested exercises: 15.2-1, 15.2-2, 15.4-1, 15.4-2, 15.4-3, 15.4-4, 15.4-5.
    Suggested problems: 15-4, 15-6, 15-7.

  4. Greedy algorithms: chapters 16.1, 16.2, 16.3 of [CLRS]

  5. All-pairs shortes paths: chapters 24.2, 25.1, 25.2 of [CLRS]
    Suggested exercises: 24.2-4, 25.1-3, 25.1-7, 25.2-4,

  6. Sorting in linear time: chapters 8.2, 8.3, 8.4 of [CLRS]
    Suggested exercises: 8.2-1, 8.2-3, 8.2-4, 8.3-1, 8.3-4, 8.4-2, 8.4-4,

 

Code and Assignments

  1. Dictionary ADT implemented in C using BST.
    Release 0: pure C.
    Code available here.
  2. Dictionary ADT implemented in C using BST.
    Release 1: This version takes one (small) step towards object-oriented programming by making the BST code independent from the actual data.
    Code available here.
  3. Assignment 1:
    Write code for a C function that constructs a BST from the preorder visit of the tree. Your function must have the following prototype:
        tree *reconstructFromPreorder(int *visit,int len)
    where visit points to the start of the array of integers that contains the visit and len denotes the length of the visit. You must provide the c source file preorder.c and the header file preorder.h.
    Here you can find a typical program that uses your function. Make sure your code is compatible with the code from Release 0.
    Submit the zip file containing a directory with the header file and the C source code by following this. The name of directory is the last name of the student followed by the first name. Please remove all spaces and apostrophes from your first and family name and use only small letters for the name of the directory.
    Deadline: October 20th, noon.
    Solution: available here
  4. Dictionary ADT implemented as a C++ Class
    Release 2.0: This version designs a class that implements the dictionary ATD using BST. Code available here.
  5. Dictionary ADT implemented as a C++ Template Class
    Release 3: This version designs a template class which can be used for any class that defines the comparison operators. Code available here.
  6. Dictionary ADT implemented as C++ Class
    Release 2.1: This version makes a distinction has two distinct classes: one for the BST and one for the node of a BST. This version provides a constructor of the tree from the preorder visit. Code available here.

  7. Dictionary ADT implemented as C++ Class with RB trees.
    Release 4.0: This version implements the dictionary using RB trees. Code available here.

  8. Release 4.1: 4.0 + operator overloading and examples for reference vs. pointer. Code available here.

  9. Assignment 2:
    The assignment;
    A file using your class (new);
    The expected output (new);
    To upload your solution. Submit a zip file containing a directory with one header file called assignment.h. The name of the directory is the last name of the student followed by his/her first name. Please remove all spaces and apostrophes from your first and family name and use only small letters for the name of the directory.
    Solutions

  10. Assignment 3:
    due December 2nd, 2015. Follow this link.

  11. A general class for Dynamic Programming
    Code available here.

  12. Assignment 4:
    due December 23rd, 2015. Follow this link.

Fun