Student manual  (Page 2/4)

The study of algorithms is intrinsically tied to the data structures. Data structures covered in this course are strings, stacks, records, linked lists, hash tables, trees and graphs.

These data structures and algorithms have close relationship. We have arranged them in a reasonable order.

Objectives

At the end of the course, students should

• have a good understanding of how a range of fundamental algorithms work, particularly those concerned with the classical problems of sorting and searching
• be able to analyse the efficiency in terms of space and time of most algorithms
• be able to design new algorithms or modify existing ones for new applications and reason about the efficiency of the result
• be able to organise convenient data structures to solve problems in practice

Prerequisites

The formal prerequisite for this course is Computer Science Fundamentals. In addition, the teaching of Data Structures and Algorithms needs to illustrate by programming languages and vice versa. This course thus should be presented concurrently with the course of programming languages (C, C++, Java).

Readings and resources

Here are some general books on algorithm and data structures:

Primary Text

• Textbook: T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, Second Edition. MIT Press, 2001, ISBN: 0262032937
• Lecture Notes on Data Structures and Algorithms, accompanied with this syllabus.

Alternatives/Background

• A. Aho, J. Hopcroft,&J. Ullman, The Design and Analysis of Computer Algorithms, Addison Wesley, 1974.
• Baase&Gelder, Computer Algorithms: Introduction to Design and Analysis, 3nd ed., Addison Wesley, 2000.
• Gilles Brassard&Paul Bratley, Algorithmics, Prentice Hall, 1988.
• Donald Knuth, The Art of Computer Programming, Addison Wesley, 2005.
• Robert Kruse, Data Structures and Program Design, Prentice Hall, 1984.
• Udi Manber, Introduction to Algorithms, Addison Wesley, 1989.
• Hồ Sĩ Đàm, Nguyễn Việt Hà, Bùi Thế Duy, Cấu trúc dữ liệu và giải thuật. Nhà xuất bản Giáo dục, 2006.

Grades

The overall grade for this course is based on your performance in (i) exercises, (ii) assignments, (iii) mid-term exam and (iv) final exam, with weights as given below. Exams consist of a midterm and a final exam.

Course component grading weight (it can be changed):

• Exercises: 20%
• Programming assignments: 20%
• Mid-term exam 20%
• Final exam: 40%

Content information

The content of this course is based on the text book “Introduction to Algorithms” presented in Reading and Resources section. The content has 8 parts, ordering by their dependency in which content of the later part used the knowledge of the previous parts.

The part 1 gives an introduction about algorithms and data structures. It is intended to be a gentle introduction to how we specify algorithms, and many of the fundamental ideas used in algorithm analysis. This part defines what an algorithm is and gives notions of data structures. Later parts will build upon this base.

In part 2, two types of data structures will be presented: Stack and queue. Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is prespecified. In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out, or LIFO. Similarly, in a queue, the element deleted is always the one that has been in the set for the longest time, the queue implements a first-in, first out, or FIFO. There are several efficient ways to implement stacks and queues on a computer. In this part we show how to use a simple array to implement each. With the stack and queue data structures, we concentrate on the definition, basic operations, implementation and applications of each in computer science.