Algorithms and Data Structures. Luciano Bononi

Course aims: The aim of the course is to provide students with basic knowledge about the design, implementation and analysis of correct and efficient algorithms and data structures supporting the modeling and analysis of complex systems. Specifically, the course will introduce to basic data structure models and design concepts, and to the relationship with the design of scalable and efficient algorithms able to exploit the opportunely defined data structures. The aim is to introduce the students to the common issues, techniques, skills and methodologies allowing for the realization of complex computation platforms for massive and complex data structures, under the requirements of a reduced space (memory) and time (computation) complexity viewpoint. The exploration of parallel/distributed computation and related bottlenecks (communication and synchronization) will be introduced. At the end of the course, the students will have basic knowledge on algorithms and data structures. In particular, students will be able to: - design correct and efficient algorithm for common computational tasks - analyze existing algorithms and data structures, and possibly optimize the design - design and analyze new algorithms and data structures for specific tasks and computation architectures.
Course contents:   Introduction to algorithms and basic data structures: definitions, algorithms, simple data structures. Lists, arrays, simple operations, examples, implementation. Complex data structures, computation efficiency and data structures. Stacks and queues (definition, examples, implementation). Trees, visit algorithms of a tree and tree operations. Sets, dictionaries and hash tables, their operations and implementation concepts. Graphs, visit algorithms for graphs, operations and implementation concepts. Exercices and tests ( graphs and trees, priority queues and heaps).
Algorithms. Divide and conquer. Recursion. Greedy techniques (knapsack problem, radix sorting problem, Huffman codes). Binary search. Sorting algorithms. Complexity analysis of algorithms. Exercises and tests.

Readings/Bibliography:
Electronic slides will be provided.
Suggested readings (not to be necessarily purchased).
Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 2001.
Donald E. Knuth. The Art of Computer Programming, Volumes 1-3. Addison-Wesley Professional, 1998.
S.B. Kishor Data Structures, Edition 3. Das Ganu Prakashan, Nagpur, 2008.

Teaching methods: Class lessons. Live exercises in class. Homeworks.
Assessment methods:
Written and oral examination.
Facultative project.

Teaching tools: Electronic slides and projector. Personal computer. Black board.