COURSE PASSPORT

Data Structures

NETB201 and NETB211

Lecturers: Nikolay Kirov, Emil Kelevedzhiev
e-mail: nkirov@nbu.bg, keleved@math.bas.bg

We will maintain a course homepage that will contain links to all course handouts and some supplementary materials. The URL for this course is
http://www.math.bas.bg/~nkirov/2006/NETB201/index.html
which you may want to save as a bookmark in your web browser. 

1. COMPETENCES:

    Students successfully finished this course will:
1) know:
2) be able to:

2. MAIN TOPICS

1. C++ Programming and Object Oriented Design
2. Analysis Tools
Running Time and Pseudo-Code, A Quick Mathematical Review, Analysis of Algorithms, Asymptotic Notation, Asymptotic Analysis
3. Stacks, Queues, and Recursion
Using Recursion, Stacks, Queues, Linked Lists, Double-Ended Queues, Sample Case Study Application: The Stock Span Problem
4. Vectors, Lists, and Sequences
Vectors, Lists, Sequences, Case Study: Bubble-Sort on a Sequence, Iterators, A Hierarchy of Sequence ADTs
5. Trees
The Tree Abstract Data Type, Basic Algorithms on Trees, Binary Trees, Data Structures for Representing Trees
6. Priority Queues
The Priority Queue Abstract Data Type, Implementing a Priority Queue with a Sequence, Heaps, The Locator Design Pattern
7. Dictionaries
The Dictionary Abstract Data Type, Hash Tables, Ordered Dictionaries, Skip Lists
8. Search Trees
Binary Search Trees, AVL Trees, Multi-Way Search Trees, (2,4) Trees, Red-Black Trees
9. Sorting, Sets, and Selection
The Set ADT, Quick-Sort, A Lower Bound on Comparison-Based Sorting, Bucket-Sort and Radix-Sort, Comparison of Sorting Algorithms, Selection
10. Text Processing
Pattern Matching Algorithms, Tries, Text Compression, Text Similarity Testing
11. Graphs
The Graph Abstract Data Type, Data Structures for Graphs, Graph Traversal, Directed Graphs, Weighted Graphs, Shortest Paths

3. RECOMMENDED TEXTBOOKS

  Michael Goodrich, Roberto Tamassia, David M. Mount, Data Structures and Algorithms in C++ , Wiley, 2004

4. TEACHING FORMS

Each topic includes:
- Theoretical lecture
- Workshop

5. FORM OF EVALUATION AND COMPETENCE ASSESSMENT

NETB201

Tests
Homeworks
Practice
Written exam
Oral exam		 Curren Evaluation
40%
30%
30%
0%
0%		 Term Exam
40%
0%
20%
20%
20%
NETB211


Homeworks
Practice 		Curren Evaluation

30%
70%

 Term Exam

30%
70%

6. CURRENT CONTROL AND SCHEDULE  
Points for NETB201
Current 
Evaluation 		Points for NETB211
Current 
Evaluation 		Week No.
Points for NETB201
Term Exam 		Points for NETB211
Term Exam
Test_1 NETB201 10 - 5
- -
Test_2 NETB201 10 - 10
- -
Final Test NETB201 20 - 15
40 -
Homework_1 NETB211 10 10 6
- 10
Homework_2 NETB211 10 10 11
- 10
Homework_3 NETB211 10 10 15
- 10
Exam of Practice_1 NETB211 10 10 6
- -
Exam of Practice_2 NETB211 10 10 11
- -
Final Exam of Practice NETB211 10 50 15
20 70
Written Exam NETB201
 - - -
20 -
Oral Exam NETB201 - - -
20 -
Extra Points* both max 5 max 5 -
 -  -
Total:
100 100 -
100 100
Points (or %) Grade
90-100 Excellent 6
76-89 Very good 5
60-75 Good 4
50-59 Satisfactory 3
0-49 Poor 2

7. ADDITIONAL EXPLANATION ON THE EXAMINATION MATERIALS AND EVALUATION CRITERIA

Obliged attendance of the lessons – minimum 80% (24 hours per each subject = 48 hours from 60)  
http://www.math.bas.bg/~nkirov/2006/netb201/