This is the syllabus for Data Structures and Algorithms course intended for undergraduate programs. The following sections provide brief information about Purpose, Description, Objectives, Prerequisites, References Documents and Grades of the course.

This course and this Student Manual reflect a collective effort by your instructor. This

course is an important component of our academic program. Although it has been offered

for many years, this latest version represents an attempt to expand the range of sources of

information and instruction so that the course continues to be up-to-date and the methods

well suited to what is to be learned.

You will be asked from time-to-time to offer feedback on how the Student Manual is

working and how the course is progressing. Your comments will inform the development

team about what is working and what requires attention. Our goal is to help you learn

what is important about this particular field and to eventually succeed as a professional

applying what you learn in this course.

This Student Manual is designed to assist you through the course by providing specific

information about student responsibilities including requirements, timelines and

evaluations.

I hope you enjoy the course.

Contact Information

Faculty Information.

Name:Nguyen Viet HaOffice Location: 309 E3 Building

Email: hanv@vnu.edu.vn

Office Hours: 8am – 5pm weekdays

Support personnel – include all important contact information for:

The purpose of this course is to understand important problems, challenges, concepts and techniques from the field of Algorithms and Data Structures. In order to achieve this, students learn how to design efficient algorithms, evaluate their time and space complexity. More specifically, in this course, students will:

This course introduces base knowledge of algorithm design, elementary analysis of algorithms, and fundamental data structures. The emphasis is on choosing appropriate data structures and designing correct and efficient algorithms to operate on these data structures.

In computer programming, algorithms play an important role. You will learn in this course how to develop efficient algorithms, analyse their running time and implement them efficiently. We discuss sorting algorithms, searching, recursion, dynamic and graph algorithms.

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.

At the end of the course, students should

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).

Here are some general books on algorithm and data structures:

Primary Text

Alternatives/Background

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):

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.

In part 3, we present the linked lists, a data structure that students should know before learning the binary search tree. The fundamental types of linked lists are single-linked lists, double-linked lists, circularly-linked lists, linearly-linked lists. We describe these types of linked lists and integrated algorithms used to create, insert, delete, … their nodes.

In part 4, we study the recursion in computer programming. Recursion defines a function in terms of itself, it is largely used to solve problems such as divide and conquer, backtracking,… We give an overview about recursive functions, recursive algorithms, recursive programming and a comparison between recursion and iteration in programming.

Part 5 of this course gives an interesting data structure and its integrated algorithms, the binary search tree. We will focus on principal operations of binary search tree such as searching, insertion, deletion. Compared to linear data structures like linked lists and one dimensional arrays, which have only one logical means of traversal, tree structures can be traversed in many different ways. In this part, we present also three types of traversals: preoder, inorder, postorder.

In part 6, we examine basic sort algorithms. These algorithms are: Insertion sort, Quick sort, Bubble sort, Merge sort, Heap sort, Selection sort. With each algorithm, we describe the mechanism and their implementation. The comparison of the complexity of these algorithms will be introduced.

Part 7 presents problems relating graph. This part includes the graph theory, minimum spanning trees problems. We also give an algorithm to solve the shortest paths problems. Concerning algorithms of search in a graph, we introduce the breath-first search and depth-first search.

Finally, part 8 introduces hash tables, an type of data structure which are used to optimize the capacity of storage and the speed of searching, hash tables support the dictionary operations INSERT, DELETE, and SEARCH. In this part, we will also present how to choose convenient hash functions to distribute elements into hash tables and how to solve the collision problems in hashing.

Unit 1. Introduction

Task 1: Read the following:

Unit 2. Stack and Queue

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook p.203 : from 10.1-1 to 10.1-4 all

Textbook p.204 : from 10.1-5 to 10.1-7 all

Unit 3. Link lists

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook p.208 : from 10.2-2 to 10.2-6 all

Textbook p.209 : 10.2-7, 10.2-8 all

Unit 4. Recursion

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook

Textbook

Unit 5. Binary search trees

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook

Textbook

Unit 6. Sorting (part one)

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook

Textbook

Unit 7. Sorting (part two)

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook

Textbook

Unit 8. Graphs (part one)

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook

Textbook

Unit 9. Graphs (part two)

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook

Textbook

Unit 10. Hashing (part one)

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook

Textbook

Unit 11. Hashing (part two)

Task 1: Read the following:

Task 2: Do the following exercises:

These exercises are NOT homework questions.

They are for helping you understand the materials of this unit

Textbook

Textbook

Assignment problem 1 - Depth First Search and The N-Queens Problem (4 weeks)

(See assignment problem link for details)

Assignment problem 2 - Greedy Search and The N-Queens Problem (4 weeks)

(See assignment problem link for details)

Assignment problem 3 - Finding a maximum weight matching in a weighted bipartite graph (6 weeks)

(See assignment problem link for details)

Assignment problem 4 - Stable marriage problem (6 weeks)

(See assignment problem link for details)

Homework 1. Stack and Queue – 7 exercises

(See exercises link for details)

Homework 2. Linked lists – 4 exercises

(See exercises link for details)

Homework 3. Designing algorithms – 3 exercises

(See exercises link for details)

Homework 4. Binary Search Trees – 20 exercises

(See exercises link for details)

Homework 5. Sorting – 19 exercises

(See exercises link for details)

Homework 6. Graphs – 5 exercises

(See exercises link for details)

Homework 7. Hashing – 12 exercises

(See exercises link for details)