ALGORITHMS AND DATA STRUCTURES AND LAB
The course is an introduction to algorithms and data structures, that are fundamental for a computer scientist. The course provide general methodologies and tools for a correct algorithm design and to estimate its computational complexity. The course also provides basics of automata and languages. Finally, the course contains an introduction to C++ language, that is user for the software implementation of the algorithms in Laboratory lessons, that are a relevant part of the course.
Knowledge and Understanding capability: The student must show to know and to understand the foundations and data structures, paying particular attention to their computational complexity. Moreover, the student must show to know C++ programming language and be familiar to basics of automata and languages.
Ability of applying knowledge and understanding: The student must show to use his acquired knowledge for designing and implementing effectively the algorithm and the programming techniques, studied in the course. Moreover, he will have to be able to estimate correctly the computational complexity, both spatial and temporal, of implemented algorithms.
Independent Judgement: The student must be able to evaluate independently the performance and effectiveness of an algorithm.
Communication Skills: Communication Skills of the student will be developed in the following way.
The student will have to write a technical report that will describe the exam project. Besides, he should be able to describe and to discuss orally effectively his project.
Learning Ability: The student must be able to do self-learning, deepening subjects of algorithms and data structures, using library books or other resources available in the WEB.
The knowledge and the know-how learnt in the courses of Mathematics I, Programming I and Laboratory of Programming I, Programming II and Laboratory of Programming II are required,
Algorithms and Data Structure and Laboratory are required.
Introduction to the Course.
- Definition of Algorithm.
- Computational Complexity of an Algorithm.
- Asymptothic Notations.
– Recurrences. Methods for the recurrence solution: Iterative method, Substitution Method, Master Theorem of Recurrences.
- Insertion Sort Sorting Algorithm.
- Divide and Conquer Paradigm. Examples: Merge Sort, Quicksort, Randomized Quicksort
- Sorting Algorithms. Counting Sort, Radix Sort, Bucket Sort. Lower Bound of Computational complexity for Comparison-based.
- Dynamic Programming Paradigm. Examples: Optimal Parenthesization of a Matrix Chain, Mounting Chain Problem, Longest Common Sequence, Editing Distance. Binary Knapsack Problem.
- Greedy Programming Paradigm. Examples: Activity Selection, Shortest Job First, Continuous Knapsack Problem, Huffman Coding
- Backtracking Programming Paradigm. 8 Queen Problem
-Branch and Bound Programming Paradigm.
- Binary Trees. Complete Binary Trees. Heap. Heapsort. Priority Queue.
- Binary Search Trees. RED Black Trees.
- Graphs. Graph Visit Algorithms. Minimum Spanning Tree. Kruskal and Prim Algorithms. Shortest Path Problem in Directed Graphs. Algorithms of Dijkstra and Bellmann-Ford.
- Hash Tables.
- Introduction to Automata and Languages. Finite State Automata . Languages. Regular Grammars.
- P and NP Problems. NP-complete Problems. Examples of . NP-complete Problems.
- Turing Machine.
-Introduction to the language C++.
- Multiple Inheritance in C++. Diamond Paradox and Nixon Paradox.
- Standard Template Library (STL). Containers: Vector, List, Map. Iterators, Algorithms.
- I/O su file: Ifstream, Ofstream, Fstream Libraries.
- Template Classes and Functions
- Implementation of the Algorithms and Data structures studied.
T. Cormen, C. Leiserson, R. Rivest, C: Stein: “Introduction to Algorithms”, 3rd edition, Mc Graw Hill, 2010.
B. Stroustrup: “The C++ Programming Language”, Pearson, 2013.
The slides of all lessons are available in e-learning platform.
The aim of verification procedure is to assess the achievement level of educational targets fixed in advance.
The verification procedure is described in the e-learning platform of Department of Science and Technology.
The verification procedure consists in a written and in an oral part. The written part consists in a written test, performed in classroom, and a laboratory software project, implemented, in C++, as homework, that regards the writing of a topic, chosen by the student among a list of five available subjects.
The oral part is partly devoted to the discussion of the exam project and, partly to the assessment of
the acquisition of the course notions. The written text, the project and the oral part
concur in an equal manner to the formulation of final mark of the exam.
During the course, there will be two mid-term tests that, if both successful, replace the written text.