UNDERGRADUATE PROGRAM

SYLLABUS

(Under Decision No.378/QĐ-ĐHFPT dated 2/

1 Course Name
2 Course Code
3 No of credits
4 Degree Level

5 Time Allocation

6 Pre-requisite

Course Objectives
7
(CO)

Learning
8 Outcomes
(LO)

9 Student's task

529645867.xlsx
 Teaching &
10 Learning
Materials

Assessment
11
scheme

12 Scoring scale
13 Schedule
14 Exam structure

15 Approval Date

16 Approval Level

529645867.xlsx
 FPT UNIVERSITY

UNDERGRADUATE PROGRAM
SYLLABUS

(Under Decision No.378/QĐ-ĐHFPT dated 2/4/2021)

DATA STRUCTURES AND ALGORITHMS (In Java)
CSD201
3
Bachelor

Contact time: 30 sessions

Lectures: 14
Lab/Tutorials: 16
Home study: 30 sessions
1 session = 90'

PRO192 (Object-Oriented Programming)

Upon finishing the course, students can:

1) Knowledge: Understand (ABET e)
- the connection between data structures and their algorithms, including an analysis of algorithms' comple
- data structurre in the context of object-oriented program design;
- how data structure are implemented in an OO programming language such as Java
2) Able to (ABET e)
- organize and manipulate basic structures: array, linked list, tree, heap, hash
- use algorithms for traversing, sorting, searching on studying structures
- select a suitable algorithm to solve a practical problem
3) Able to (ABET k)
- use JAVA programming language for solving some problems
- use Eclipse tool for developing programs in JAVA
- Implement some programs in JAVA to solve practical problems based on the studying algorithms
4) Others: (ABET i)
- Improve study skills (academic reading, information searching, ...)

LO1. Describe the list data structure and its’ different way of implementations. Write programs to implement the si
LO2. Define stack and queue. Describe basic operations and the use of these structures. Write programs to implem
push, pop, enqueue, dequeue,...
LO3. Describe about recursive definitions, algorithms, functions and their implementation and use.
LO4. Explain about general tree, Binary Tree and Binary Search Tree (BST). Write programs to implement BST w
LO5. Discuss about graphs and their application. Write programs to implement a graph with some basic operation
LO6 Explain the operation and performance of some basic and advanced sorting alggorithms
LO7 Explain about hashing and application.
LO8 Describe the Text Processing problem and its’ application. Explain the Huffman, LZW and Run-length encod

- Students must attend more than 80% of contact sessions in order to be accepted to the final examinatio
- Student is responsible to do all exercises given by instructor in class or at home and submit on time
- Promptly access to the FU CMS at http://cms.fpt.edu.vn for up-to-date course information

529645867.xlsx
Main books/resources:
1) Michaelt T. Goodrich, Roberto Tamassia, Michael H. Goldwasser: Data Structures and Algorithms in Ja
2) Link to the book: http://coltech.vnu.edu.vn/~sonpb/DSA/Data%20Structures%20and%20Algorithms%2
3) FU slides (ppt)
4) FU exercises (pdf)
5) Code files for students (java files)
6) FU CMS at http://cms.fpt.edu.vn.

Other references/resources:
1) Robert Lafore, Data Structures & Algorithms in Java
Second Edition, 2003 by Sams Publishing
(http://rineshpk.weebly.com/uploads/1/8/2/0/1820991/data_structures_and_algorithms_in_javatqw_darks
2) http://www.dmoz.org/Computers/Algorithms/index.htm

Tools:
- Internet
- NetBeans IDE tool for Java programming

1) On-going Assessment
- 2 Assignments: 20%
- At least 2 progress tests: 20%
- 1 Practical Exam (PE) 30%
2) 1 Final Exam: 30%
3) Final Result 100%
Completion Criteria:
1) Every on-going assessment component > 0
2) Practical Exam > 0
3) Final Exam Score >= 4 & Final Result >= 5

10
See Appendix 1
See Appendix 2

529645867.xlsx
 0

529645867.xlsx
529645867.xlsx
 LO1. Describe the list data
structure and its’ different way
1 of implementations.
Implement the singly linked
list.

LO2. Define stack and queue.

2 Describe basic operations and
the use of these structures.

LO3. Describe about

recursive definitions,
3
algorithms, functions and
their implementation and use.

LO4. Explain about general

tree, Binary Tree and Binary
4 Search Tree (BST).
Implement BST with basic
operations.
 LO5. Díscuss about graphs
and their application.
5
Implement a graph with some
basic operations.

LO6 Explain the operation

and performance of some
6
basic and advanced sorting
alggorithms

LO7 Explain about hashing

7
and application.

LO8 Describe the Text

Processing problem and its’
8 application. Explain the
Huffman, LZW and Run-
length encoding Algorithms.
LEARNING OUTCOMES IN DETAILS

LO1.1 Demonstrate the list data structure with basic operations: insert, remove, edit, search, sort,...
LO1.2 Explain two ways of implementing a list: using arrays and using linked lists.
LO1.3 Write programs to implement the singly linked list with basic operations: add (last, first, before, after, at positi
LO1.4 Understand the doubly linked-list data structure with basic operations.
LO1.5 Write code snippets which manipulate operations on doubly linked list, and use diagrams to illustrate the effe
LO1.6 Describe the circularly linked-list data structure with some basic operations like add, remove.
LO1.7 Expain why the Java code library provides the ArrayList and LinkedList classes

LO2.1 Define stack and queue.

LO2.2 List and demonstrate the operations common to stacks and queues.
LO2.3 Describe specific tasks to which stacks and queues are suited.
LO2.4 Apply stacks to a specific application.
LO2.5 Apply queues to a specific application.
LO2.6 Write programs to implement stack and queue in Java programming language.
LO2.7 Define and explain the need of priority queue.

LO3.1 Describe the basic ideas of recursion and how to set up recursive systems that represent certain real-world p
LO3.2 Know how to develop recursive algorithms and programs
LO3.3 Write programs in Java using recursion to solve some problems, like creating the Fibonacci sequence.
LO3.4 Analyse a recursive function to find out its’ ouput without running.
LO3.5 Explain type of recursive functions, give examples and comparing them.
LO3.6 Compare recursion with iteration, analyzes their pros and cons

LO4.1 Define general tree, Binary Tree and Binary Search Tree (BST).
LO4.2 Given a BST and a sequence of insert and delete operations on it, draw the resulted tree.
LO4.3 Find the smallest and largest elements, number of nodes in a tree and its’ height.
LO4.4 Write code to implement features of a binary search tree, such as insertion, deletion, searching, traversals, n
LO4.5 Derive the time complexities for the above operations on a binary search tree.
LO4.6 Compare a binary search tree over other data structures that we have discussed in class.
LO4.7 Identify applications where a binary search tree will be useful.
LO4.8 Define balanced BST and explane simple balancing algorithm.
LO4.9 Define AVL Tree and explain by examples the insertion and deletion operations in it.
LO5.10 Define heap and explain its’ application.
LO5.1 Demonstrate graphs and their applications. Define an undirected graph and directed graph.
LO5.2 Explain basic notions about a graph: vertex, edge, adjacent vertices, incident edge,...
LO5.3 Know how to represent a graph using matrix and list
LO5.4 Able to apply BFS and DFS to traverse a graph
LO5.5 Write prorams to implement Graph with BFS and DFS traversals using Java
LO5.6 Explain the shortest path problem and Dijkstra’ algorithm.
LO5.7 Write program in Java to implement Dijkstra’s shortest path algorithm.
LO5.8 Define the minimum spanning tree and using the Kruskal’s algorithm to find it.
LO5.9 Define Euler cycle/path and the necessary and sufficient conditions for their existance.
LO5.10 Explain the algorithm to find Euler path / circuit using Stack and implement it in Java lannguage.
LO5.11 Define Halmilton cycle/path and able to determine them using backtracking algorithm.
LO5.12 Demonstrate the graph coloring and can apply Sequential coloring algorithm to color a graph.

LO6.1 Explain the operation and performance of selection sort applying to arrays.
LO6.2 Explain the operation and performance of insertion sort applying to arrays.
LO6.3 Explain the operation and performance of bubble sort applying to arrays.
LO6.4 Explain the operation and performance of quick sort applying to arrays.
LO6.5 Explain the operation and performance of merge sort applying to arrays.
LO6.6 Explain the operation and performance of heap sort applying to arrays.
LO6.7 Demonstrate the operation and performance of radix sort.

LO7.1 Explain the concept of "hash". Define concepts hash function and hash table and their application.
LO7.2 Demonstrate the types of hash functions: Division, Folding,...
LO7.2 Explain the collision and collision-handling.
LO7.3 Explain the open addressing method for collision-resolution: lear and quadratic probing.
LO7.4 Explain the chaining method for collision-resolution: separate chaining and Coalesced chaining.
LO7.5 Define perfect hash function and extendible hashing.

LO8.1 Describe the Text Processing problem and its’ application.

LO8.2 Explain the Brute Force Text Pattern-Matching algorithm
LO8.3 Describe the main idea of The Knuth-Morris-Pratt Algorithm
LO8.4 Explain The Huffman Coding Algorithm.
LO8.5 Explain steps needed to use The Huffman Coding Algorithm for compressing a text file.
LO8.6 Explain the LZW encoding algorithm.
LO8.7 Explain the Run-length encoding algorithm.
 Back to Syllabus

Learning
Sess. Unit Chapter Content Content in text book
Outcomes

1 1 - List Data Structures Course Introduction Course Introduction

1 1.1. Using Arrays

1.2. Singly Linked Lists
2
1.3. Circularly Linked Lists 3 Fundamental Data Structures 103
1.4. Doubly Linked Lists 3.1 Using Arrays - . 104 LO1.1 - LO1.7
3.2 Singly Linked Lists - 122
Progress test and/or 3.3 Circularly Linked Lists - 128
3
Review Exercises 3.4 Doubly Linked Lists - 132
2
4 Guiding Exercises/Assignment

5 2.1 Stacks 6 Stacks, Queues, and Deques 225

3
2-Stacks and Queues

6.1 Stacks - 226

6 Guiding Exercises/Assignment

7 2.2 Queues
4 2.3 Double-Ended Queues (Deque)
8 2.4 The Priority Queue LO2.1 - LO2.7
6.2 Queues - 238
Progress test and/or 6.3 Double-Ended Queues (Deque) - 248
9
Review Exercises 9.1 The Priority Queue Abstract Data Type - 360
5
10 Guiding Exercises/Assignment

3.1 Illustrative Examples

3.1.1 The Factorial Function
11 5 Recursion 189
3.1.2 Binary Search
3.1.3 File Systems 5.1 Illustrative Examples - 191
3.2 Analyzing Recursive Algorithms 5.1.1 The Factorial Function -191

Assignment 1 introduction
5.1.3 Binary Search - 196

Summit Assignment 1
6 3.3 Further Examples of Recursion
3- Recursion

3.3.1 Linear Recursion 5.1.4 File Systems - 198

3.3.2 Binary Recursion 5.2 Analyzing Recursive Algorithms - 202
LO3.1 - LO3.6
12 3.3.3 Multiple Recursion 5.3 Further Examples of Recursion - 206
3.4 Designing Recursive Algorithms 5.3.1 Linear Recursion - 206
3.5 Eliminating Tail Recursion 5.3.2 Binary Recursion - . 211

Progress test 1
5.3.3 Multiple Recursion - 212
Progress test and/or 5.4 Designing Recursive Algorithms - 214
13 5.6 Eliminating Tail Recursion -. 219
Review Exercises
7

529645867.xlsx
 5.3.2 Binary Recursion - . 211

Assignme

Progress test 1
Summit
5.3.3 Multiple Recursion - 212
5.4 Designing Recursive Algorithms - 214
5.6 Eliminating Tail Recursion -. 219
7
14 Guiding Exercises/Assignment

4.1 General Trees

15 4.1.1 Tree Definitions and Properties
4.1.2 The Tree Abstract Data Type 8 Trees 307
4.2 Binary Trees - . 317 8.1 General Trees - 308
8 8.1.1 Tree Definitions and Properties - 309
4.2.1 The Binary Tree Abstract Data Type
16 4.2.2 Properties of Binary Trees 8.1.2 The Tree Abstract Data Type - 312
4.3 Implementing Trees 8.2 Binary Trees - 317
4.4 Tree Traversal Algorithms 8.2.1 The Binary Tree Abstract Data Type - 319
8.2.2 Properties of Binary Trees - 321
Progress test and/or 8.3 Implementing Trees - 323
17
Review Exercises 8.4 Tree Traversal Algorithms - 334
9
18 Guiding Exercises/Assignment
4 - Trees

19 4.5 Binary Search Trees

10 4.5.1 Searching Within a Binary Search Tree
20 4.5.2 Insertions and Deletions
11.1 Binary Search Trees - 460 LO4.1 - LO4.11
11.1.1 Searching Within a Binary Search Tree - 461
Progress test and/or 11.1.2 Insertions and Deletions - 463
21
Review Exercises
11
22 Guiding Exercises/Assignment

23 4.6 Balanced Search Trees

12 4.7 AVL Trees 11.2 Balanced Search Trees - 472
24 4.8 Heaps 11.3 AVL Trees - 479
9.3 Heaps - 370
Progress test and/or 9.3.1 The Heap Data Structure - 370
25 9.3.2 Implementing a Priority Queue with a Heap -
Review Exercises
13 372
26 Guiding Exercises/Assignment

27
14 Progress test 1 and review
28

29 5.1 Graphs
5.2 Data Structures for Graphs 14 Graph Algorithms 611
5.2.1 Edge List Structure 14.1 Graphs - 612
5.2.2 Adjacency List Structure 14.1.1 The Graph ADT - 618
15
5.2.3 Adjacency Matrix Structure 14.2 Data Structures for Graphs - 619
5.3 Graph Traversals 14.2.1 Edge List Structure - 620
5.3.1 Depth-First Search 14.2.2 Adjacency List Structure - 622
5.3.3 Breadth-First Search 14.2.4 Adjacency Matrix Structure - 625
14.3 Graph Traversals - 630
14.3.1529645867.xlsx
Depth-First Search - 631
14.3.3 Breadth-First Search - 640
 5.1 Graphs
5.2 Data Structures for Graphs 14 Graph Algorithms 611
5.2.1 Edge List Structure 14.1 Graphs - 612
5.2.2 Adjacency List Structure 14.1.1 The Graph ADT - 618
15
5.2.3 Adjacency Matrix Structure 14.2 Data Structures for Graphs - 619
30 5.3 Graph Traversals 14.2.1 Edge List Structure - 620
5.3.1 Depth-First Search 14.2.2 Adjacency List Structure - 622
5.3.3 Breadth-First Search 14.2.4 Adjacency Matrix Structure - 625
14.3 Graph Traversals - 630
Progress test and/or 14.3.1 Depth-First Search - 631
31 14.3.3 Breadth-First Search - 640
Review Exercises
16
32 Guiding Exercises/Assignment

33 5.4 Shortest Paths

5 - Graphs

17 5.4.1 Weighted Graphs

34 5.4.2 Dijkstra’s Algorithm 14.6 Shortest Paths - 651 LO5.1 - LO5.12
14.6.1 Weighted Graphs - 651
Progress test and/or
35
Review Exercises 14.6.2 Dijkstra’s Algorithm - 653
18
36 Guiding Exercises/Assignment

37 5.5 Minimum Spanning Trees

5.5.1 Prim-Jarn´ık Algorithm
19 14.7 Minimum Spanning Trees - 662
38
5.5.2 Kruskal’s Algorithm
5.6. Euler's tour and Euler's cycle 14.7.1 Prim-Jarn´ık Algorithm - 664
14.7.2 Kruskal’s Algorithm - 667
Progress test and/or (Euler's tour and Euler's cycle, exercise
39 C.14.5.2)
Review Exercises
20
40 Guiding Exercises/Assignment

41 6.1 Selection-Sort

Assignment 2 introduction
6.2 Insertion-Sort

Summit Assignment 2
21
6.3 Bubble-sort 12 Sorting and Selection 531
42 6.4 Quick-Sort 9.4.1 Selection-Sort and Insertion-Sort - 386
Progress test and/or
bubble-sort (see Exercise C-7.51)
43 12.2 Quick-Sort - 544
Review Exercises
22
44 Guiding Exercises/Assignment
6 - Sorting

LO6.1 - LO6.7

rogress test 2
45 6.5 Merge-Sort
6.6 Heap-Sort
23 6.7 Linear-Time Sorting: Bucket-Sort and 12.1 Merge-Sort - 532
529645867.xlsx
Radix-Sort 9.4.2 Heap-Sort - 388
 As
6 - Sortin
LO6.1 - LO6.7

Progress test 2
6.5 Merge-Sort
6.6 Heap-Sort
23 6.7 Linear-Time Sorting: Bucket-Sort and 12.1 Merge-Sort - 532
46 Radix-Sort 9.4.2 Heap-Sort - 388
6.8 Comparing Sorting Algorithms 12.3.2 Linear-Time Sorting: Bucket-Sort and
Radix-Sort - 558
Progress test and/or 12.4 Comparing Sorting Algorithms - 561
47
Review Exercises
24
48 Guiding Exercises/Assignment

49 7.1 Hash Tables

7.2 Hash Functions
7.3 Collision-Handling 10 Maps, Hash Tables, and Skip Lists - 401
25 10.2 Hash Tables - 410
7.4 Load Factors, Rehashing, and
7 - Hashing

50 Efficiency 10.2.1 Hash Functions - 411

7.5 Java Hash Table Implementation 10.2.2 Collision-Handling Schemes - 417 LO7.1 - LO7.5
10.2.3 Load Factors, Rehashing, and Efficiency
- 420
Progress test and/or
51
Review Exercises 10.2.4 Java Hash Table Implementation - 422
26
52 Guiding Exercises/Assignment

53 8.1 Abundance of Digitized Text

8.2 Pattern-Matching Algorithms 13 Text Processing 573
8.2.1 Brute Force 13.1 Abundance of Digitized Text - 574
8 - Text Processing

8.2.2 The Knuth-Morris-Pratt Algorithm 13.2 Pattern-Matching Algorithms - 576

27
8.3 Text Compression 13.2.1 Brute Force - 576
54 8.3.1 The Huffman Coding Algorithm 13.2.3 The Knuth-Morris-Pratt Algorithm - 582
8.3.2 The LZW Algorithm LO8.1 - LO8.7
13.4 Text Compression and the Greedy Method
8.3.3 The Run-length Encoding Algorithm - 595
13.4.1 The Huffman Coding Algorithm - 596
55
Progress test and/or LZW and Run-length encoding algorithms: FU
Review Exercises slides, Slide named: "8-TextProcessing.ppt"
28
56 Assignment evaluation

57
29
58

529645867.xlsx
 59
30 Progress test 2 and review
60

FINAL EXAM

529645867.xlsx
 APPENDIX 1: COURSE SCHEDULE
ITU levels
(I= Introduce, T Student's task
= Teach, Teacher's Material Student's task after class
before class
U = Utilize)

IT

T
Text book, slides, exercises Study just learned materials, do writing
Read text book and sample practical exercises and redo practical examples and
examples do assignment 1

IT

T Text book, slides, exercises Study just learned materials, do writing

Read text book and sample practical exercises and redo practical examples and
examples do assignment 1

IT
Text book, slides, exercises Study just learned materials, do writing
Read text book and sample practical exercises and redo practical examples and
examples do assignment 1

529645867.xlsx
U

T
Text book, slides, exercises Study just learned materials, do writing
Read text book and sample practical exercises and redo practical examples and
examples do assignment 1

IT

529645867.xlsx
IT

T Text book, slides, exercises Study just learned materials, do writing

Read text book and sample practical exercises and redo practical examples and
examples do assignment 2

IT

Text book, slides, exercises Study just learned materials, do writing

Read text book and sample practical exercises and redo practical examples and
examples do assignment 2

T
529645867.xlsx
 Text book, slides, exercises Study just learned materials, do writing
Read text book and sample practical exercises and redo practical examples and
examples do assignment 2

IT
Text book, slides, exercises Study just learned materials, do writing
and sample practical exercises and redo practical examples and
examples do assignment 2

Read text book

IT
Text book, slides, exercises Study just learned materials, do writing
and sample practical exercises and redo practical examples and
examples do assignment 2

529645867.xlsx
529645867.xlsx
 Back to Syllabus ASSESSMENT STRUCTURES

Evaluation Type of Number of Scope of knowledge and skill

# Duration How?
Category questions questions of questions

Option 1:
essay or
PT 1
multiple Option 1: 15-30
LO1 - LO4
choice if multiple choice
PT 2 on paper or
1 Progress test (PT) 20'-40' Option 2: Option 2: Follow
LO5 - LO8 using computer
Questions or lecturer's
Number of questions:
Activities proposal
3-8 for each LOx
proposed by
lecturer

Option 1: a
problem
similar to
Option 1: 1 Individual or team
real one
Option 2: Follow AS1: LO1 - LO3 work, guided by
3 Assignment (AS) at home Option 2:
lecturer's AS2: LO4-LO6 instructor, submission
Questions
proposal by a given deadline
or Activities
proposed
by lecturer

Preferable
problem(s) to solve by supervised by
to be 1-2 small
5 Practical Exam 85' programming (LO1, LO2, LO4, proctor(s) sent by
marked by problems
LO6) exam board
scripts

529645867.xlsx
 questions distribution:
LO1.x: 5 - 8
LO2.x: 5 - 8
LO3.x: 3 - 7
LO4.x: 5 - 10
LO5.x: 5 - 8 supervised by
multiple
6 Final exam 60' 50 LO6.x: 3 - 5 proctor(s) sent by
choice
LO7.x: 3 - 5 exam board
LO8.x: 3 - 5

more than 70% new questions

(for the current semester);

529645867.xlsx
 Note

Progress test must be taken right after the

last lectures of required material.

Instructor has resposibility to review the

test for students after graded.

Automatic or manual evaluating

529645867.xlsx
529645867.xlsx