Student manual  (Page 3/4)

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.

Instructional sequence

Unit 1. Introduction

Task 1: Read the following:

1. Introduction to Data Structure and Algorithms
2. Textbook: The role of algorithms in computing (1.1 – 1.2)
3. Textbook: Introduction to data structures. pp. 197

Unit 2. Stack and Queue

Task 1: Read the following:

1. Stack and Queue
2. Textbook: Stack and Queues pp.200

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:

1. Link lists
2. Textbook: Link lists pp.204

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