General Information

Goals

At the end of the course, students should be able to:

  1. analyze the temporal and spatial complexity of algorithms;
  2. analyze the correctness of simple algorithms;
  3. know the main search and sorting algorithms and their complexity;
  4. understand the concept of abstract data type and know how to organize programs around this concept;
  5. know the fundamental data structures (and associated algorithms and respective complexity) used to efficiently implement common abstract data types in collection libraries;
  6. choose appropriate collections, data structures and algorithms to solve practical problems;
  7. 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.