PROGRAMMING MOD. B
No requirements
• The main aim of the course consists in giving the basis of data structures theory and algorithms.
The intended scope of the course is also to introduce to the main subjects related to the theory of complexity.
Besides an outline of java programming is given.
• Contents and program of the course
Module A
Introduction to java programming:
- Variables, constants and type of elementary data.
- Assignment and composite statement.
- Basics of Input/output.
- Expressions and operators.
- Control Structures: selection and cycles.
- Class and methods.
- Array.
- Introduction to recursion.
Module B
Useful Mathematical materials for a preliminary
approach to complexity theory.
Recurrences and Master Theorem.
Sorting Algorithms:
- Setting the problem. Lower bound in time complexity.
- Insertion sort – worst case and average case.
- Merge sort - worst case and average case.
- Heap sort - worst case and average case.
- Quick sort - worst case and average case.
- Random Quick sort.
Algorithms for sorting in linear time.
Elementary data structures: Stacks, queues and trees.
• Types of teaching activities: Usual classes.
• Text books and useful materials
Module A
-Tutorial: available on the official web-site.
MIT Press.
-C. Thomas Wu: "Java. Fondamenti di Programmazione.". McGraw-Hill.
Module B
- Introduction To Algorithms. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein.
• Exams verification:
Final exam is composed of an oral and a practice test. You are admitted to the oral test provide that your score in practice examination is more than 15.