Java程序辅导

CITS2200 : Data Structures and Algorithms
Prof. Amitava Datta
Room 1.07
amitava.datta@uwa.edu.au
A unit about space, time, and complexity.
Handbook Description
At the core of most computer applications is the storage and retrieval of
information. The way that the stored data is structured has a strong impact
on what can be retrieved, how quickly it can be retrieved, and how much space
it occupies. The use of generic structures, or abstract data types (ADTs), to
encapsulate the data also allows software engineering principles of independent
modification, extension and reuse.
This unit studies the specification, implementations and time and space per-
formance of a range of commonly-used ADTs and corresponding algorithms in
an object-oriented setting. The aim is to provide students with the background
needed both to implement their own ADTs where necessary, and to select and
use appropriate ADTs from object-oriented libraries where suitable.
1
Unit Outcomes
At the end of the unit you will:
1. be able to programme proficiently in Java.
2. be able to identify and abstract computational problems.
3. be able to identify, analyse and implement and apply a range of common
data structures.
4. know important algorithmic techniques and a range of useful algorithms.
5. be able to implement algorithms as a solution to any solvable problem.
6. be able to analyse the complexity and correctness of algorithms and data
structures.
7. be able to design correct and efficient algorithms.
The course will proceed by covering a number of algorithms; as they are
covered, the general algorithmic technique involved will be highlighted, and the
role of appropriate data structures, and efficient implementation considered.
2
Timetable
• Lectures
– 3pm-4pm Tuesdays, Austin Lecture Theatre
– 8am-9am Thursdays, Austin Lecture Theatre
• Workshops
– 9am-10am Thursdays, Austin Lecture Theatre
• Laboratories
– 4pm-6pm Tuesdays, CSSE Lab 2.03
– 8am-10pm Wednesdays, CSSE Lab 2.03
– 10am-12pm Wednesdays, CSSE Lab 2.03
– 12pm-2pm Wednesdays, CSSE Lab 2.03
• Consultation
– 2pm-3pm Friday, CSSE Room 1.07
You may also get help via the help2200 electronic forum — a public discussion
board for all queries relating to the unit.
3
Assessment
Assessment Date % of Final Mark
Laboratory work Starting Week 2 20%
Mid-semester test Thursday, Week 7 10%
Project Weeks 10-13 20%
Final examination June examination period 50%
References
• CSSE, Data Structures and Algorithms Notes , 2012.
• CSSE, Algorithms Notes , 2012
• Mark Weiss, Data Structures and Problem Solving using Java, Addison
Wesley, 1998.
• Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, In-
troduction to Algorithms, 3rd Ed, MIT Press, 2009 (CITS3210 textbook).
4
Further Reading
There are many different books on the subject of data structures as well as
books on the subject of Java, including some which combine the two. A few
examples of books worth looking at include:
• Kenneth Lambert and Martin Osborne, Java: A Framework for Program
Design and Data Structures, 2nd Ed, Thomson, 2004 (previous textbook).
• Sartaj Sahni, Data Structures, Algorithms, and Applications in Java, Mc-
Graw Hill, 2000.
• Mark Weiss, Data Structures and Algorithm Analysis in Java, Addison
Wesley, 1999.
• Adam Drozdek, Data Structures and Algorithms in Java, Thomson, 2005.
• Janet Prichard and Frank Carrano, Data Abstraction & Problem Solving
with Java: Walls & Mirrors, 3rd Ed, Addison Wesley, 2011.
5
Topics Of Study
We will study the following topics this semester:
1. Intro to Data Structures 2. Intro to Algorithms
3. Stacks and Queues 4. Data Abstraction
5. Lists 6. Complexity Analysis
7. Objects and Iterators 8. Trees and Graphs
9. Tree Search 10. Priority Queues
11. Optimisation Algorithms 12. Search Trees
13. Hash Tables 14. Dynamic Programming
6
What You Should Do This Week
1. Get set up to use the School’s Computer Systems:
https://secure.csse.uwa.edu.au/run/csentry?pw1=yes
2. Begin to familiarise yourself with the Unit’s web site.
3. Work through An Introduction to MacOSX and the first labsheet.
4. Revise Java.
Laboratory and tutorial classes start next week!
7