Course information

The course provides a comprehensive study of data structures and their algorithms. Topics include: Introduction: Concepts of data structures and algorithms, correctness of algorithms, asymptotic analysis, and Abstract Data Type (ADT). Sorting Algorithms: Binary search. Comparative sorting algorithms (insertion, selection, bubble, merge, quick sort). Lower bounds for comparative sorting. Algorithms for sorting through distribution (bucket sort, bin sort, radix sort, counting sort). Simple Data Structures: Arrays. Connected structures: Lists (simply/circularly/doubly linked), positional lists, ArrayLists. Simple Abstract Data Types (ADT): Stack (LIFO), queue (FIFO), circular queue. The Priority queue ADT: Heap structures (tree implementation, vector implementation, heapify). Adaptable priority queue. The ADT Map (or Symbol table): Implementations with lists: Hashing (chaining, linear probing, quadratic probing, double hashing). The ADT Sorted Map: Implementation with ArrayList. Skip-list. The ADT Set. The ADT Dictionary (dictionary/multiset/bag). Search Trees: Binary search trees. Leaf-oriented search trees: AVL-trees, B-trees, and databases. ATD implementations for SortedMap, AdaptablePriorityQueue. The ADT disjoint sets.