## 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

### 1. COMPETENCES:

Students successfully finished this course will:
1) know:
• Stacks, Queues, Linked Lists and Recursion
• The Tree Abstract Data Type, Basic Algorithms on Trees, Binary Trees, Data Structures for Representing Trees
• The Priority Queue Abstract Data Type
• The Dictionary Abstract Data Type, Hash Tables, Ordered Dictionaries
• Binary Search Trees, AVL Trees, Multi-Way Search Trees, (2,4) Trees, Red-Black Trees, Locator-Based Search Trees
• The Set ADT, A Lower Bound on Comparison-Based Sorting, Comparison of Sorting Algorithms
• Pattern Matching Algorithms
2) be able to:
• Using Recursion, Stacks, Queues, Linked Lists, Double-Ended Queues
• Using STL Vectors, Lists and Sequences
• Implementing a Priority Queue with a Sequence, Heaps, The Locator Design Pattern
• Writing Quick-Sort,  Bucket-Sort and Radix-Sort
• Using Tries, Text Compression, Text Similarity Testing

### 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/