Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MIE0001	Data Structures and Algorithms	

Semester	Hours: C+S+L+P	Category	Status	
2	2+1+0+0	fundamental	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
MOTOGNA Simona Claudia	Ph.D.	Assoc.Prof.	Programming  Languages and Methods	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
- 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. 

IV. Course contents
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 

V. Bibliography
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

	

VI. Thematic of didactic activities per weeks

VII. Didactic methods used

VIII. 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.

IX. Additional references

	Dean,							Chair head,

	Date,							Course responsible,
								Assoc.Prof. MOTOGNA Simona Claudia, Ph.D.