Data Structure & Algorithm

Course Notes to

DATA STRUCTURE AND ALGORITHM

Dr. Dao NamAnh

OBJECTIVE

Data Structures and Algorithms are fundamental to programming and to understanding computation. The purpose of this module is to provide students with a coherent introduction to techniques for using data structures and some basic algorithms, and with the tools for applying these techniques to computational problems. Teaching and learning methods include lectures and reading material which describe techniques for analyzing algorithms and applications of data structures, and a problem sheet which gives students an opportunity to practice problem solving.

PREREQUISITES

Prrogramming language C/C++ or Java

COURSE OUTLINE

Introduction to Data Structures and Analysis of Algorithms

• Algorithm, Elementary/Abstract data types
• Flowchart
  • Linked list, stack, Dijkstra’s stack, queue
  • Recursion, Euclid, factorial
• Trees
• Dynamic Programming

Bài giảng Khóa học

CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI

Ts. Đào NamAnh

MỤC ĐÍCH

Môn học cấu trúc dữ liệu và giải thuật cung cấp cho sinh viên một khối lượng lớn các kiến thức cơ bản về các kiểu dữ liệu trừu tượng và các phép toán trên kiểu dữ liệu đó. Khóa học này tập trung vào việc nghiên cứu các kiểu dữ liệu có cấu trúc có kích thước không đổi hoặc thay đổi trong ngôn ngữ lập trình. Ngoài ra còn giới thiệu các giải thuật chung quanh các cấu trúc dữ liệu này như cách tổ chức, thực hiện các phép toán tìm kiếm, sắp xếp thứ tự nội, sắp xếp thứ tự ngoại.

ĐIỀU KIỆN

Kỹ thuật lập trình trên ngôn ngữ C/C++ hoặc Java

NỘI DUNG MÔN HỌC

Giới thiệu về Cấu trúc dữ liệu và Thuật giải

• Thuật giải, Kiểu dữ liệu cơ bản, trìu tượng
• Lưu đồ
  • Danh sách, ngăn xếp, ngăn xếp Dijkstra, hàng đợi,
  • Đệ qui, Euclid, giai thừa
• Cây
• Qui hoạch động

Sorting Algorithms

• Selection, Insertion, Bubble, Shell sort
• Quick sort
• Merge sort
• Heap sort
• Radix sort

Thuật giải sắp xếp

• Chọn, Chèn, Nổi bọt, Shell sort
• Phân đoạn
• Sắp xếp trộn
• Vun đống
• Cơ số

Searching Algorithms

• Sequential and Binary Search
• Binary Search Tree
• Hash tables

Thuật giải tìm kiếm

• Tìm kiếm tuần tự, Tìm kiếm nhị phân
• Cây nhị phân tìm kiếm
• Phép băm

Graph Algorithms

• Undirected Graph
• Depth-first search
• Breadth-First Search
  • Directed Acyclic Graph. Topological Sort
  • Shorted path. Dijkstra's algorithm and Floyd's algorithm
• Connected components
  • Minimum spanning tree: Kruskal's algorithm, Prim's algorithm

Thuật giải đồ thị

• Đồ thị không hướng
• Tìm kiếm theo chiều sâu
• Tìm kiếm theo chiều rộng
  • Đồ thị định hướng không có chu trình. Sắp xếp tôpô
  • Đường đi ngắn nhất. Thuật toán Dijkstra và Thuật toán Floyd
• Các đỉnh liên thông
  • Cây bao chùm ngắn nhất: Thuật toán Kruskal, Thuật toán Prim

GRADING

A combination of discussions and short tests (30%),

Project Presentation (70%).

Project defense at 13:00 Saturday, 13/04/2013 in room K203.

RECOMMENDED TEXTS

ĐÁNH GIÁ

Các bài kiểm tra ngắn (30%),

Bảo vệ Đồ án(70%).

Điểm bảo về đề tài xem tại đây

Bảo vệ 13:00 thứ Bảy ngày 13/4/2013 tại K203.

TÀI LIỆU THAM KHẢO

INTERESTING LINKS

CÁC TRANG WEB HỮU ÍCH