Instructor: 郁方
(Yu, Fang) Office:
商院大樓260908-1
Contact: yuf@nccu.edu.tw
Lecture Times: Thursday 9:00-12:00 (Session A) / Thursday
2:00-5:00 (Session B) Location: 研究大樓
250301
TAs: 廖文成, 99356013@nccu.edu.tw (Session A) and 邱芃瑋, 99356027@nccu.edu.tw (Session B)
Lab Times: Monday 12:00-1:00 (Session A) / Wednesday 12:00-1:00 (Session B) Location: 逸仙樓 5F 資管系PC 教室
This course focuses on the fundamentals of data structures and their implementations. Students come to understand and use data structures effectively by studying the method descriptions and applications. Students also get chance to learn how to develop Java applications using eclipse and java class library. At the end of this course, students should understand common data structures and algorithms, and be able to apply that understanding to implementing new data abstractions and using existing library components. Students should also be stronger programmers and feel comfortable programming in Java.
This course will cover basic/advanced data structures and their related algorithms with the aim of offering students a solid technical training. The (tentative) topics include:
A brief review of java programing, object oriented design, and analysis of algorithms
Basic data structures: queues, stacks, linked lists, sequences, vectors, trees, heaps, and priority queues
Advanced data structures: dictionaries, hash tables, maps, skip lists, search/balance/splay trees, directed/weighted graphs
Fundamental algorithms: divide and conquer, merge/quick/bucket/radix sort, set partition, dynamic programing, greedy method, breadth-first search, depth-first search
Advanced topics: topological sorting, pattern matching, tries, text compression, task scheduling, transitive closures, strongly connected components, shortest paths, minimum spanning trees
Homework:
- Assignments/Labs: 40% (Weekly)
- Programming Project: 30% (1-4 students as a team. The project details will be announced at the end of Sep.)
Exam:
- Final Exam (close book): 30%
Data Structures and Algorithms in Java 5th edition, by Michael T. Goodrich and Roberto Tamassia, John Wiley & Sons, Inc.
Official Website: http://www.wiley.com/go/global/goodrich
PDF Handouts [zip]
代理商：新月圖書公司/東華書局, 台北市重慶南路一段143號三樓TEL: 02-23317856
Web Search Data can be be a key tool!
[Important Dates] The team project report due date: 11/11, demo date: 12/23(A) and 12/30(B), code upload date: 1/6, and final exam on 1/13.
[Location Changed!] Our classes will be offered in the MIS PC Class Room (逸仙樓5F) on 11/4, 11/18, 12/16, 12/23(Session A) and 12/30(Session B).
Due to the full-moon festival, the lab of Session B will be on Monday (Sep. 20) 12:00-1:00pm together with the lab of Session A.
There will be no labs on Monday Sep 13th and Wednesday Sep 15th.
Find a team (1-4 students) and send the list (name and contact) to TAs before Sep. 30.
Eclipse has been installed in the PC and Mac Classrooms!
September- Get ready to programming!
9/16: Opening: A brief overview of Java and eclipse [Lec0] [Lec1]
- Text Book (TB) Chapter 1
9/23: Introduction: Object-oriented design and abstract data type [Lec2]
- TB Chapter 2
9/30: Text/Pattern matching and Class project announcements [Lec3]
- TB Chapter 12
- Project: Smart Ranking
October – Introduce basic data structures and their implementations
10/7: Linked Lists [Lec4]
- TB Chapter 3 and Chapter 6
10/14: Queues and Stacks [Lec5]
- TB Chapter 5 and Chapter 8
10/21: Trees [Lec6]
-TB Chapter 7
10/28: Heaps [Lec7]
-TB Chapter 8
November – Introduce fundamental algorithms and their analyses
11/4: Analysis of Algorithms, HW Review [Lec8][PC Classroom]
- TB Chapter 4
11/11: Divide and Conquer, Merge/Quick Sort, Recurrence Equations [Lec9] [Project Proposal]
- TB Chapter 11
11/18: Dynamic Programming: Matrix Chain Production and Longest Common Subsequence [Lec10][PC Classroom]
-TB Chapter 12
11/25: Search Trees
-TB Chapter 10
December – Step on advanced data structures and other topics
12/2: Hash tables
12/9: Dictionaries and Maps
12/16: Graphs (1) [PC Classroom]
12/23: Project Demo [PC Classroom: Session A] / Graphs (2) [Session B]
12/30: Graphs (2) [Session A] / Project Demo [PC Classroom: Session B]
January – Exam and Demo
1/6: Selected Topic (to be announced)
1/13: Final Exam
Eclipse download [official website]