Courses Currently Offered in English

Course Version

Course Code:EADS
Version Number:2
Course Name:Algorithms & Data Structures
Credit Units:4
ECTS:6
Cost Units:30
Examination type (E-with exam):E
Grading threshold:5
Initiation semester:14Z
Person responsible:doc. dr inż. Roman Podraza
Description:ICT programme taught in English

Hours per week

Class typeHours
W2
C1
L1

Class types: W - lecture, C - tutorial, L - laboratory, P - project

Prerequisites

---

Prerequitise types: W - required, Z - recommended

Similar Courses

Course CodeNameDiscount CUDiscount ECTS
AISDIAlgorytmy i struktury danych (I)34
AISDTAlgorytmy i struktury danych (T)34

Last Course Instances

Semester codeInstance codeLecturerInstituteMax. number of students
17ZAdoc. dr inż. Roman PodrazaIN60

Thematic Classification

Class CodeClass name (in Polish)
ANGLAll Courses in English (A)

Conspectus

Summary (in Polish)

Wykład przedstawia podstawowy materiał pozwalający na zrozumienie struktur danych. Paradygmat projektowania (i programowania) obiektowego jest wykorzystywany do prezentacji abstrakcyjnych typów danych. Główny akcent jest położony na algorytmy wykorzystywane w operacjach na strukturach danych.

Lecture contents

Data Structures Overview (4h): data types, data type system, object, data structure, linear data structure, tree, graph, evaluating efficiency and the O-notation. Data Types: built-in types, collections, indexed collections.

Linear Data Types (4h): singly-linked list, doubly-linked list, ring, stack, queue, priority queue.

Sorting Algorithms(6h): simple sorting (Insertion Sort, Selection Sort, Bubble Sort), advanced sorting (Quicksort, Merge Sort, Heap Sort, Shell Sort), Straight Radix Sort, Radix Exchenge Sort, Shell Sort.

Searching Algorithms (2h): linear searching, binary searching, interpolation searching, Fibonacci searching, hashing strategy, hashing functions and hash search methods.

Trees (6h): Binary Search Tree, Binary Tree Sort, trees with arbitrary degree, AVL Trees, balancing, rotations, digital trees, B-trees, BB-trees.

Recursion (2h): Divide-and-Conquere strategy, Hanoi Towers.

Graphs (6h): directed and undirected graphs, paths, loops, reachibility, implementation methods, adjacency matrix, linked adjacency lists,graph traversals, Depth-First traversals and Breadth-First traversals, weighted and unweighted graphs, positive-weighted shortest path problem (Dijkstra's algorithm).

Tutorial contents

During exercises some typical problems of data structures are formulated , discussed and solved.

Laboratory contents

The laboratory consists of 3 simple tasks involving data structures. Classes employing single-linked lists, doubly-linked rings and binary search trees have to be designed, implemented and tested.

References
  1. M. A. Weiss: Data Structures and Problem Solving Using C++, Second Edition, Addison Wesley Longman Inc., 2000.
  2. T. Budd: Data Structures in C++ Using the Standard Template Library, Addison Wesley Longman Inc., 1997.
  3. S. Sengupta, C.Ph. Korobkin: C++, Object-Oriented Data Structures, Springer-Verlag, 1994.
Summary

The lecture presents fundamental material to the understanding of data structures. The object-oriented paradigm is used to demonstrate abstract data types. The main focus is put on algorithms handling operations of data structures.