Ktl-icon-tai-lieu

Giáo trình cấu trúc dữ liệu - English

Được đăng lên bởi Johny Trần
Số trang: 260 trang   |   Lượt xem: 6532 lần   |   Lượt tải: 1 lần
15/01/2013

Data structure

Instructor Information
Dr. Nguyen Thanh Binh
Email: ntbinh@dut.udn.vn
Office: Faculty of IT

2

Objectives
•
•
•
•

Understand data structures (lists, trees, hash tables)
Understand graph representations and algorithms
Understand time and space analysis
Be able to translate high-level, abstract data
structure descriptions into concrete code
• Data structures will include lists, vectors, queues,
stacks, trees, hash-tables, and graphs
• Algorithms include searching, sorting using the
above data structures, iterative, and recursive
algorithms
3

1

15/01/2013

Prerequisites & Textbook
• Prerequisites
– Programming in C
– Discreet mathematics
• Proof techniques (induction, contradiction), mathematical
structures (sets, relations, trees, graphs)

• Textbook & References
– Ellis Horowitz, Sartaj Sahni and Susan Anderson-Freed,
Fundamentals of Data Structures in C, 2nd Edition, Silicon
Press, 2007.
– M.A. Weiss, Data Structures and Algorithm Analysis in C,
2nd Edition, Addison Wesley, 1997.
4

Assignments & Projects
• On assignments, students are asked to
implement data structures and algorithms
using C language
• Projects
– Group of 2 or 3 students
– A given subject
– A report & a presentation are required for each
group at the end of semester
5

Grading information
• Assignments: 20%
• Midterm exam: 30%
• Final Exam: 50%

6

2

15/01/2013

What this course is about?
• Data structures: conceptual and concrete ways
to organize data for efficient storage and
efficient manipulation
• Employment of this data structures in the
design of efficient algorithms
• Analysis of the algorithms complexity

7

Why do we need them?
• Requirements for a good software
– Good detailed design
– Easy maintenance
– Reliable
– Easy to use
– Reusable
→Efficient data structure
→Efficient algorithms
8

Content
•
•
•
•
•
•
•

Topic #0: Course Introduction
Topic #1: C Language Review
Topic #2: Algorithm Analysis
Topic #3: Arrays and Structures
Topic #4: Stacks and Queues
Topic #5: Lists
Topic #6: Trees, Binary Trees, Binary Search
Trees
9

3

15/01/2013

Content
•
•
•
•
•

Topic #7: Graphs
Topic #8: Sorting
Topic #9: Hashing
Topic #10: Heap Structures
Topic #11: AVL Trees

10

Example
• Given n numbers, how many steps do we need
to search a number from the n numbers
– Linear search
– Binary search

• How to search a word in a dictionary?

11

C Language Review

12

4

15/01/2013

Content
• Basics of C language
• Recursion

13

Overview of C
• C is developed ...
15/01/2013
1
Data structure
Instructor Information
Dr. Nguyen Thanh Binh
Email: ntbinh@dut.udn.vn
Office: Faculty of IT
2
Objectives
Understand data structures (lists, trees, hash tables)
Understand graph representations and algorithms
Understand time and space analysis
Be able to translate high-level, abstract data
structure descriptions into concrete code
Data structures will include lists, vectors, queues,
stacks, trees, hash-tables, and graphs
Algorithms include searching, sorting using the
above data structures, iterative, and recursive
algorithms
3
Giáo trình cấu trúc dữ liệu - English - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Giáo trình cấu trúc dữ liệu - English - Người đăng: Johny Trần
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
260 Vietnamese
Giáo trình cấu trúc dữ liệu - English 9 10 585