| Course Name | Year | Term | Period | Faculty / Graduate School | All Instructors | Credits |
|---|---|---|---|---|---|---|
| 34616:Data Structures and Algorithms (G1) | 2019 | Spring | Fri3 | College of Information Science and Engineering | BAI YANG | 2 |
Campus
Class Venue
Language
Course Outline and Method
Student Attainment Objectives
* understand and be able to explain the basics of problem solving using computer's algorithms
* understand and be able to explain the basics of algorithm complexity analysis.
* be able to select and apply the most appropriate data structures and algorithms to solve a given problem.
* understand and be able to effectively implement various data structures and algorithms for problem solving.
Recommended Preparatory Course
'Programming Language'
'Programming Practice I'
'Computing Mathematics'
'Mathematical Foundations for Computer Science'
Course Schedule
| Lecture/Instructor（When there are multiple instructors) | Theme |
|---|---|
| Keyword, References and Supplementary Information | |
| w01 | Algorithm Analysis (Chapter 3) |
asymptotic analysis, big-oh notation, comparative analysis |
|
| w02 | Recursion (Chapter 4) |
examples, analysis, tail recursion, linear/binary/multiple recursion |
|
| w03 | Array-Based Sequences (Chapter 5) |
python sequence types, low-level arrays, dynamic arrays, multi-dimensional data sets, examples |
|
| w04 | Stacks, Queues, and Deques (Chapter 6) |
definitions, implementations, reversing data using stacks, circular arrays |
|
| w05 | Linked Lists (Chapter 7) |
singly/doubly/circularly linked lists, positional lists, sorting positional lists, link-based vs array-based sequences |
|
| w06 | Trees (Chapter 8) |
definition, depth and height, binary trees, tree traversals algortihms |
|
| w07 | Priority Queues (Chapter 9) |
definition, heaps, sorting with a priority queue |
|
| w08 | Mid-term Review and Quiz |
w01-w08 review and short test |
|
| w09 | Maps, Hash Tables, and Skip Lists (Chapter 10) |
maps and dictionaries, hash functions, sorted maps, skip list, sets, multisets and multimaps |
|
| w10 | Search Trees (Chapter 11) |
binary/balanced search trees, AVL/Splay/(2,4)/Red-Black Trees |
|
| w11 | Sorting and Selection (Chapter 12) |
merge sort, quick sort, selection prune-and-search |
|
| w12 | Text Processing (Chapter 13) |
Knuth-Morris-Pratt pattern matching algorithm, dynamic programming, text compression, tries |
|
| w13 | Graph Algorithms (Chapter 14) |
definition, data structures for graphs, graph traversals, shortest paths, dijkstra's algortitm, minimum spanning trees |
|
| w14 | Memory Management and B-Trees (Chapter 15) |
memory allocation, garbage collection, memory hierachies and caching, external searching and B-trees, external memory sorting |
|
| w15 | Main algorithms and data structures review |
review and applications (examples) of the algorithms and data structures covered in the course |
Class Format
Recommendations for Private Study
Grade Evaluation Method
| Kind | Percentage | Grading Criteria etc. |
|---|---|---|
| Final Examination (Written) | 50 | Ability to solve the questions provided in the final exam |
| Report Examination (A report to be submitted by the unified deadline) |
||
| Exams and/or Reports other than those stated above, and Continuous Assessment (Evaluation of Everyday Performance in Class) |
50 | Attendance, assignments and the mid-term exam |
Grade Evaluation Method （Note）
Advice to Students on Study and Research Methods
Textbooks
| Title | Author | Publisher | ISBN Code | Comment |
|---|---|---|---|---|
| Data Structures and Algorithms in Python Paperback – 2016 | Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser | Wiley india Pvt. Ltd; 1st edition (2016) | ISBN-10: 812656217X |
Textbooks （Frequency of Use, Note）
Reference Books
| Title | Author | Publisher | ISBN Code | Comment |
|---|---|---|---|---|
| Introduction to Algorithms, 3rd Edition (MIT Press) 3rd Edition | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein | The MIT Press; 3rd edition (July 31, 2009) | ISBN-10: 0262033844 | |
| Data Structures and Algorithms in Java 6th Edition | Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser | Wiley; 6 edition (January 28, 2014) | ISBN-10: 1118771338 | |
| Problem Solving with Algorithms and Data Structures Using Python (2nd Ed) (online!) | Bradley N. Miller, David L. Ranum | Franklin, Beedle & Associates; 2nd edition (August 22, 2011) | ISBN-10: 1590282574 | http://interactivepython.org/runestone/static/pythonds/index.html |
| Python Algorithms: Mastering Basic Algorithms in the Python Language 2nd ed. Edition | Magnus Lie Hetland | Apress; 2nd ed. edition (September 4, 2014) | ISBN-10: 148420056X | |
| Data Structures and Algorithms with Python 2015th Edition | Kent D. Lee, Steve Hubbard | Springer; 2015 edition (January 13, 2015) | ISBN-10: 3319130714 |