Data Structures and Algorithms - INT 2043

K54Đ
Semester II, 2011

Announcements:

• There will be no programming assignments. Marks given for lab exercises will instead contribute to 20-30% of the final result.
• Midterm exam will be on April 9 (NOT April 11).
• (7/3/2011). Do sự khác biệt về chương trình học giữa hai ngành Công nghệ thông tin và Điện tử viễn thông. Nội dung của khóa học này được thiết kế đặc biệt cho ngành Điện tử viễn thông, không phù hợp yêu cầu của ngành Công nghệ thông tin. Các sinh viên ngành Công nghệ thông tin tham gia khóa này chỉ có thể học dự thính chứ không được lấy tín chỉ.
• Welcome! Lectures starts on February 14. Labs start next week. Information on lab sections will be posted here as soon as it is available.

Classes

Objectives:

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++ for their assignments and laboratory exercises.

Outcomes:

• 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.
• [AIC] Robert Sedgewick, Algorithms in C++, 3rd edition
• [DSAJ] Michael T. Goodrich and Roberto Tamassia. Data structures and Algorithms in Java (4th edition).
• Trần Minh Châu, Lê Sỹ Vinh, Hồ Sỹ Đàm, Giáo trình lập trình căn bản C++ (draft version)
• C++ quick reference and tutorial: Cplusplus.com (highly recommended!)

Course Description:

• Analysis of algorithms
• Recursion
• Stacks, queues and linked lists
• Trees, search orders
• Priority queue and heaps
• Binary search trees, AVL trees
• Hashing
• Sorting: quicksort, mergesort
• Graph traversal: breadth and depth first
• Shortest path, minimum spanning trees
• Fast string matching
• Dynamic programming

Assessment (tentative):

• Final exam: 50%, closed-book, written test
• Midterm exam: 20%, closed-book, written test
• Weekly lab exercises / homework: 30%, arbitrarily selected submissions will contribute to the mark.

• Plagiarism will result in immediate failure of the course!
• 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: