Introduction to Computer Science II, ICS 211

This page is subject to change without notice -- please reload it in your browser if an item that might affect you may have changed.

The organization of the course is described here. Please review it at the beginning of the course and occasionally during the course. It includes information about course goals, class time and location, contacting the instructor, office hours, the textbook, grading, and the no cheating policy.

If you have any questions, please contact the instructor.

Schedule

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

• Tue, Jan 15, class introductions, course summary
  Outline
  • introductions
  • course overview
  extra credit assignment, due in class Jan 17th (preferable) or Jan 22nd.
  Some links for this class:
  • Richard Medina, TA for this class
  • you might benefit from knowing about Repetitive Motion Injury
  • Java Tutorial (or download), from Sun Microsystems
• Thu, Jan 17, Java review, Appendix A and Chapter 2-2.4
  Outline
  • announcements
  • Java review: basics, exceptions, variables, arrays, compound statements
  Homework 1 assigned, due Friday January 25th.
  Some links for this class:
  • Java Platform, Standard Edition
  • Java 2 Edition 5.0 API, a good guide to the standard classes, and a search engine for this documentation. See also this collection of Java notes, by Fred Swartz, and this Intro to Programming using Java, from David J. Eck.
  • also an introduction to Java Applet Animation
  • Java coding standard, required for this class
  • Eclipse IDE home page and download and setup instructions
  • Netbeans IDE home page
  • Code examples for today's lecture
• Tue Jan 22, Recursion, Chapter 7.
  Outline
  • Java review: arrays, if statements, booleans, comparisons, while and for loops
  • recursive thinking
  • recursion in Java
  • principles of recursion
  • examples
  • Java command line arguments
  Code examples for today's lecture
• Thu Jan 24, Recursion, Chapter 7.
  Outline
  • recursion reminder
  • examples of recursion
  • Java command line arguments
  • recursion with return values
  • examples: fibonacci, factorial, power
  • infinite recursion
  • debugging
  Homework 2 assigned, due Friday February 1st.
  Some links for this class:
  • Code examples for today's lecture
  • fibonacci numbers
  • first computer bug
• Tue Jan 29. Testing and debugging, Chapter2.1, 2.5, 2.6. Big O notation, Chapter 2.8
  Outline
  • infinite recursion
  • debugging
  • runtime of programs
  • program runtime analysis
  • big O notation
  • sequential and binary search
  Links for this class:
  • Code examples for today's lecture
  • links for Java programming on Windows without an IDE, including Compiling from the command line in windows and Using TextPad
• Thu Jan 31. Abstract Data Types, Chapters 1.2-1.3
  Outline
  • sequential and binary search
  • program design
  • abstraction
  • Java interfaces
  • abstract data types
  • Java classes -- review
  • scope
  • inheritance
  • exceptions -- details
  Homework 3 assigned, due Friday February 8th.
  Code examples for today's lecture
• Tue Feb 5. Stacks, Chapter 5.
  Outline
  • Java classes -- review
  • scope
  • inheritance
  • exceptions -- details
  • stacks
  • stack ADT
  • method signatures
  • array stack implementation
  • Java types and operators
  • expressions, parsing, evaluating
  Code examples for today's lecture
• Thu Feb 7. Stacks implemented using linked lists, Chapter 5.
  Outline
  • Java types and operators
  • expressions, parsing, evaluating
  • File I/O
  • linked list implementation of stack ADT
  • nodes
  • linked lists
  • stack applications
  Homework 4 assigned, due Friday February 15th.
  Code examples for today's lecture and assignment
• Tue Feb 12. Generic Types, Chapter 4.
  Outline
  • stack applications
  • shopping list implementation
  • generic types
  • generic linked lists
  • menu implementation
  Code examples for today's lecture
• Thu Feb 14. Ordered linked lists, Chapter 4.7
  Outline
  • menu implementation
  • database
  • ordered linked lists
  • Comparable interface
  • ordered linked list add
  Code examples for today's lecture
• Tue Feb 19. Exam review.
  Outline
  • ordered linked list add
  • exam review:
    • Java constructs
    • Abstract Data Types
    • stacks and stack implementations
    • run-time analysis and big-O
    • objects, references, and pointers
    • generic classes
• Thu Feb 21, Exam 1, on all the material in the lectures, the assignments, and Chapters 1.2-1.3, 2, 3-3.2, 4, 5, and 7 in the textbook.
  Homework 5 assigned, due Friday February 29th.
• Tue Feb 26. Post-exam review.
  Outline
  • post-exam review
  • iterators
  • iterator use
  • iterator implementation
• Thu Feb 28. Iterators, Chapter 4.5. Collections, Chapter 4.7. Queues, chapter 6.
  Outline
  • iterators
  • iterator use
  • iterator implementation
  • queues
  • queue interface
  • queue implementation: array queue
  • using queues
  Links for this class:
  • Code examples for today's lecture
  • Iterator interface
  • Queue interface
  • Collection interface
  Homework 6 assigned, due Sunday March 9th.
• Tue Mar 4. Queues, chapter 6.
  Outline
  • queue interface (reminder)
  • queue implementation: array queue
  • using queues
  • queue implementation: linked queues
  • queue exercises
  Code examples for today's lecture
• Thu Mar 6 Queues, chapter 6. Binary search, trees. Chapter 7.3, 8.1.
  Outline
  • queue implementation: linked queues
  • queue exercises
  • binary search
  • trees
  • binary search trees
  • tree traversal
  Homework 7 assigned, due Sunday March 16th.
• Tue Mar 11. Binary Trees. Chapter 8.2, 8.3.
  Outline
  • trees, continued
  • binary search trees
  • tree traversal
  • binary search tree algorithms: add, remove, traverse
  • binary node class
  Links for this class:
  • Code example for today's lecture
  • tree traversal applet (from Prof. Jarc of University of Maryland College Park, and suggested by Richard Medina)
• Thu Mar 13. Binary Search Trees. Chapter 8.4.
  Outline
  • binary search tree algorithms: add, remove, traverse
  • binary node class
  • binary search tree implementation
  • databases
  • runtime analysis
  Code example for today's lecture
  Homework 8 assigned, due Sunday March 30th.
• Tue Mar 18. Chapter 8.4, 8.5.
  Outline
  • binary search tree implementation: remove
  • databases
  • runtime analysis
  • heaps
  Code examples for today's lecture are the same as for the March 13 lecture.
• Thu Mar 20. Chapter 8.4, 8.5.
  Outline
  • databases
  • binary search tree runtime analysis
  • breadth-first traversal
  • heaps
• Tue Apr 1. Exam review.
  Outline
  • exam review
  • databases
  • iterators
  • invariants
  • queues
  • binary search
  • binary trees
  • binary search trees and operations
  • tree traversal
  • heaps
  • runtime analysis
  • ability to implement needed methods
  • recursion
• Thu Apr 3. Exam 2, on all the material since Exam 1 in the lectures, the assignments, the quizzes, and Chapters 4.5, 4.7, 6, 7.3, 8.1-8.5 (except priority queues). The exam will assume, but not specifically test, general familiarity with the material in Chapter 7 and all material in the first exam.
  Homework 9 assigned, due Sunday April 13th.
• Tue Apr 8. Exam 2 review, Chapter 8.5.
  Outline
  • exam 2 review
  • heap reminder
• Thu Apr 10. Priority Queues, Chapter 8.5. Sorting, Chapter 10.
  Outline
  • priority queues implementation
  • equality and comparisons in Java
  • sorting
  • selection sort
  • bubble sort
  • insertion sort
  Homework 10 assigned, due Sunday April 20th.
• Tue Apr 15. Sorting, Chapter 10.
  Outline
  • insertion sort
  • shell sort
  • merging sorted data
• Thu Apr 17. Sorting, Chapter 10.
  Outline
  • merge sort
  • heap sort
  • quick sort
  Homework 11 assigned, due Sunday April 27th.
• Tue Apr 22. Hashing, Chapter 9.3 and 9.4.
  Outline
  • hash tables
  • hash functions
  • open addressing
  • chained hashing
  Links for this class:
  • a much more in-depth explanation of hash functions can be found here, with a more complex (and more effective) hash function here.
  • a much more in-depth explanation of hash functions, see here, which includes this link to a more effective (and more complex) hash functions.
  • this link compares a simple hash table implementation to an advanced 256-ary balanced tree implementation, and this link is a brief explanation of the tree data structure.
  • One blogger's opinion of what is wrong with hash tables, with some sensible responses at the end.
• Thu Apr 24. Hashing, Chapter 9.3 and 9.4. Vectors, Chapter 4.1-4.3.
  Outline
  • open addressing
  • chained hashing
  • vectors
  • vector implementation
  • arrayList
  Homework 12 assigned, due Sunday May 4th.
• Tue Apr 29. Huffman coding and Huffman trees. Chapter 8.6.
  Outline
  • huffman coding
  • huffman trees
  • implementation
• Thu May 1. Balanced Trees, Chapter 11 (material not required on final).
  Outline
  • balanced trees
  • AVL trees
  • splay trees
  • red-black trees
  • 2-3 trees
  • B-trees
• Tue May 6. Exam review.
  Outline
  • course review
  • exam 1 material: Java, ADTs, stacks, run-time big-O, objects, references and pointers, recursion, generic types and container classes
  • exam 2 material: linked lists, queues, binary trees, binary search, binary search trees, tree traversal, invariants
  • heaps, priority queues, hashing, sorting, huffman coding