Lists and sorting

Overview

Goals

Goal of this activity is the implementation of doubly linked lists and sorting algorithms in programming language C. Moreover, the comparative measurement of the performance of the algorithms.

Learning Objectives

Upon completion of the course, students will have acquired knowledge of the implementation of a complex program in C and they will have a thorough understanding of the concepts underlying the course. The course introduces to the basic concepts of data structuring and efficient data storage and manipulation. Aims at introducing to the right usage and application of fundamentals data structures and sorting algorithms. The lectures are based on reading material and applets that demonstrate and explain the use of the various data structure and sorting algorithms. Upon successful completion of this course, the student will be able to: know the usage of a variety of data structures and sorting algorithms analyze and understand the characteristics and the performance of data structures and sorting algorithms compare and categorize a variety of data structures and sorting algorithms based on their functionality and performance choose the appropriate data structures and sorting algorithms based on criteria related to functionality, time/space complexity and hardware requirements.

Context

The course provides the students an introduction to the basic data structures, sorting and searching techniques. The following topics are covered: Review of asymptotic estimations, worst case and average case performance; Basic Data Structures like Arrays, Lists, Stacks, FIFOs, Dequeues, Static and Dynamic Trees and their Traversals; Binary Search and Introduction and Αnalysis of Comparison-based sorting algorithms (i.e., Insertion Sort, Selection Sort, Bubble Sort, Shaker Sort, Quick sort, Heap Sort, Merge Sort) and Distribution-based Sorting Algorithms (i.e., Bucket Sort, LSD and MSDRadix Sort); Selection and Order Statistics; Ordered Dictionaries, like Simple, Balanced Search Trees (AVL Trees, (a, b)-Trees, Red-Black Trees) and Digital Trees (Trie, PATRICIA Trees); Union-Find in Disjoint Sets; Introduction to Hashing and Unordered Dictionaries like Hashing with Chaining, Hashing with Open Addressing, Rehashing,and Extendible Hashing; Skip Trees, Splay Trees, Treaps; Heaps (Binomial, Fibonacci).