﻿ .:CS240:. - Data Structures

# Course Contents

• Introduction
Basic concepts on algorithms and data structures, Proof techniques (proof by example or counterexample, proof by contradiction, mathematical induction), RAM model, Analysis of algorithms, Time complexity , Asymptotic analysis (in terms of Ο, Ω, Θ), Standard complexity classes, Mathematical background , Recursive algorithms and their analysis, Recursive relations, Experimental analysis. .
• Arrays
Operations on Arrays, Multi-dimensional Arrays, Symmetric and Triangular Arrays, Sparse Arrays.
• Basic data structures
Stacks (abstract data type, static and dynamic implementations, static implementation of multiple stacks, applications, complexity), stacks that support the multipop() operation, Amortized analysis.
Queues (abstract data type, static and dynamic implementation, complezity, applications).
Lists (unsorted and sorted lists, guard node, list traversals, zig-zag traversals, doubly linked lists, complexity, applications).
• Trees
Definition, types of trees and their properties, implementation, tree traversals, ordered trees.
• Sets & Dictionaries
Abstract data type, Implementation using linked lists, Move-to-front and Transpose heuristic, Binary search, Expected analysis, Binary Search Trees.
• Balanced Trees
AVL Trees, (2,3)-trees, Red-Black trees.
• Hashing
Chain hashing (separate and coalesced chaining), Open addressing strategies (linear probing, double hashing), Analysis of different strategies, Ordered hashing, Extendible hashing, Hash Functions, Universal Hashing.
• Priority queues
Abstract data type, Implementation using balanced binary search trees, Partially ordered trees, Implementation using Heaps.
• Sorting
InsertionSort, SelectionSort, MergeSort, HeapSort, QuickSort.
• Sets with special operations
Disjoint sets that support Union-find, Up-Trees.
• Graphs
Representation, implementation, traversal, applications.

# Program

Week Subject
1st Introduction - Basic concepts of algorithms and data structures
2nd Time complexity - Amortized cost, recursive algorithms and recursive relations - Arrays
3rd Basic data structures: Lists, stacks, queues
4th Lists
5th Trees
6th Trees
7th Balanced Trees: Implementation of dynamic dictionaries
8th Balanced Trees: Implementation of dynamic dictionaries
9th Hashing
10th Hashing
11th Priority queues
12th Sorting
13th Sets with special operations
14th Graphs - Techniques of algorithm design

# Attendance

Attendance is strongly recommended. Students are expected to know the material presented in class. Part of the material that will be taught is not covered by Greek books or it is presented in a different order.