Type of Credit: Required
Credit(s)
Number of Students
This course covers the fundamental data structures, and their implementations and applications. Students come to understand how to use data structures effectively, knowing their concepts and programs from method descriptions and applications. Students also get chance to learn how to develop Java applications using eclipse and java class library.
We will discuss basic and advance 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
Students are required to implement a middle size system to relaize what they have learned in the course. The course is qulified to the adjustable course. There will be no lectures on Week 2, 16, and 18.
能力項目說明
The objective of this course is to offer students a solid training on object-oriented prorgaming consepts and skills. At the end of this course, students should understand common data structures and algorithms, and be able to apply that understanding to investigating new data abstractions, as well as using existing library components to develop middle-size applications. Students should also feel comfortable while programming in Java.
Lectures/Schedules (Subject to change)
彈性上課/No Lectures: Week 17 and 18.
September- Get ready to programming!
Week 1. [3/3 hours] Opening: A brief overview of Java and eclipse [Lec0] [Lec1]
- Text Book (TB) Chapter 1
Week 2. [6 hours] Java environement setup. [彈性上課/No Lectures]
Week 3. [3/3 hours] Introduction: Object-oriented design and abstract data type [Lec2]
- TB Chapter 2
Week 4. [3/3 hours] Text matching and Class project announcements [Lec3]
- TB Chapter 12
- Project: Intelligent Searching-BeatGoogle!
October – Introduce basic data structures and their implementations
Week 5. [3/3 hours] Linked List [Lec4]
- TB Chapter 3 and Chapter 6
Week 6. [3/3 hours] Queues and Stacks [Lec5]
- TB Chapter 5 and Chapter
Week 7. [3/3 hours] Trees [Lec6]
-TB Chapter 7.
-Lab programming test
Week 8. [3/3 hours] Heaps [Lec7]
-TB Chapter 8
November – Introduce fundamental algorithms and their analyses
Week 9. [3/3 hours] BigO, Divide and Conquer [Lec8]
-TB Chapter 4, 11
Week 10. [3/3 hours] Merge/Quick Sort (Recurrence Equations) [Lec9]
-TB Chapter 4, 11
Week 11. [3/3 hours] Dynamic Programming [Lec10]
-TB Chapter 12
Week 12. [3/12 hours] Midterm Exam
-Lecture 1-9 TB Chapter 1-8, 11-12
December – Step on advance data structures
Week 13. [3/3 hours] Binary Search Trees [Lec11]
-TB Chapter 10
Week 14. [3/3 hours] Maps and Hash tables [Lec12] and Dictionaries and Skip Lists [Lec13]
-TB Chapter 9 and 10
Week 15. [3/6 hours] Graphics I [Lec14] and Graphics II [Lec15]
-TB Chapter 13, 15
January – Talk and Demo
Week 16. [12 hours] Project Implementation: Let's Beat Google (Project Demo)
Week 17. [3/12 hours] Project Implementation: Let's Beat Google (Project Discussion) [彈性上課/No Lectures]
Week 18. [12 hours] Project Implementation: Let's Beat Google (Final Report and Code Uplaod) [彈性上課/No Lectures]
Homework:
- Assignments/Labs: 40% (Weekly)
- Programming Project: 30% - including project proposal (20%), demo (40%) and implementation (40%). 3-5 students as a team. The project details will be announced at the early of Oct.
Exam:
- Midterm Exam (close book): 30%
*Please note that all slides/exams will be written in English despite Chinese or English sessions. Students are strongly encouraged to write their proposal and present their project in English.
Text Book
Data Structures and Algorithms in Java 6th 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
The course web page: http://soslab.nccu.edu.tw/Courses.html Links that might be useful: •Introduction to programming in Java [open course by MIT] •Java Applet Tutorial [oracle] •An svn tutorial [ibm] •Eclipse download [official website] •An eclipse tutorial [eclipse]