Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Calculatoare şi tehnologia informaţiei
Programul de studii: Ingineria informatiei - in limba engleza
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		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.	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 and dynamic structures. [1, ch. 1, 2] 
- Abstractness and data encapsulation 
- Dynamic sets 
- Complexity

2. Data Types: domain, operations and data representation [6, ch. 5] 
- 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] 
- 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] 
- 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] 
- 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] 
- Related concepts
- Related applications 
- Specifications and design 
- Representations using arrays and linked lists

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

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

9. Hash-table [1, ch. 12] 
- 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] 
- 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] 
- 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. ADT Graph [1, ch. 23] 
- 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. SIMONAS SALTENIS, Algorithms and Data Structures, 2002.
5. STANDISH, T.A.: Data Structures, Algorithms & Softwae Principles in C, Addison-Wesley, 1995
6. Frentiu, M., Pop, H.F., Serban, G.: Programming Fundamentals, Ed. Presa Universitara Clujeana, Cluj-Napoca, 2006	

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

VII. Didactic methods used
Expositions: description, explanation, class lectures, lectures with demonstrations 
Conversations: debate, dialog, introductive conversations, conversations for knowledge consolidation, 
Use of problems: use of problem questions, problems and problem situations. 
Discovery: directed and independent rediscovery, discovery by documenting, experimental discovery. 
Other methods: case study; exercise, homework study.	

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. In order to promote the final exam, grade (C) and the final grade has to be at least 5.

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. 
3.	BRUNO R. PREISS, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, 1997	

	Dean,							Chair head,

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