Introduction to Computer Science II

V22.0102 Spring 2000
Page contents (C) by Samuel Marateck, 1999

Professor: Samuel Marateck
TA: Tatiana Kichkaylo

Help with homeworks and course

• Mon 5:15 - 6:45 in her office (408 WWH)
• Tue 10:00 - 12:00 in the lab
• Wed 1:00 - 2:30 in the lab
• Thu 1:00 - 2:30 in her office; 5:15 - 6:45 in the lab

For lecture times and location click Syllabus.

Reaching Samuel Marateck

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

Java Tree Recursion Applets

Java Applets for Conway's Game of Life

IF YOU DON'T DO ALL THE PROJECTS, YOU CANNOT PASS THE COURSE. ATTENDANCE IN CLASS IS MANDATORY.

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 2000 tree picture program
  • Time analysis
  • 2-3 Trees
  • How to write tree procedures

  Sort programs

  • The quick sort
  • How the Quick sort works
  • Building a heap
  • Sorting an array in heap form
  • Sorting an array using heap sort
  • How the heap sort works
  • 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 for draft #2.

  Since your ability to download player.tpu using Netscape depends on the version you are using, I will distribute this file over majordomo.

  • Connect-4 applet
  • The BoardADT INTERFACE
  • The pre & post conditions for BoardADT
  • The player.tpu (14384 bytes, dated 1/24/99)
  • 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
  • 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 output for draft #1
  • The output for draft #2
  • How to procede with draft #2

    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
  • readOrdList
  • 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
  • The compressed file for the testing program
  • Partial output for the program
  • The testing program
  • The output for the testing program
  • How to procede with draft #2
• Homework #4 , A Simple Compiler

  Helpers for Homework #4

  • Statement to be compiled (input data)
  • IR code for sequential T subscripting
  • The Evaluate function

Class Programs

1998 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

• Chapter 16
• Chapter 17
• Chapter 18