Introduction to Computer Science II

V22.0102 Spring 98
Page contents (C) by Samuel Marateck, 1998

Professor: Samuel Marateck
TA: Archi Rudra

We are fortunate to have Archie Rudra as the TA for this course(archi@cs.nyu.edu). His lab hours at 14 Wash Pl. for the current week will be found by clicking here.

>>

Connect Four

6
5
4
3
2
1
	1	2	3	4	5	6	7

For lecture times and location click Syllabus.

USING THIS PAGE

Reaching Samuel Marateck

v
• e-mail marateck@cs.nyu.edu
• phone: (212) 998-3146
• office: 620 Warren Weaver Hall
• office hours: 4:30 - 6:00 Monday and Wednesday

Java Tree Recursion Applets

Java Applets for Conway's Game of Life

FINAL EXAM: May 6, WED, 8:00 am, 703 Main

Sample midterm #1

Sample midterm #2

Solutions for Sample midterm #2

Midterm 1 (1997) and its solutions

Midterm 2 (1997) and its solutions

The sample final

Solutions for Sample Final

Rules for writing programs

Instructions for course email list

Sending homeworks by email

• Where to submit your programs
• How to attach files to a pine email
• How to ftp your programs to a Unix machine

Writeups & Related Programs

• Objects and Units

  Programs and Data for the Objects and Units writeup.

  • The object unit for the Game of Life
  • The client program for the Game of Life
  • Data set for the Game of Life

  Supplement for Turbo Pascal 7.0

  Turtle graphics writeup

  Stack programs

  • Evaluating postfix expressions & converting infix to postfix
  • The stack ADT unit
  • Defining the type of the stack
  • Reversing input
  • Evaluating a postfix expression
  • Converting an infix to a postfix expression
  • Converting an infix w/parentheses to a postfix expression

  Queue programs

  • The queue ADT unit
  • Defining the type of the queue
  • Using the queue
  • A memory efficient queue ADT

  Linked list programs

  • Introduction to linked lists
  • Converting infix to postfix w/paren
  • stackadt.pas as a linked list
  • stacktyp.pas
  • Using a queue
  • The queueadt.pas as a linked list
  • qtype.pas
  • About queues

  Tree programs

  • A binary search tree w/include file
  • The include file for BST
  • Binary search tree using TreeADT
  • TreeADT containing a BST
  • Erasing the nodes of a tree
  • Counting nodes of a tree w/ a procedure
  • Counting the nodes of a tree w/ a function
  • Printing the info in the leaves
  • Copying a tree
  • Testing for identical tree
  • Performing a binary search
  • producing the mirror image of a tree
  • A breadth-first search of a tree
  • The queue include file
  • Overton's tree picture program
  • Time analysis
  • 2-3 Trees

  Sort programs

  • The quick sort
  • Building a heap
  • Sorting an array in heap form
  • Sorting an array using heap sort
  • The heap ADT
  • The heap sort
  • Sorting an array using heap sort

  Hashing programs

  • A simple hash
  • A simple hash using hashADT
  • The hash ADT
  • Using chaining in bucket hashing ADT
  • The bucket ADT
  • The linked list ADT
  • Record definition for linked list ADT
  • Testing the linked list ADT

Homeworks

• Homework #1, Connect 4.

  Helpers for Homework #1. WARNING. If you change the interface, your program WILL NOT execute.

  Since your ability to download player.tpu using Netscape depends on the version you are using, I will distribute this file over majordomo. They are also available on the z: drive of the acfsw (14 Wash place) server in the \courses\v220102 directory.

  • The BoardADT INTERFACE
  • The pre & post conditions for BoardADT
  • some of the methods for BoardADT
  • The info on methods to be written.
  • The essentials of graphics for this project
  • The graphics interface
  • The text layout
  • The valid function used in is_win
  • Determines whether to continue playing
  • Finds row in which to place the checker
  • Checks that the column chosen is valid
  • How to procede with drafts 1 & 2
• Homework #2, A String Calculator.

  Helpers for Homework #2

  • test1.pas tests your StrnADT.tpu (for draft 1)
  • analyse.pas is the Scanner and Initial Parser (for draft 2)
  • The interface
  • The assignment method
  • The Last function
  • The output for draft #1
  • The output for draft #2
  • How to procede with draft #2
  • A hashing program
  • Data for hashing program

    Data for Homework #2

    • Data set for draft 2
    • Data set for draft 3
• Homework #3, Draft1, Huffman Coding

  Helpers for Homework #3, draft #1

  • The interface for the ADT
  • The client
  • Data set
  • How to procede
  • The output for draft 1
• Homework #3, Draft2, Huffman Coding

  Helpers for Homework #3, draft #2

  • The interface for the ADT
  • The client
  • The compressed file
  • Testing Decode & PrintCode
  • The compressed file for the testing program
• Homework #4 , A Simple Compiler

  Helpers for Homework #4

  • Drawing an expression tree and evaluating it
  • Statement to be compiled (input data)
  • IR code to be generated (output data)
  • IR code for sequential T subscripting

Class Programs