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	
LUPSA Dana	Ph.D.	Lect.	Computer Science	*			

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 and dynamic structures. [1, ch. 1, 2] 
- Abstractness and data encapsulation 
- Dynamic sets 
- Complexity

2. Data Types: domain, operations and data representation [2] 
- 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. Set [1, ch. 5] 
- concepts; ADT
- Specifications and design 
- Representations using arrays, linked lists, hash tables, and binary trees 
- Related applications 

Bag [1, ch. 5] 
- concepts; ADT
- Specifications and design 
- Representations using arrays, linked lists, hash tables, and binary trees
- Related applications 

4. Map; Sorted map [4, ch. 6] . 
- concepts; ADT
- Specifications and design 
- Representations using arrays, linked lists, hash tables, and binary trees 
- Related applications 

5. List; Sorted Lists [1, ch. 11] [5]
- - concepts; ADT
- Related applications 
- Specifications and design 
- Representations using arrays and linked lists

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

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

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

8. Priority Queue  [1, ch. 7] 
- - concepts; ADT
- Related applications 
- Specifications and design 
- Representations using arrays and linked lists

9. Hash-table [1, ch. 12] 
- Concepts, properties 
- Direct Addressing 
- Open and Closed Hash-tables 
- Collisions resolution:  chaining, interleaved lists and open addressing
- Operations: searching, insertion / deletion 

10. Tree [1, ch. 13] 
- - concepts; ADT
- Specifications and design 
- Linked Representation 
- ATD Tree with different properties 
- Related applications 

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

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

12. Balanced Search Trees [1, ch. 14; 3] 
- AVL Trees
- Red-Black Trees 

13. Graph [1, ch. 23] 
- concepts; ADT, related applications	

V. Bibliography
1. CORMEN, THOMAS H. - LEISERSON, CHARLES - RIVEST, RONALD R.: Introducere în algoritmi. Cluj-Napoca: Editura Computer Libris Agora, 2000. 
2. FRENTIU M., POP H.F., SERBAN G., Programming Fundamentals, Ed.Presa Universitara Clujeana, Cluj-Napoca, 2006
3. HOROWITZ, E.: Fundamentals of Data Structures in C++. Computer Science Press, 1995. 
4. MOUNT, DAVID M.: Data Structures. University of Maryland, 1993. 
5. NICULESCU V., CZIBULA G., Structuri fundamentale de date. O perspectiva orientate obiect. Editura Casa Cartii de Stiinta, Cluj-Napoca,2011
6. STANDISH, T.A.: Data Structures, Algorithms & Softwae Principles in C, Addison-Wesley, 1995
7. SIMONAS SALTENIS, Algorithms and Data Structures, 2002.

VI. Thematic of didactic activities per weeks
Week 1.        Introduction. Data Structures. Complexity.
Week 2.        Data Types: domain, operations and data representation 
Week 3.        Containers. Iterators.
Week 4 & 5  Lists, Arrays . Linked lists
Week 6         Set, Bag, Map
Week 7         Stack ; Queue ; Priority Queue 
Week 8.        Stacks & queues : problems and applications
Week 9.        Trees ; Binary Search Trees
Week 10.      Heaps ; HeapSort
Week 11.      Sorting algoritms: ranksort, radixsort, bucketsort, etc.
Week 12       Hash-table, hash-function
Week 13.      Balanced trees (AVL, Red-black)
Week 14       Graph	

VII. Didactic methods used
Lectures, conversations, exercises, individual study, homework assignments.	

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). At the end of the term the student must take an  exam for which he will receive a second grade –(B). The final grade will be computed as (3*A+7*B)/10. In order to promote the final exam, grade (B) and the final grade has to be at least 5.
Further information regarding the evaluation process and the course requirements can be found following the URL:  http://www.cs.ubbcluj.ro/~dana/DSA

IX. Additional references
1. AMBSBURY, WAYNE: Data Structures. From Arrays to Priority Queues, 1993. 
2. WIRTH, N.: Algorithms + Data Structures = Programs. Prentice- Hall Inc., 1976.

	Dean,							Chair head,

	Date,							Course responsible,
								Lect. LUPSA Dana, Ph.D.