Data Structures and Algorithms - INT 2043

K55Đ
Semester II, 2012

Announcements:

(03/05/2012). Midterm results.
(28/3/2012). Place and time of lab sessions updated.
(28/3/2012). Lab groups 1 and 2 use bbc.vnu.edu to submit all lab exercises. Details will be available in your first lab session.
(26/3/2012). Lab01 project in bitbucket must be named EXACTLY as dsa-lab01. You must inform your lab instructor of your bitbucket username by the first lab session.
(22/3/2012). Welcome again! Lectures start on March 27. Labs start next week.
(23/2/2012). Môn học này được hoãn cho đến tuần 8 để sinh viên học xong môn tiên quyết. Từ tuần 8 sẽ học mỗi tuần 2 buổi lí thuyết và 2 buổi thực hành vào giờ của môn Tin học Cơ sở 3.
(6/2/2012). 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ế riêng 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 start on February 7. Labs start in week 2. Information on lab sections will be posted here as soon as it is available.

Classes

Lectures: Tue 4-5, 308-G2, Thu 6-7, 309-GĐ2
Lecturer: Trần Thị Minh Châu (Office: 309 E3)
Labs:
Group 1: Wed 2-3 at 202-G2, Sat 2-3 at 202-G2, Instructor: Nguyễn Quốc Đại (nquocdaiATgmail.com,303-E3)
Group 2: Wed 4-5 at 202-G2, Sat 4-5 at 202-G2, Instructor: Nguyễn Quốc Đại
Group 3: Wed 4-5 at 2.1-E4, Sat 4-5 at 208-G2, Instructor: Lê Minh Khôi (khoilmATvnu.edu.vn, 306-E3)

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++ 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 complexity of algorithms.
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, Lập trình cơ bản với C++ (draft version) (có thể mượn tại thư viện ĐHQG)
C++ quick reference and tutorial: Cplusplus.com (highly recommended!)

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
Hashing
Sorting: bubble sort, insertion sort, quicksort, mergesort
Graph traversal: breadth and depth first
Shortest path, minimum spanning trees
Dynamic programming (optional)

Assessment (tentative):

Final exam: 60%, closed-book, written test.
Midterm exam: 20%, closed-book, written test.
Weekly lab exercises / homework: 20%.

Note:

Plagiarism will result in immediate failure of the course!
Lab work must be demonstrated to your lab instructor as well as electronically submitted. Late submissions (without valid excuse) will not be accepted.
Homework is given after each topic. Students should submit their solutions in hand-written form at the beginning of the next lecture.

Schedule (subjected to changes without warnings):

Week	Lecture	Readings/Notes/Samples	Homework	Lab
1	Introduction	Programming style guide
8.Tue	C++ Review Template	Hướng dẫn sử dụng Bitbucket Point.h,Segment.h,TestSegment.cpp	Hw01 (due on Thusday)	Lab01(due on April 4)
8.Thu	Algorithm Analysis	DSAJ Ch.4 Optional Experimental setup	Hw02	Lab01
9.Tue	Recursion	DSAJ Ch.3	Hw03	Lab02 (due on 11/4)
9.Thu	Linked lists	DSAJ Ch.3	Hw04(due on Tuesday 17/4)	Lab02 (cont.)
10.Tue	Stacks & queues	DSAJ Ch.5	Hw05 (stacks)	Lab03 (due on 18/4)
10.Thu	Stacks & queues (cont.)	DSAJ Ch.5	Hw05 (queues)	Lab03 (cont.)
11.Tue	Trees	DSAJ Ch.7	Hw06	Lab03 (cont.)
11.Thu	No lecture
12.Tue	Midterm exam			Lab04 (due on 2/5)
12.Thu	Binary Search Trees	DSAJ Ch.10	Hw07	Lab04 (continue)
13.Thu	Sorting C++ Templates	DSAJ Ch.11	Hw08	Lab05 (due on 15th May)
14.Tue	Maps, Dictionaries, Hashing Sample code: map.cpp, multimap.cpp	DSAJ Ch.9	Hw09	Lab05(continued)
14.Thu	Graphs	DSAJ Ch.13		Lab05(continued) Lab06 (due on the last lab)
15.Tue	Graphs (DFS, BFS)	DSAJ Ch.13	Hw10: R-13.1,2,3,7,8,10,22, 23, 24. (DSAJ, Ch.13, p.864--)	Lab06(cont.)
15.Thu	Graphs (shortest paths, minimum spanning trees) Review	DSAJ Ch.13	Hw11: R-13.14. (DSAJ, p.867)	Lab06(cont.)