Credits:
3
for
NETB201 and 3 for NETB211
Department Informatics
Lecturers: Assoc. Prof. PhD
Nikolay Kirov (NETB201) and Assist.
Prof.
Emil
Kelevedzhiev (NETB211)
e-mail:
nkirov<at>nbu.bg,
keleved<at>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://nikolay.kirov.be/2011/NETB201/index.html
(or mirror http://www.math.bas.bg/~nkirov/2011/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:
- 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
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/2011/netb201/ or http://nikolay.kirov.be/2011/NETB201/index.html