Data Structures and Algorithms
K53Đ
Semester I, 2010
Announcements:
- We're done!. No labs after this week (Dec. 13-17). But watch out for upcoming news such as exam samples and assignment-related stuff.
- No class on November 24.
- No class on November 17.
- Midterm exam will be held in class on November 3rd.
Closed-book, written test. Students should review material up to (and including) Priority queues.
- Assignment is out!
Due date and instructions on how to submit will be announced later.
Staff:
Instructor: Trần Thị Minh Châu
Office: 309 E3
Teaching Assistant: Nguyễn Bá Đạt
Email:datnb.nguyenATgmail.com
Office:.
Lab Instructor: Nguyễn Việt Anh
Email: vietanhATvnu.edu.vn
Office: Trung tâm máy tính, G2.
Objectives:
The main goal of this course is to introduce the basic data structures and algorithms. This course will also help students to develop skills in the design and analysis of algorithms and data structures.
Although the course examples are given in C++, this is not a course in C++. Students are expected to be able to program in C/C++ or Java for their assignments and laboratory exercises.
Outcomes:
At the end of the course, students should be able to:
- understand the basic data structures and algorithms.
- analyse the complexities of software.
- select appropriate data structures and algorithms for applications at hand.
Resources
- Đinh Mạnh Tường. Cấu trúc dữ liệu và giải thuật.
- [DSPS] Mark Alen Weiss. Data Structures and Problem Solving using C++. Addison Wesley. 2000
- Main text[DSAJ] Michael T. Goodrich and Roberto Tamassia. Data structures and Algorithms in Java (4th edition).
Course Description:
The following list includes the main topics covered in the course:
- Analysis of algorithms
- Recursion
- Stacks, queues and linked lists
- Trees, search orders
- Priority queue and heaps
- Binary search trees, AVL trees
- Huffman codes, data compression
- Hashing
- Dictionaries
- Sorting: quicksort, mergesort
- Graph traversal: breadth and depth first
- Shortest path, minimum spanning trees
- Tries
- Fast string matching
- Dynamic programming
Assessment (tentative):
- Final exam: 50%, closed-book, written test
- Midterm exam: 20%, closed-book, written test
- 01 assignment: 20%
- Late submissions (without valid excuse) are not accepted.
- Weekly lab exercises / homework: 10%, ten arbitrarily selected submissions will contribute to the mark.
Note:
- Plagiarism will result in immediate failure of the course!
No exam retake will be allowed.
- Late submissions of assignments (without valid excuse) will not be accepted.
- Lab work should be shown to the lab instructor during that week or the week after, i.e. only one week late at the latest.
ALL work must be electronically submitted to the course website (detailed instruction will be given later)
- Homework is given after each topic.
Students should submit their solutions in hand-written form at the beginning of the following lecture.
Schedule: