Introduction to Computer Science II, ICS 211

Instructor: Holger Mauch

Teaching Assistant: Zach Tomaszewski

Grading Assistant: TBA

Official Course Description:

Goals

• 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

• 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:
  1. e-mail all the required files to the TA
  2. 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
  3. 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

Lectures notes are in HTML. I usually post notes no later than the day before the lecture.

1. Tue, Aug 26. Course overview and Introduction. Chapter 1.
   Materials covered:
   • course overview
   • software development life cycle
   • modular design
   • object-oriented programming
   • debugging
2. 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
3. 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
4. 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
5. 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
6. Thu, Sep 11. Chapter 3.
   Materials covered:
   • classes and objects
   • class implementation
   • inheritance, extended classes
   • interfaces
   • exceptions
   • special methods:
     • constructor
     • equals
   • ADT List Implementation (array based)
   • Homework 3 assigned, due Thursday September 25
7. Tue, Sep 16. Chapter 4.
   Materials covered:
   • linked lists basics
   • resizable arrays
   • object references
   • class Node
   • reference-based linked list implementation
8. 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
9. Tue, Sep 23. Exam 1.
   Materials covered:
   • Exam 1
10. 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
11. Tue, Sep 30. Chapter 4.
    Materials covered:
    • solutions to exam 1
    • recursive linked list processing
    • linked list variants
    • object serialization in Java
12. Thu, Oct 02. Chapter 5.
    Materials covered:
    • 8-queens (n-queens) problem
    • backtracking
    • grammars
    • formal languages
13. 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:
14. Thu, Oct 09. Chapter 6.
    Materials covered:
    • Stack ADT
    • Stack applications
    • Stack implementations
    • Homework 5 assigned, due Thursday, October 23
15. 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
16. Thu, Oct 16. Chapter 7.
    Materials covered:
    • Queue Operations
    • Queue Implementations
    • review for exam 2
17. Tue, Oct 21. Exam 2.
    Materials covered:
    • Exam 2
18. 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
19. Tue, Oct 28. Chapter 8.
    Materials covered:
    • inheritance and polymorphism
    • packages
20. Thu, Oct 30. Chapter 8.
    Materials covered:
    • abstract classes
    • interfaces
    • iterators
21. Tue, Nov 04. Chapter 9.
    Materials covered:
    • program speed and memory efficiency
22. Thu, Nov 06. Chapter 9.
    Materials covered:
    • Big-O notation
    • growth rates
    • Homework 7 assigned, due Thursday November 20
23. Tue, Nov 11. Holiday. Veterans' Day.
    Materials covered:
    • No Class!
24. Thu, Nov 13. Chapter 9.
    Materials covered:
    • O(n²) sorting algorithms
      • selection sort
      • bubble sort
      • insertion sort
25. Tue, Nov 18. Chapter 9.
    Materials covered:
    • recursive sorting
      • merge sort
      • quicksort
    • radix sort
26. Thu, Nov 20. Chapter 10.
    Materials covered:
    • Solving recurrence relations
    • General tree definitions
    • Homework 8 assigned, due Thursday December 04
27. Tue, Nov 25. Chapter 10.
    Materials covered:
    • Binary trees
      • representations
      • classes
      • traversal
    • Binary search trees
      • definition and ADT
28. Thu, Nov 27. Thanksgiving Holiday.
    Materials covered:
    • No Class!
29. Tue, Dec 02. Chapter 10.
    Materials covered:
    • Binary search trees
      • inorder traversal
      • search, insertion, deletion
      • cost of operations
30. Thu, Dec 04. Chapter 11.
    Materials covered:
    • table operations
    • keyed items
    • table implementations:
      • sorted array
      • binary search tree
31. Tue, Dec 09. Chapter 11.
    Materials covered:
    • heaps
    • priority queues
    • priority queue implementation using heaps
    • heapsort
    • review for exam 3
32. Thu, Dec 11. Last day of instruction. Exam 3 option.
    Materials covered:
    • Exam 3
33. 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

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.