Introduction to Computer Science II, ICS 211
This course homepage is http://www2.hawaii.edu/~tp_250/Welcome.html
Office is in POST 306C, telephone 956-3960, e-mail tp_250@hawaii.edu. Office hours are Tuesday
and Thursday from 2:00 to 3:00, and by appointment.
Office is in POST 314-2, no telephone, e-mail ztomasze@hawaii.edu. Zach will be teaching
the lab, Tuesday and Thursday 9:00 to 10:15, in POST 319. His office hours are
Tuesday 3:00 to 4:00, Thursday 12:00 to 1:00 , and by appointment.
Grading Assistant: TBA
He/she will assist Holger and Zach with the grading.
Official Course Description:
Algorithms and their complexity, introduction to software engineering, recursion, data structures (linked lists, queues, stacks, trees), searching and sorting algorithms.
Goals
In this course, students will:
- Learn standard data structures, including linked lists, stacks, queues,
and trees.
- Learn standard algorithms for sorting and searching
- Be exposed to the basics of algorithm analysis and complexity.
- Be exposed to software engineering techniques such as: abstract data
types, separation of definition and implementation.
- Learn to use Java for more complex programming projects than those in ICS
111.
Organization
This course has
- lectures -- class participation is encouraged
- labs -- class participation is encouraged
labs start on August 28, 2003 (note the change!)
- homeworks -- all homeworks must follow this simplified Java
Coding Standard. (SUN's code
conventions are more comprehensive - check them out sometimes). Your TA
will set the detailed rules of how to turn in the homework. It will be explained
to you in the lab. In general, the following applies. A late homework gets
no credit. The due date will always fall on a lab day, and you should have
your homework ready for turn in by the end of the lab session. Homeworks must
be turned in, in the following way:
- e-mail all the required files to the TA
- all programs must be able to execute on uhunix2 using javac2
and java2, but you may develop on the lab machines using any
environment you are comfortable with
- Your TA might give you special instructions, which override these rules,
e.g. check your homework right away in the lab, or allow you to turn in
a printout, etc.
- pop up quizzes -- duration is 5-10 minutes and they start at the beginning
of class.
- three exams
All quizzes and exams are closed books, closed notes unless otherwise noted.
Please check your current grades frequently,
and report any errors immediately to me or the TA.
A cumulative score of 90% will guarantee an A in the course, 80% a B, 70% a
C, and 60% a D. Depending on the performance of the class as a whole, these
values might be adjusted to the students' advantage. The plus/minus grading
system will be used.
Here is the detailed grading policy.
The textbook is "Data Abstraction and Problem Solving with Java -- Walls and
Mirrors", by Frank Carrano and Janet Prichard (Addison-Wesley, 2001). ISBN is 0201702207. The textbook is available from the UH bookstore.
The lectures are Tuesdays and Thursdays at 10:30 am in POST126, starting August 26, 2003.
The labs are Tuesdays and Thursdays at 9:00 am in POST 319, starting September 02, 2003.
I strongly recommend that you make use of your lecture time and your lab time to develop your understanding of the material, to get useful information for your homework, to ask questions, and to take part in discussions. However I do not plan to check for attendance.
Cheating Policy: any cheating will result in a grade of 0 for the
assignment, quiz, or exam, and possibly a grade of F for the course. There is to be no collaboration
whatsoever on homeworks, quizzes, or exams (you may study together, but anything you turn
in, must be entirely your own intellectual contribution). As practicing computer
scientists, you will learn to work in groups, but don't try it in this class if
you want to pass.
Tentative Schedule
This schedule is subject to change.
Lectures notes are in HTML. I usually post notes no later than the day before
the lecture.
- Tue, Aug 26. Course overview and Introduction. Chapter 1.
Materials covered:
- course overview
- software development life cycle
- modular design
- object-oriented programming
- debugging
- Thu, Aug 28. Java Review. Appendix A.
Materials covered:
- program structure
- language basics
- selection statements
- iteration statements
- file input and output
- Other programming issues
- Homework 1 assigned, due Thursday September
04
- Tue, Sep 02. Chapter 2.
Materials covered:
- infinite Mirrors
- recursive-valued methods: factorial
- recursive void methods: printing backwards
- counting rabbits: fibonacci
- counting k out of n
- Thu, Sep 04. Chapter 2.
Materials covered:
- searching
- binary search
- k-th smallest item in an array
- recursion and efficiency
- Homework 2 assigned, due Thursday September
11
- Tue, Sep 09. Chapter 3.
Materials
covered:
- building walls
- ADT specification:
- collections of data: add, remove, ask questions about the data
- the ADT List
- the ADT Sorted List
- designing the specification
- date ADT, appointment book ADT
- axioms
- Thu, Sep 11. Chapter 3.
Materials covered:
- classes and objects
- class implementation
- inheritance, extended classes
- interfaces
- exceptions
- special methods:
- ADT List Implementation (array based)
- Homework 3
assigned, due Thursday September 25
- Tue, Sep 16. Chapter 4.
Materials covered:
- linked lists basics
- resizable arrays
- object references
- class Node
- reference-based linked list implementation
- Thu, Sep 18. Chapter 4.
Materials covered:
- linked list implementation
- displaying the contents of a linked list (traversal)
- linked list manipulation
- inserting a node into a linked list
- deleting a node from a linked list
- reference-based implementation of ADT List
- array-based vs. reference-based lists
- review for exam 1
- Tue, Sep 23. Exam 1.
Materials covered:
- Thu, Sep 25. Chapter 4.
Materials covered:
- reference-based implementation of ADT List
- array-based vs. reference-based lists
- passing a linked list to a method
- Homework 4
assigned, due Thursday October 09
- Tue, Sep 30. Chapter 4.
Materials covered:
- solutions to exam 1
- recursive linked list processing
- linked list variants
- object serialization in Java
- Thu, Oct 02. Chapter 5.
Materials covered:
- 8-queens (n-queens) problem
- backtracking
- grammars
- formal languages
- Tue, Oct 07. Chapter 5.
Materials covered:
- algebraic expressions
- infix, prefix and postfix expressions
- recognizing prefix expressions
- towers of Hanoi problem and solution
- proofs about programs using mathematical induction:
- Thu, Oct 09. Chapter 6.
Materials covered:
- Stack ADT
- Stack applications
- Stack implementations
- Homework 5
assigned, due Thursday, October 23
- Tue, Oct 14. Chapter 6.
Materials covered:
- array based stack vs. stack based on linked list
- arithmetic expressions
- recursion and iteration
- exhaustive search
- relationship between stacks and recursion
- Thu, Oct 16. Chapter 7.
Materials covered:
- Queue Operations
- Queue Implementations
- review for exam 2
- Tue, Oct 21. Exam 2.
Materials covered:
- Thu, Oct 23. Chapter 7.
Materials covered:
- solutions to exam 2
- array based queue implementation
- queue applications
- simulation
- October 24 is the last day to withdraw
- Homework 6
assigned, due Thursday, November 06
- Tue, Oct 28. Chapter 8.
Materials covered:
- inheritance and polymorphism
- packages
- Thu, Oct 30. Chapter 8.
Materials covered:
- abstract classes
- interfaces
- iterators
- Tue, Nov 04. Chapter 9.
Materials
covered:
- program speed and memory efficiency
- Thu, Nov 06. Chapter 9.
Materials
covered:
- Big-O notation
- growth rates
- Homework 7
assigned, due Thursday November 20
- Tue, Nov 11. Holiday. Veterans' Day.
Materials
covered:
- Thu, Nov 13. Chapter 9.
Materials
covered:
- O(n^{2}) sorting algorithms
- selection sort
- bubble sort
- insertion sort
- Tue, Nov 18. Chapter 9.
Materials
covered:
- recursive sorting
- radix sort
- Thu, Nov 20. Chapter 10.
Materials
covered:
- Solving recurrence relations
- General tree definitions
- Homework
8 assigned, due Thursday December 04
- Tue, Nov 25. Chapter 10.
Materials
covered:
- Binary trees
- representations
- classes
- traversal
- Binary search trees
- Thu, Nov 27. Thanksgiving Holiday.
Materials
covered:
- Tue, Dec 02. Chapter 10.
Materials
covered:
- Binary search trees
- inorder traversal
- search, insertion, deletion
- cost of operations
- Thu, Dec 04. Chapter 11.
Materials
covered:
- table operations
- keyed items
- table implementations:
- sorted array
- binary search tree
- Tue, Dec 09. Chapter 11.
Materials
covered:
- heaps
- priority queues
- priority queue implementation using heaps
- heapsort
- review for exam 3
- Thu, Dec 11. Last day of instruction. Exam 3 option.
Materials
covered:
- Thu, Dec 18. 09:45-11:45. Discussion. Final Exam option.
Materials
covered:
- solutions to exam 3
- discussion
- no mandatory final exam if you took exam 3
- final exam mandatory if you did not take exam 3
Feedback
I appreciate feedback! Please send me mail at tp_250@hawaii.edu with any comments, or if
you notice any mistakes, or if you have problems accessing any of these links.
Miscellaneous
Documentation of the Java 2 Platform, Standard
Edition, v 1.4.2 ("Java 2 API").
Philip Johnson's Java
coding standards
The sourcecode of the textbook.