Introduction to Computer Science II

Class programs, pages in text, recitation links and powerpoint presentations

• Class Programs
• Pages in text, recitation links and .ppt files

Rules for writing programs

Instructions for course email list

Sending homeworks by email

• Where to submit your programs
• How to attach and send your programs to a Unix machine
• Tutoring at Weinstein
• Schedule for Weinstein

Writeups & Related Programs

• Stack programs

  • Evaluating postfix expressions & converting infix to postfix
  • Converting infix w/oparentheses to postfix
  • Exceptions explained.
  • StackIsEmptyException
  • StackADT w/API exception
  • StackADT w/generics

• Queue programs

  • The queue implemented as an array
  • The queue ADT class
  • Using the queue

• Linked list programs

  • Introduction to linked lists
  • stackadt.java as a linked list
  • Using a queue
  • The queueadt.java as a linked list
  • About queues

• Tree programs

  • manually producing a binary tree
  • Binary search tree using char type
  • Binary search tree using Comparable
  • BST includes insert and delete
  • calculating the height & printing the leaves
  • Counting nodes of a tree w/ void method
  • Counting the nodes of a tree w/ a function & making mirror image
  • Copying a tree
  • evaluating an expression tree
  • Testing for identical tree
  • Performing a binary search
  • A breadth-first search of a tree
  • The QueueADT file
  • Inserting balance factor in O(n)
  • Time analysis
  • 2-3 Trees
  • 2-3 Trees (London School of Economics Java version)
  • 2-3 Trees (AI Horizons version)
  • How to write tree procedures
  • Overton's tree-drawing methods

• Sort programs

  • The quick sort
  • Sort includes merge sort
  • How the Quick sort works
  • Building a heap
  • Sorting an array using heap sort
  • How the heap sort works

• Hashing programs

  • A simple hash
  • Using the API HashMap

Homeworks

• Homework #1 Evaluating infix expressions
  
• Homework #2 Solving the fifteen puzzle
  
  • The original fifteen program slightly altered
• Homework #3, Draft1, Huffman Coding

  Helpers for Homework #3, draft #1

  • Data set
  • FileStringReader(name) reads a string from file name
  • How to procede
  • The output for draft 1
• Homework #3, Draft 2, Huffman Coding compression

  Helpers for Homework #3, draft #2

  • Algorithm explained
  • The testing program(Optional)
  • The compressed file for the testing program(Optional)
  • The output for the testing program(Optional)
  • The compressed file
  • Partial output for the assigned program
• Homework #3, Draft 3, Huffman Coding using a heap
  • Partial output for draft #3
  • Diagram of steps for draft #3
  • The initialize() method for draft #3
• Homework #3, Draft #4, Using a hash table to decode Huffman code.

Honors Projects

1. A maze
   • A program that prints a maze
   • Some hints for doing the assignment
   • Example of tracing back to the entrance
2. A GUI maze
   • A program that creates a maze basis
3. Finding the shortest path in a maze
   • A program that creates a maze basis

Class Programs

a sample midterm

Sample midterm #2

Solutions for Sample midterm #2

The sample final questions