1. Instructor information
:
Instructor name: Dr. Vu Thanh Nguyen Email: nguyenvt@uit.edu.vn
Phone: 848.38421595 Cell phone: 84.903936840
Office: UIT, Linh Trung, Thu Duc, HCMC Office hours:
2. Class room
:
Main class room (campus): UIT Auditorium
Online classroom (website):
Class meeting time: weekly
Library hours (where): VNU-Library.
3. Course information
:
Course description:
Credit: 4 (3 lecture, 1 lab).
This course provides an introduction about basic data structures and algorithms in programming: string matching, lists, trees, sorting, indexing, hashing,
graphs.
Course objectives:
Upon successful completion of this course, the student will be able to.
- Understand the concepts data, algorithms, programs.
- Describe the relevance of abstraction to problem solving.
- Implement data structures and algorithms.
- Apply appropriate data structures for particular problems.
Prerequisite:
- Introductory programming
- Array and pointer knowledges
- Use of simple data structures (queues, stacks, lists, trees)
4. Book and materials
:
Required textbook:
- Introduction to Algorithms, Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, The MIT Press © 2001.
-
Starting Out with C++ - From Control Structures through Objects
Data Structures & Algorithm Analysis in Java,
Mark Allen Weiss, Addison-Wesley, 1999.
Other materials:
Course website:
5. Course requirements
:
1. Describe formal analysis measures. {assignments, tests}
2. Describe the relevance of abstraction to problem solving. {tests}
3. String matching {assignments, programming}
4. Lists {assignments, programming}
5. Trees {assignments, programming}
6. Sorting {assignments, programming}
7. Iindexing, hashing {assignments, programming}
8. Graphs {assignments, programming}
9. Analyze algorithms. {assignments, tests}
10. Use appropriate data structures {programming assignments}
6. Grading Procedures
:
Oral and Written Communication (analysis, design, implementation, or use of selected algorithms is required of all students):
....................................................................................................... 20%
Prograrming assignments: ....................................................................................... 40%
Midterm Examinations: .......................................................................................... 20%
Final Examination: .................................................................................................. 20%
Total point and Grades
:
90-100: Good (A) 80-89: Well (B) 70-79: Mean (C)
60-69: Weak (D) 50-59: bad (E) 1-49: too bad (F)
7. Academic integrity Policies
:
- Student may not be absence in 4 sessions. If so, he/she will be prohibitted from test or exam
- Student may not use Vietnamese languague in their class, or will be reduced 2% final marks
- Be punctual to come and leave the class.
- Maximum cancellation time per semester is 6 hours per class.
8. Course outline
:
|
Week |
Topics |
Assigments |
|
1 |
Introduce about Data structures and Algorithms String matching a) Brute-Force b) Knuth-Morris-Pratt |
|
|
2, 3 |
List 1. linked list a) linear simply-linked list b) doubly linked list c) circular d) multiply-linked e) operations (1) create (2) insert (3) delete (4) traverse (5) concate 2. applications a) Stack (1) push (2) pop (3) create (4) isempty (5) isfull b) Queue (1) enqueue (2) dequeue (3) create (4) isempty (5) size (6) priority queue |
|
|
4, 5, 6 |
Tree 1. operations a) traverse (1) NLR (2) LNR (3) LRN b) add c) delete 2. binary search tree 3. balanced binary search trees a) operations (1) balance (2) rotation b) AVL tree c) Red-Black Tree 4. B-Tree 5. qBinary heap |
|
|
7, 8 |
Sorting 1. Selection sort 2. insert sort 3. interchange sort 4. bubble sort a) shaker sort 5. shell sort 6. heap sort 7. quick sort 8. merge sort 9. counting sort 10. bucket sort 11. radix sort |
|
|
9 |
Indexing 1. Dense 2. sparse 3. multi-level 4. b+ tree
|
|
|
10 |
Hashing 1. hash table 2. hash function 3. collision resolution a) chaining (1) linked-lists (2) dynamic arrays (3) balanced trees b) open-addressing (1) linear probing (2) quadratic probing (3) double hashing |
|
|
11, 12 |
Graphs 1. types a) directed graph b) undirected graph 2. implementation a) 2-array b) linked-list 3. graph-searching a) breadth-first search b) depth-first search c) topological sort 4. shortest path a) Bellman-Ford b) Dijkstra c) Floyd-Warshall d) Joshson |
|
|
13 |
Reviews and exams |
9. Comments and notes
:
Make-up: Make-up classes are officially accepted after the Make-up forms are signed by all of the students in the class and directly send to the
Registrars.
Preparation for Class: It is expected that the students read related chapter in textbook and lecture noted before each class. This will help to
capture the topics presented and discussed during class hours.
Use of Class Time: Class time will be used mainly for lectures and discussions. A small part of class hours is used for testing. House works will
be discussed on individual basis.
Class Attendance: Due to the broad range of topics discussed throughout the course and their inter-relationship, it is requested that the students
should attend the class regularly.
Incomplete Grade: A grade of “I” (Incomplete) will be administered only under extreme, verifiable “emergency” situation where the student is
unable to complete some portion of the course work due to circumstances beyond his/her control PROVIDED THE STUDENT IS PASSING THE COURSE.
Assignment Requirement: Assignments should be turned in both electronically (via drop-boxes or e-mail attachments) and on paper, by the due date.
We need BOTH so that we may run your electronic versions, and read (and write comments on) the code on the paper version. In general we won't begin grading
your assignment unless we have both copies; if for some reason you cannot hand in both an electronic and a paper copy, please communicate directly with the
TA so we know what's going on.
Instructor’s Signature
Dr. Vu Thanh Nguyen