Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate

SUBJECT

Code
Subject
MIE0001 Data Structures and Algorithms
Section
Semester
Hours: C+S+L
Category
Type
Mathematics
2
2+1+0
fundamental
compulsory
Computer Science
2
2+1+0
fundamental
compulsory
Mathematics and Computer Science
2
2+1+0
fundamental
compulsory
Information engineering
2
2+1+0
fundamental
compulsory
Teaching Staff in Charge
Assoc.Prof. CZIBULA Gabriela, Ph.D.,  gabiscs.ubbcluj.ro
Lect. CIOBAN Vasile, Ph.D.,  vciobancs.ubbcluj.ro
Lect. TRÎMBITAS Gabriela, Ph.D.,  gabitrcs.ubbcluj.ro
Lect. IONESCU Clara, Ph.D.,  claracs.ubbcluj.ro
Assoc.Prof. MOTOGNA Simona Claudia, Ph.D.,  motognacs.ubbcluj.ro
Aims
- to study the concept of abstract data types (ADT) and the most used ADTs in application development;
- to study the data structures used to implement these ADTs (arrays, linked lists, binary trees, hashing tables, etc.);
- to create the ability to design and build applications starting from abstract data types;
- to create the ability to work with data stored different data structures: arrays, linked lists, binary trees, hashing tables, stacks, queues, graphs, trees;
- to create the ability to compare the cost of static and dynamic allocation for different data structures;
- to create the ability to choose the appropriate structure for a certain application;
- to create the ability to design and implement algorithms that use these data structures;
- to improve the ability to evaluate the complexity of the algorithms.
Content
1. Introduction. Data Structures. Static, semistatic, and dynamic structures. [1, ch. 1, 2] (1 lecture - S1 + 1 seminar - S1 / S2)
- Abstractness and data encapsulation
- Dynamic sets
- Complexity

2. Data Types: domain, operations and data representation [6, ch. 5] (1 lecture - S2)
- Abstract Data Types: domain and operations
- Requirements, interface, implementation (implementations)
- Abstract Data Types Design

Array
- Description, properties
- Strings, substrings, subsequences, matrix
- Dynamic Arrays: operations: insertion / deletion, sequential and binary search
- Merging
- Sorting: mergesort, ranksort, radixsort, bucketsort etc.

3. ADT Collection [1, ch. 5] (1 lecture - S3)
- Related concepts
- Related applications
- Specifications and design
- Representations using arrays, linked lists, hash tables, and binary trees

ADT Set
- Related concepts
- Related applications
- Specifications and design
- Representations using arrays, linked lists, hash tables, and binary trees

4. ADT Map [4, ch. 6] (1 lecture - S4+ 1 seminar - S3 / S4)
- Related concepts
- Related applications
- Specifications and design
- Representations using arrays, linked lists, hash tables, and binary trees
- Sorted map

5. ADT List [1, ch. 11] (2 lectures - S5, S6+ 2 seminars - S5, S7 / S6, S8)
- Related concepts
- Related applications
- Specifications and design
- Representations using arrays and linked lists
- Sorted Lists

Linked List
- Description, properties
- Singly, doubly and circular linked lists - dynamic allocation
- Linkage on arrays
- Operations: insertion / deletion, searching, traversal

6. ADT Stack [1, ch. 11] (1 lecture - S7)
- Related concepts
- Related applications
- Specifications and design
- Representations using arrays and linked lists

7. ADT Queue [1, ch. 11] (1 lecture - S7)
- Related concepts
- Related applications
- Specifications and design
- Representations using arrays and linked lists

8. ADT Priority Queue [1, ch. 7] (1 lecture - S8+ 1 seminar - S9 / S10)
- Related concepts
- Related applications
- Specifications and design
- Representations using arrays and linked lists

9. Hash-table [1, ch. 12] (1 lecture - S9, S10+ 1 seminar - S11 / S12)
- Direct Addressing
- Description, properties
- Open and Closed Hash-tables
- Collisions resolution: chaining, interleaved lists and open addressing
- Operations: searching, insertion / deletion

10. ADT Tree [1, ch. 13] (1 lecture - S11 + 1 seminar - S13 / S14)
- Related concepts
- Related applications
- Specifications and design
- Linked Representation
- ATD Tree with different properties

Binary Tree
- Description, properties
- Search Binary Tree
- Operations: searching, insertion / deletion, traversal

11. Heaps [1, ch. 7] (1 lecture - S12)
- The structure presentation
- Binary Heap
- Priority Queue representation using a heap
- HeapSort

12. Balanced Search Trees [1, ch. 14; 3, Lecture 9] (1 curs - S13)
- AVL Trees
- Red-Black Trees

13. ADT Graph [1, ch. 23] (1 curs - S14)
- Related concepts
- ADT Graph
- Related applications

References
1. CORMEN, THOMAS H. - LEISERSON, CHARLES - RIVEST, RONALD R.: Introducere în algoritmi. Cluj-Napoca: Editura Computer Libris Agora, 2000.
2. HOROWITZ, E.: Fundamentals of Data Structures in C++. Computer Science Press, 1995.
3. MOUNT, DAVID M.: Data Structures. University of Maryland, 1993.
4. AMBSBURY, WAYNE: Data Structures. From Arrays to Priority Queues, 1993.
5. WIRTH, N.: Algorithms + Data Structures = Programs. Prentice- Hall Inc., 1976.
6. STANDISH, T.A.: Data Structures, Algorithms & Softwae Principles in C, Addison-Wesley, 1995
7. SEDGEWIK: Algorithmen
8. Frentiu, M., Pop, H.F., Serban, G.: Programming Fundamentals, Ed. Presa Universitara Clujeana, Cluj-Napoca, 2006


Assessment
Each student will receive a list of problems that must be solved during the term. For this homework the student will receive a first grade (A). Each student will receive a grade to a written paper at the middle of the term (B). At the end of the term the student must take an exam for which he will receive a third grade (C). The final grade will be computed as (2*A+2*B+6*C)/10. The access to the written paper is conditioned by the grade (A), which has to be at least 5. In order to promote the final exam, grade (C) and the final grade has to be at least 5.
Links: Syllabus for all subjects
Romanian version for this subject
Rtf format for this subject