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	Category	Status	
2	2+1+0	fundamental	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
NICULESCU Virginia	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
Arrays (sorting algorithms: mergesort, heapsort, radixsort, bucketsort etc.)
Linked lists (simple, and double)
Hash-tabels
Binary trees
Stacks
Queues and priority queues
Heap structures
Maps
Balanced binary search trees
Algorithms complexity

V. Bibliography
BIBLIOGRAFIE
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
Lectures and seminars (S1-S14 corresponding to the 14 weeks of the second semester)

1. Introduction. Data Structures. Static, semistatic, and dynamic structures. (1 lecture – S1 + 1 seminar – S1 / S2)
- Abstractness and data encapsulation 
- Dynamic sets 
- Complexity

2. Data Types: domain, operations and data representation (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 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 (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  (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 lecture – S7)
- Related concepts
- Related applications 
- Specifications and design 
- Representations using arrays and linked lists

7. ADT Queue (1 lecture –  S7)
- Related concepts
- Related applications 
- Specifications and design 
- Representations using arrays and linked lists

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

9. Hash-table (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 lecture – S11 + 1 seminar – S13 / S14)
- Related concepts
- Related applications 
- Specifications and design 
- Linked Representation 
- ATDs Tree with different properties 

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

11. Heaps  (1 lecture – S12)
- The structure presentation 
- Binary Heap
- Priority Queue representation using a heap 
- HeapSort

12. Balanced Search Trees (1 curs – S13)
- AVL Trees
- Red-Black Trees 

13. ADT Graph (1 curs – S14)
- Related concepts
- Related applications 
- Specifications and design 

VII. Didactic methods used

Lectures, conversations, projects, exercises and individual study.

VIII. Assessment
Project (N1 - 30% final grade),
Seminar activity (N2 - 10% final grade)
Written exam (N3 -60% final grade). 
Final grade: NF =  (3*N1+N2+6*N3)/10. 
Requirements N1>=5 and  N3>=5 and NF >=5 	

IX. Additional references
1.	AMBSBURY, WAYNE: Data Structures. From Arrays to Priority Queues, 1993. (library)
2.	WIRTH, N.: Algorithms + Data Structures = Programs. Prentice- Hall Inc., 1976. (library)
3.	Bruno R. Preiss, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, 1997. (Campus – digital format) 
4.	V. Niculescu. A Uniform Analysis of Lists Based on a General  Non-recursive Definition, Studia Universitatis "Babes-Bolyai", Informatica, Vol. LI, No. 1 pp. 91-98 (2006).

	Date,							Course responsible,
							Assoc.Prof. NICULESCU Virginia, Ph.D.