General Information
Goals
At the end of the course, students should be able to:
- analyze the temporal and spatial complexity of algorithms;
- analyze the correctness of simple algorithms;
- know the main search and sorting algorithms and their complexity;
- understand the concept of abstract data type and know how to organize programs around this concept;
- know the fundamental data structures (and associated algorithms and respective complexity) used to efficiently implement common abstract data types in collection libraries;
- choose appropriate collections, data structures and algorithms to solve practical problems;
- write programs in C++ that implement and use the fundamental data structures and algorithms.
Syllabus
Basic concepts and techniques: space and time complexity of algorithms; abstract data types; analysis of algorithm correctness.
Arrays searching and sorting algorithms.
Linear data structures and their implementation: lists, stacks, and queues.
Hierarchical data structures and their implementation: binary trees; binary search trees; balanced binary trees. Applications.
Hash tables and related algorithms.
Priority queues and binary heaps.
Basic graph algorithm: types of graphs; representation; depth-first and breadth-first search. Applications: topological sorting; cycles; connectivity.