Java程序辅导

CITS2200 Data Structures and Algorithms
Topic 1
Welcome
Dr. Luigi Barone
Room 2.12
luigi@csse.uwa.edu.au
Dr. Rowan Davies
Room 2.16
rowan@csse.uwa.edu.au
A unit about space, time, and integrity .
c© Cara MacNish & Tim French CITS2200 Welcome Slide 1
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 performance
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.
c© Cara MacNish & Tim French CITS2200 Welcome Slide 2
This Lecture
• Introductory information — teaching sessions, teaching staff, assessment, lab
rules, unit software, on-line resources, teaching and learning agreement
• Introduction to ADT’s
Wikipedia disambiguation:
1. Abstract data type: a computer programming term
2. Asynchronous data transfer: a method of transferring data
3. Automatic double tracking: an audio recording technology invented for
The Beatles
4. American Discovery Trail: a coast-to-coast hiking trail across the mid-tier
of the United States.
5. Average Daily Traffic: to show the volume of traffic on a road in trans-
portation planning
6. Active Denial Technology: also known as the pain ray
c© Cara MacNish & Tim French CITS2200 Welcome Slide 3
Timetable
• Lectures
– 2pm-3pm Tuesdays, Webb Lecture Theatre
– 10pm-11am Fridays, Gentilli Lecture Theatre
• Tutorials
– 2pm-3pm Thursdays, Engineering Lecture Theatre 1
• Laboratories
– 10am-12pm Thursdays, CSSE Lab 2.01
– 12pm-2pm Thursdays, CSSE Lab 2.01
– 3pm-5pm Thursdays, CSSE Lab 2.01
– Only the hours 12noon-1pm and 3pm-4pm are supervised
• Consultation
– Luigi: 3pm-5pm Tuesdays, CSSE Room 2.12
– Rowan: 2pm-4pm Mondays, CSSE Room 2.16
c© Cara MacNish & Tim French CITS2200 Welcome Slide 4
Help Forum
Aside from the aforementioned activities, you may also get help via the help2200
electronic forum — a public discussion board for all queries relating to the unit.
Assessment
Assessment Date % of Final Mark
Laboratory work Selected weeks, starting Week 4 10%
Mid-semester test Tuesday, Week 8 10%
Project Weeks 10-13 20%
Final examination June examination period 60%
References
Cara MacNish & Tim French, Data Structures and Algorithms Notes, 2008.
c© Cara MacNish & Tim French CITS2200 Welcome Slide 5
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).
Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, Introduction
to Algorithms, 3rd Ed, MIT Press, 2009 (CITS3210 textbook).
Sartaj Sahni, Data Structures, Algorithms, and Applications in Java, McGraw Hill,
2000.
Mark Weiss, Data Structures and Problem Solving using Java, Addison Wesley,
1998.
Mark Weiss, Data Structures and Algorithm Analysis in Java, Addison Wesley, 1999.
Adam Drozdek, Data Structures and Algorithms in Java, Thomson, 2005.
c© Cara MacNish & Tim French CITS2200 Welcome Slide 6
Michael Gooodrich and Roberto Tamassia, Data Structures & Algorithms in Java,
Wiley, 1998.
Robert Lafore, Data Structures and Algorithms in Java, Wiley, 2005.
Janet Prichard and Frank Carrano, Data Abstraction & Problem Solving with Java:
Walls & Mirrors, 3rd Ed, Addison Wesley, 2011.
c© Cara MacNish & Tim French CITS2200 Welcome Slide 7
Topics Of Study
We will study the following topics this semester:
1. Introduction 2. Java Revision
3. Recursive Data Structures 4. Abstract Data Types
5. Queues and Stacks 6. Complexity Analysis
7. Objects and Iterators 8. Lists
9. Maps and Binary Search 10. Trees
11. Sets, Tables, and Dictionaries 12. Priority Queues
13. Hash Tables 14. Revision
c© Cara MacNish & Tim French CITS2200 Welcome Slide 8
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. Have a go at An Introduction to MacOSX and the first labsheet.
4. Start brushing up your Java in preparation.
Laboratory and tutorial classes start Thursday, Week 2.
c© Cara MacNish & Tim French CITS2200 Welcome Slide 9