A. Juozapavicius: "Data Structures and Algorithms"

Catalog description:

Review of abstract data types (ADT) in applications, analysis and efficiency of algorithms, algorithmic techniques, sorting and searching, range searching and multidimensional searching, spatial and spatio-temporal access methods, concept-based indexing and retrieval of multimedia data.

Manuscripts of some topics in pdf or word files:

• Outline of data structures and algorithms, abstract data types, models of memory, in pdf format
• Trees, balancing of search trees, in pdf format
• Heaps and priority queues, Huffman trees, in pdf format
• Sorting (including external) algorithms, in pdf  format
• Hashing and radix searching algorithms, in pdf format
• String matching algorithms, and algorithmic analysis, in pdf format
• Quadtrees and other multidimensional data structures, in pdf format

Current textbooks:

• Robert Sedgewick. Algorithms in C, Parts 1-4 Addison-Wesley, 1999
• Gregory L. Heileman, Data Structures, Algorithms, and Object-Oriented Programming. The McGraw-Hill Companies, Inc., New York, etc., 1996.
  
• Algimantas Juozapavièius. Data Structures and Algorithms, Vilnius University Press, 1997

Additional textbooks:

• L.Ammeraal, Algorithms and Data Structures in C++. John Wiley & Sons, Chichester, England, 1996.
  
• Th. Cormen, Ch. Leiserson, R. Rivest, Introduction to Algorithms. The MIT Press, Cambridge, MA, 1990;
  
• S. K. Chang, E. Jungert, Symbolic Projection for Image Information Retrieval and Spatial Reasoning. Academic Press Limited, London, 1996.
  

Goals:

The fundamental methods for designing good algorithms in both theory and practice are studied, together with the methods for analyzing time and memory demands of algorithms. The student should learn important algorithms of data access, especially of complicated cases, like multidimensional and spatial data, spatio-temporal data.

The content of the course:

• ADT specification, pseudocode;
• models of computer memory, main memory, secondary memory, ternary memory;
• models of memory in VLDB, multimedia DB, GIS;
• importance of data structures, their role and function in applications like VLDB, multimedia, GIS, image processing, computer vision;
• discussion and analysis of suitable applications, exercises.

• glossary, definitions, properties;
• representation of trees;
• traversing of trees, recursion, balancing of trees;
• priority queues, heap data structure;
• algorithms on heaps, heapsort;
• applications and exercises.

• analysis of algorithms, classification;
• computational complexity, worst-case, average-case, asymptotic notations;
• sums, recurrences, sets, counting;
• discussions, problems and exercises.

• running time and memory usage;
• algorithms of exponential time;
• algorithms of polynomial and superpolynomial time;
• problems and exercises.

• brute-force algorithms, examples;
• divide-and-conquer algorithms, examples;
• dynamic programming, examples;
• greedy algorithms, examples;
• randomized and similar algorithms, examples;
• discussions, comparisons, problems, exercises.

• sequential search, binary and binary tree search;
• hashing and extendible hashing;
• search by heaps and priority queues;
• problems and exercises.

• meldable priority queues;
• nonamortized structures: binary, leftist, binomial heaps;
• skew, lazy binomial, Fibonacci heaps;
• approximation algorithms;
• project, problems, exercises.

• range searching, tries;
• multidimensional searching, quadtrees;
• B-trees and BV-trees;
• project, problems, exercises.

• overview, grid-files;
• hashing-based structures;
• spatial data, spatio-temporal data, complex objects;
• problems, exercises.