91.102 Computing II  --  Spring 2011   

IF YOU NEED SOMETHING TO DO THIS SPRING BREAK
AND YOU WANT TO SAVE SOME TIME WHEN WE START UP AGAIN:
DO THESE SEVEN HOMEWORKS.

YOU CAN DO THEM!

infix1.doc

infix2.doc

infix3.doc

combination.doc

lisp1.doc

lisp2.doc

lisp3.doc

lisp4.doc


 

Instructor          Jim Canning
Office              Olsen Hall, Room 231
Email               canning@cs.uml.edu
Lectures           91.102 M,W,R, F from 9-10 and from 11-12
                       91.406 M,W,F      from 12-1

Office Hours     Not established yet.

Teaching Assistants     They have not been identified as of yet.

Esakov and Weiss Hall of Fame

These students are in my Esakov and Weiss Hall of Fame.
Textbooks

Data Structures - An Advanced Approach Using C, by Esakov and Weiss

This book is a gem. Short, sweet, and chock full of example code.  Esakov and Weiss have given you a chance to read a pile of small case studies in C. Embedded in these case studies are opportunities for you  to see how other people write code. You should learn each case study. My goal is to inspire you to read, understand, and enjoy this book. Once purchased, never sell this book.

Applications Programming in ANSI C, by Johnsonbaugh & Kalin

         
This book is commonly referred to as your best friend. It is. You need to know the contents of this book. You need to know how to use this book as a reference book.

Articles

Description

This course covers all eight chapters of Esakov and Weiss's data structures book. Students will learn how polymorphic data structures are implemented. Ideally, all case studies of example C code found in Esakov's book will be discussed. Students should obtain a clear understanding of pointers, pointers to functions, and recursion. Beyond this, students will be given ample opportunity to practice reading for detail and discovering within themselves that they can achieve much more academically than they have to date. One of our goals is to have all students emerge as very confident C programmers that have an appreciation of basic data structures and algorithms. The topics covered in this course will be: a review of C Programming, recursion, data abstraction, sorting, divide and conquer, big O notation, using pointers to functions and pointers to data to implement polymorphic data types, linked lists, hashing, circularly linked lists, doubly-linked lists, stacks, queues, trees, tree traversal, binary search trees, AVL trees, n-ary trees, heaps, graphs, and sets. In this class we obtain a better appreciation of the gdb debugger and the UNIX make utility. Computing II is not a spectator sport. You must bring a full level of commitment.

This is a four credit class. It meets 53 times during the semester. The semester spans 106 days. We can accomplish alot.

Prerequisites
Statement from Jim

91.102 Computing II is an extremely important course in your development. There is a lot to master. The time commitment is substantial. It takes time to read, understand, and program. You must get on-board. No slow starts. No fading in the middle of course. No wilting at the end. You need to sit still and read your textbook. Lectures will help you understand the book. Come to class alert and prepared. I feel very strongly that you should be in class at all times. You need to follow the discussion for the entire 50 minutes. No losing your focus. You need to get a study system in place that removes distractions and allows you to learn as an individual. You can do it. When you leave the lecture room, your work in this course is just beginning. You all know how I feel about this. Make 91.102 your highest priority. You need blocks of consecutive hours to sit and concentrate. Friday nights, Saturdays, Sundays, and Spring break are chocked full of consecutive hours. We want to master the material.

Attendance

Class attendance is mandatory.This semester, I will be taking attendance. You will be awarded two points if you arrive on time. If you arrive late or if you appear disinterested, you will be awarded 1 point.

Academic Honesty

You should do all of your work by yourself. You should not copy your classmate's homework. You should not copy a classmate's solution to a programming problem. You can receive a hint or two but you should fully understand how to do the work after you receive the hint. When you hand in your work you are declaring that (1) you did your own work and (2) you thoroughly understand how the code works and (3) you will be able to either recreate it or discuss it on an examination. You can do these things. Lapses in honesty lead to trouble. It is better to get your work in late and have it be your own than it is to copy a classmate's solution and hand in it under your own name. Lapses in honesty, when discovered, break an unspoken trust.  Don't do it. You break this trust even when you provide the answer to a classmate. You are robbing your classmate of the opportunity for accomplishment.

If you give or receive a noticeable amount of help from another person or from the internet you should state that on the document you hand in.

Attitude

Be positive. Try. If you are struggling,  review your study habits. Read and apply Hamachek's book. Your study schedule may not be as intense as it needs to be. You may need to go back and remove some of that accumulated academic rust. You can do it. Your body language screams, it never whispers.

Classroom Demeanor

You should take Alice Hamachek's advice regarding classroom demeanor. Do not arrive late. Come to class early, fifteen minutes early if possible. Do not wear a hat or baseball cap in the  classroom. Do not have your laptop turned on. Do not have speaker wires hanging from your ears.  Do not have your head on your desk. Do not slouch. If possible, sit closer to the front. Apply these suggestions to all of your classes. You should not be talking with your classmate during lecture. You should not be fiddling with your cell-phone. If you need to use your phone, just leave the room.

Quality of Work

Pay attention to the quality of the work you hand in. It is not just about getting the right answer. When I review your work, I should think to myself that this work was done with pride. Your work should be respectful and courteous to your reader. Your work is telling the reader a story. It should be clear. Your spelling matters. Your indentation matters. Your tidiness matters. Your grammar matters. It all matters. Cross-outs and scribbles should be kept at a minimum or eliminated completely. Your typing or penmanship should not be cramped. Your work should not looked rushed. Work that is deemed discourteous, disrespectful, messy, and/or rushed will be discounted. Work that contains spelling errors, fundamental grammatical errors, and/or awkwardly phrased concepts will be discounted. Do not over capitalize. Do not misspell. A single assignment that spans multiple pages should be stapled in the upper left hand corner. The staple should be angled diagonally. Multiple assignments should not be stapled together when they are handed in. You can do these things.

Pop and Announced Quizzes

Pop quizzes are quite possible. When I ask you to read something or if I have asked you do a programming problem, please do it. I intend to encourage your reading by rewarding you with a pop quiz.

Late Work

Your work should be handed in on time. Work handed in 1-6 days late will be discounted. Work handed in 7-14 days late will be severely discounted.  No credit will be given for work that is received 15 or more days late.


Time

All of this takes time. Lots of time. If you are taking an overload of classes or if you are working 15-30 hours per week or if you are commuting a long distance then time will be difficult to come by. Assess your own situation. Can you give this course the time it requires? The material is not difficult, but it requires your time and your attention to detail. If you get off to a slow start it will get rough. You need to invest your time wisely. Friday nights, Saturdays, Sundays, and spring vacation week offer you important blocks of consecutive hours. Use them. My expectation is that you are using them to study. Get out of the dorm and get over to Olsen Hall or get yourself into the library. You can do all of this work, but it requires that you sit yourself down in a chair for multiple consecutive hours. You should get in the habit of sitting by yourself. Nobody who will disturb you is nearby. You can do it and if you do, you will be rewarded. This is not a good course to cobble together 20 minutes here and then another 15 minutes there. We are not trying to do the minimum to get by. We are trying to emerge as confident scholars. We are on a mission to become strong. You can do it. We are not here to settle for less. You are not just trying to collect 4 college credits. It is a very competitive world out there. Do not let them eat your lunch.

Most of your learning occurs outside of the classroom. It is what you are doing outside of the classroom that really matters. Never mistake activity for achievement. Who said that?

Shortcuts    There are no shortcuts.

Readings

You need to establish a daily reading schedule. This should be seven days per week. You should figure out the place you will go to read. It should be very quiet. It should be well-lit. You should get to feel comfortable going there. It should become your space to get away from all distractions. It is quiet time. Your cell-phone is not near you. You should not have earbuds in your ears. You should be sitting solidly in a straight backed chair. You are not reading on your bed. You are not reading on the couch. You are not reading while you are watching TV. You should be in an isolated location. It would be great if there was a white board near you. You should be reading with pencils and paper at your side. There should be a dictionary near you. Use it. You need to practice the skill of "effective use of quiet time". You need to train yourself to sit still as best you can.  Increase your study stamina as you go. Leave the dorm room. Leave all the craziness behind you. Go someplace quiet and learn how to invest in yourself. If you train yourself to do this, it will become fun. Your grades will improve too. Each day affords you a chance to practice. You need to practice the art of studying. You can do this. You can get much much better at this.

Day
Read before 9:00 pm
Reading Assignment
Pages
1
Monday
January 24
Preface
1.1 Structures and Section 9.1 of your best friend
2.1 What is Recursion? (Review)
5.1 The Stack
5.2 Application: Parenthesis Checker
5.3 Stack Implementation: Static Array

ix - xi
1-3
29-33
103-104
104-110
110-113
2
Tuesday
January 25
The Perils of Java Schools
1.2 Unions and Section 9.8 from your best friend
2.2 The Towers of Hanoi

1-6
3-4
33-35
3
Wednesday
January 26

1.3 Enumerated Types
2.3 Fibonacci Numbers
4-5
35-36
4
Thursday
January 27

1.4 Function Invocation
5.4 Application: Graphical Region Fill
5.5 Stack Implementation:  Dynamic Arrays

5-9
113-121
121-123
5
Friday
January 28
1.5 Pointers ( partial: Intro )
8.3.2 Mergesort
10-14
340-345

6
Saturday
January 29
1.5.1 Using Pointers to Return Values
4.1 List Concepts
4.2 Linked Lists (partial: Intro, 4.2.1, 4.2.2, 4.2.3 )

14-15
54-56
56-59
7
Sunday
January 30
1.5.2 Pointer and Arrays
4.2.4 Primitive Operations on Linked Lists
4.3.5 Additional List Primitive Operations
15-20
59-65
73-76

8
Monday
January 31
1.5.3 Pointers and Structures
4.3.1 Polynomial Addition Program Design
4.3.2 Polynomial Driver

20-21
66-67
67
9
January 30
1.5.4 Pointer Arithmetic
4.3.3 Polynomial Data Type Implementation
8.3.6 Radix Sorting
21-22
68-72
357

10
January 31
1.6 Pointers to Functions
4.3.4 List Interface Routines for Polynomials
7.1 Trees and Graph Concepts

23
72-73
238-239
11
February 1
1.7 Typedef
7.2 Binary Trees Intro
7.2.1 Traversing a Binary Tree
7.2.2 C Representation of Binary Trees
23-24
239-240
240-242
242-243

12
February 2
1.8 Dynamic Memory Allocation
7.2.3 Primitive Operations on Binary Trees
Binary Search Trees

25-26
244-248
328-332
13
February 3
5.8 The Queue
5.10 Queue Implementation: List Functions
3.1 Abstract Data Types
135-136
145-146
39-44
14
February 4
6.1 Circular Lists Intro
3.2 Polymorphic Data Tyypes
152-153
44-45
15
February 5
6.1.1 Primitive Operations on Circular Lists
3.3 Software Development and Life Cycle ( first part)
153-159
45-46


Homeworks

Homework1
Homework2
Homework3
Homework4
Homework5
Homework6
Homework7
Homework8
Homework9
Homework10
Homework11
Homework12












HomeworkA
HomeworkB
HomeworkC















Homeworkgtk1
Homeworkgtk2







Grading

There will be in-class points and out-of-class points. Your average of in-class points will contribute to 60% of your grade. Your average of out-of-class
points will contribute to 40% of your grade. The usual 90, 80, 70, etc. average will drive your letter grade. Grades will be scaled, but not as much as they
are in Computing I. If you wish to become a CS major, now is the time to get serious about your coursework.




IGNORE WHAT IS BELOW THIS FOR NOW.


Ch
Title
Date
Readings
Study Guide/Worksheet
Homeworks
Due Dates
Old Exams + Powerpoint Slides
Other
1
Advanced C Constructs
Should
be
done
before
class
starts.
Pages 1-26

101 Programs 1-25
101 Programs 26-30
101 Programs 31-35
101 Programs 36-40
101 Programs 41-45
101 Programs 46-50
101 Programs 51-55
101 Programs 56-60
101 Programs 61-65
101 Programs 66-70
101 Programs 71-75
101 Programs 76-80
101 Programs 81-85
101 Programs 86-90
101 Programs 91-95
101 Programs 96-101
Monday, Feb. 1
Monday, Feb. 8
Monday, Feb. 15
Monday, Feb. 22
Monday, March 1
Monday, March 8
Friday, March 12
Monday, March 22
Monday, March 22
Monday, March 29
Monday, April 5
Monday, April 12
Monday, April 19
Monday, April 26
Monday, May 3rd
Monday, May 10th
Fall 2008 91.101 Computing Final
2
Recursive Functions
Jan. 25
Jan. 25
Jan. 26
Jan. 26
Section 2.1 (pp. 29-33)
Section 2.2 (pp. 33-35)
Section 2.3 (pp. 35-36)
Section 2.4 (pp. 36-37)
Study Guide and Worksheet
Assignment 1
Assignment 2
Assignment 3
Assignment 4



3
Data Structures and Software Development

Section 3.1
Section 3.2
Section 3.3
Section 3.4
Section 3.5
Study Guide and Worksheet
Assignment 1
Assignment 2
Assignment 3
Assignment 4

Chapter 3 Powerpoint Slides 1

Chapter 3 Test


4
Lists

Section 4.1
Section 4.2
Section 4.3
Section 4.4
Section 4.5
Study Guide and Worksheet 1
Study Guide and Worksheet 2
Assignment 1
Assignment 2
Assignment 3
Assignment 4

Chapter 4 Test
Chapter 4 Test (2007)


5
Stacks and Queues

Section 5.1
Section 5.2
Section 5.3
Section 5.4
Section 5.5
Section 5.6
Section 5.7
Section 5.8
Section 5.9
Section 5.10
Section 5.11
Study Guide and Worksheet 1
Study Guide and Worksheet 2
Stack 1
Parentheses Checker
Fill 1
Fill 2
Fill 3
Fill 4
Infix to Postfix 1
Infix to Postfix 2

Queue 1
Oper. System Sim 1
Queue 2
Oper. System Sim 2



6
Advanced List Structures

Section 6.1
Section 6.2
Section 6.3
Section 6.4
Section 6.7

Assignment 1
Alligators and Ducks
Lisp 1
Lisp 2
Lisp 3
Lisp 4
Doubly Linked Lists
Simple Line Editor 1

Chapter 6 Test
7
Trees and Graphs

Section 7.1
Section 7.2
Section 7.3
Section 7.4
Section 7.5
Section 7.6
Section 7.7
Section 7.8
Section 7.9
Section 7.10
Section 7.11
Section 7.12
Section 7.14

7.1 Assignment

Expr. Eval A
Expr. Eval B
Expr. Eval C

Graph Primitives AM



8
Sets, Searching, and Sorting

Section 8.1
Section 8.2
Section 8.3
Section 8.4

Bit Vector Assignment

Poly. Mergesort
Poly. Quicksort
Poly. Heapsort
Poly. Radix sort




Other









Programming Style Guide

Programs must adhere to the rules and guidelines given in the style guide document. The style guide document can be found in the C programming problems document.


P
*************

Ignore this for now.
Task

Description
Due Date
Comment

Deliverable to Pass In?
8

Read section 8.1 in Esakov.
Jan. 26
Record how long it took you to read it. Take notes. In your notes write down the title of section. In your notes write down the formal definition of the Big Oh notation. As you read the section, ask yourself  "What would Jim ask me about this section?" Write down possible questions that I would ask of you. Thirty minutes spent now reading this section is time you will save later. Try to get this done well before the start of classes. It is always better to have read the material in the book before we discuss it in class.

No
13

Read the four introductory paragraphs that start Section 8.2
Jan. 26
This is less than 1 full page of material. You should take notes as you read it. Make sure you know the title of Section 8.2. Make sure you know the exact title of your textbook. Make sure you know the exact spelling of the names of the textbook's two authors.


16

Read Subsection 8.2.1
Now
Subsection 8.2.1 is called Bit-Vector Representation. Know this title. What is the title of Chapter 8? Who are the two authors of your textbook?  This subsection is just three pages full.  As you read this section doodle a picture of the data structure. What is the purpose of the  array called bit? Do you see exactly how a set of integer values is being represented. This approach is a  good approach when you are keeping track of a finite set of integers or when your data can be mapped easily into a finite set of integer values.


17

Bit Vector Representation
TBA
Remember at the tail end of Compuing I, I gave a copy of globals.h to you. You were supposed to have typed it in. I hope you did. Make a copy of globals.h and move it into your bitvector directory. For this assignment you will also need to create set.h, set.c, and a makefile. You will also need to create two data files. The full write-up for this assignment can be found by clicking on the link to the left. This code is not polymorphic.

You need to do this assignment if you wish to become a Master of Chapter 8. There will be other such assignments. Get this one out of the way now. Spend 90 minutes now getting this to work. It is 90 minutes you will have when you need to study that math test or write that term paper.

Yes
19

(re) submit paper copies of problems 11-20 of "Jim's Programming Problems" given in Computing I

If you received 3 points on a problem, you may submit the same paper copy back to me that I handed back to you during Computing I. If not, fix it. Make your code look good. I am going to (re) collect all of your Computing I assignments and put them into your binder. Each of these assignments must look great. In order to achieve the label "Master of Chapter 1", you need to have a binder filled with beautiful looking, working programs. All of the programs. You can do this. You can start now. Go back and revisit problems 11-20.  Make sure that your solutions to them look snappy and that they work. A program that is not "healthy" will not be placed into the binder. Bring your best game.

Yes
20

(re) submit your paper copy of selection sort. This is the non polymorphic version.

You should go back and review this code. I beleive it was programming problem 79 from last semester. Walk yourself through it. Take the time to do. Doodle how it works. Make sure you can replicate this code without the aid of a textbook. You should be able to write this program on a piece of paper with your book closed and nobody looking over your shoulder.

Yes
23

Extending Problem 74

On page 50 of your textBook, you will find problems 1a, 1b, and 1c. You need to get these routines built and placed into your complex.c file. You will also need to add their "declarations only" to your complex.h file. 

Yes
25

Read Section 8.2.2

You are on your way to becoming Masters of Chapter 8. One step along this path is to fully understand the material on pages 321, 322, 323, and the top half of page 324. Find a quiet, well lit location, shut down your ipod, mp3 players, cell phone, blackberry, radio, tv, and have a quiet moment with subsection 8.2.2. You can do this.

No
26

Sequential Set Representation
TBA
Make another copy of globals.h and move it into your sequential directory within your ch8 directory. In addition to this you will need to obtain my version of main.c for this problem. It can be found in my public directory. You will also need to create set.h, set.c, and makefile. The set.c file will contain the init_set function definition located on page 322. Type this in. It will also contain both the set_insert and set_member functions found on pages 322, 323, and 324.

This representation of sets is polymorphic. It can be used to represent a set of integers, a set of words, a set of doubles, a set of sets, etc. It contains two key ideas. The first is the concept of a generic pointer. Generic pointers are pointers to a void. They are useful because their size is the same no matter what it is they point to. The second concept is passing a function as an argument.

Yes
31

Read Section 5.2
Now
Read section 5.2 in its entirety. Go someplace quiet. Turn off your electronic devices. This section spans pages 104, 105, 106, 107, 108,109, and 110. As you read this material, you should realize that the code given relies upon the material discussed in section 5.3. You should also note that the switch statement at the bottom of page 106, the top of page 107,  and at the top of page 108 contain errors.  The '-' symbol and the  " symbol are the wrong symbols. Never the less, you should mentally trace through this code.



33

Create stack.h, stack.c for the Parenthesis Checker Case Study.

Using Section 5.3 as your guide create two files within your ch5/paren subdirectory. One file is called stack.c and it contains the code for init_stack, empty_stack, push, pop, and top. These function definitions are given on pages 111 and 112. You can do this. You will need to include both globals.h and stack.h. The second file is called stack.h. Use the #ifndef construct and put an appropriate description comment at the top of the files identifying who you are, the name of each file, and incorporate the case study name too (parenthesis checker).

After doing this you should be able to successfully compile the program. I did not say link the program.  You need to use the -c option on the gcc command line. For example, %gcc -c -ansi -Wall stack.c. Ideally, you will have no error messages or warning messages. If you do, find a way to eliminate them. Make sure you understand the code that you are typing in.


Not yet
35

Creating a stack interface module for the parenthesis checker problem.

Make sure you've completed tasks 29, 30, 31, 32, and 33.  Now, you need to built interface.c and interface.h for the parenthesis checker problem. The code for interface.c is located on page 108 and page 109. This interface codes sits between the main function and the stack primitives. The interface code know that the stack primitives seeks generic pointers. The interface code knows that the main routine will be passing down (push_char) or expecting to receive (pop_char, top_char) character data. The interface code repackages the data.

The interface.c file will need to include interface.h and globals.h.

At first, this code will look confusing to you. Try your best to doodle it out and walk yourself through it. I will go over this code in class.

Not yet
36

Parenthesis Checker

Create main.c for the parenthesis checker program. The code for this is in your book on pages 106, 107, and 108. Type it in.
Create a makefile for the parenthesis checker program. You can do this.
Hand in a working paper copy of the parenthesis checker program to me. Put the makefile on top. Clearly label the makefile with a comment as to who you are and what the program name  is.
Electronically submit your working copy of the parenthesis checker as indicated in the table below.

Yes
37

Selection Sort - the non polymorphic version

Go back and find your solution to programming problem 79. This was the non polymorphic version of selection sort. It sorted integers. Submit your paper copy of this program. In so doing, you are verifying that it works and that you understand it.

Yes
38

Polymorphic Selection Sort of Strings

At the very bottom of page 338 and at the top of page 339 you will find code for a polymorphic implementation of selection sort. It relies upon generic pointers and C's ability to pass a function as an argument. You should move into your 102/ch8/sorting directory and then create a selection subdirectory. Move into the selection subdirectory and then create selection.h and selection.c. The code for selection.c is in the book. The code in the book is correct. There are no typos.  Within selection.c you will need to include "globals.h". Make your code look good. Let it breathe. You are not in a rush to complete it. The doodle in the book 2/3rds of the way down page 339 is a bit misleading since it shows integer data within an array of integers. This is not quite right. The doodle should be an array of pointers (to voids). The authors did this, perhaps, to save ink as the real doodle would have been a bit more complicated. They simplified matters and hoped that you would know how the code works by reading it.

Your selection.h must have a header comment. Your selection.h must use the #ifndef construct. You will need to include "globals.h". You should  compile this using the -c option as well as the -ansi and the -Wall options.

Ok, now you should create main1.c. it is given to you on the bottom of page 339 and the top of page 340.  It is very short.

Build an executable image and get your program to run.  Submit yoru hard copy to me and also submit your code electronically.

Yes

 


Submitting Your Programs

You need to submit all of your programs to me in hard copy format.  

You need to electronically submit the following programs to the grader indicated in the table below.

When you submit your program to the grader you need submit all of the files needed to build an executable image, including a Makefile. The grader should only need to type "make" to build your program. For example,  to submit your bit vector representation of sets code you would:

                                        % submit canning  bv name main.c, set.h, set.c makefile

You need to use one invocation of the submit command to send all of your files to the grader.

If you have trouble submitting an assignment please email the associated grader and work it out.



Check Lists

Powerpoint Lecture Notes