91.102 Computing II

91.102 Computing II
Spring 2009
(last updated - December 31, 2008)

Become a Master of Esakov and Weiss.

Join the Esakov and Weiss Hall of Fame.

You can do it.

Instructor          Jim Canning
Office               Olsen Hall, Room 231
Email             canning@cs.uml.edu
Office Hours TBA

STUDENTS WHO WISH TO GET A JUMP ON THE COURSE

Class will start on Monday, January 26, 2009. I am looking forward to it. I hope you are too. You can do lots of good work before class starts. Those students who have done this in the past were thankful they did. The weeks before class is a good time to get things under control before you are overwhelmed with semester duties. For a list of things you can do, check the "To Do List" given below and get cracking. Do as much of this as you can. Email me that you are working on this, I will put you on the "winter workers" email distribution list. I hope to meet the winter workers a few times over winter break as a group. Please keep checking this website. This website is evolving.

Make the commitment to become a Master of Esakov and Weiss. To see what it will take to become a master scroll down to the bottom. Start now. You could do it.

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.

Coping with College, by Alice L. Hamachek

A small guide to success in college. Pick this book up frequently.

The Elements of Style, by Strunk and White

The "little book". You should all be carrying this book around with you. Paperback version is best.

Reading and Doodling

Reading a textbook for detail is an important academic activity. It is the skill to practice. You can improve. Significant and swift improvement will result with daily practice. You need to pride yourself on reading slowly and thoroughly. Do not pride yourself on how fast you read. Make sure you understand what the author is saying. Help yourself out by diagramming the material. Create a set of useful doodles. Doodles come in all sizes and shapes. They are timelines, they are stick figures, they are tables, they are graphs, they are summary notes, and they are pictures with circles and labelled arcs. It takes time to create doodles, but the activity of doodling what you read is rewarding and beneficial. When you read you should make a note of the important terms. Write the terms on a piece of paper. Doodle and write what you read. The mere act of writing what you've read will strengthen your understanding of the material. You should go to a classroom with a white board and diagram what you have read on the board. Do so with a friend. Try to verbally explain what you've read to yourself. As you read, make a list of possible questions that could appear on a future exam. Build your own test and then take it at a later time. Test yourself before you get tested.

It is never enough to read the material just once. It may take you many readings of the same material to finally get it. Slow, but sure, wins the race. Take notes as you read.

Our textbook contains 360 pages spread across eight chapters. If you average five pages of reading per day you can cover the book. How long does it take to read and fully understand five pages? Sometimes this can go quite fast. Sometimes it moves a bit more slowly. Commit yourself to reading, on average, five pages per day from our textbook. If you skip a day, then you will need to read ten pages the next day. Remember, reading means understanding. Understanding means doodling and verbalizing.

In our case, the pages are filled with C programs. You need to walk through this code mentally. You need to create meaningful doodles. How does the code work? Can you explain it? Can you replicate it? You need to get the code to work. You need to type it in. You need to debug it when there is trouble. How do you know how the code works? Get out those #2 pencils. Get out that blank white paper. Draw it out. Follow the flow. Do not just type it in and hope for the best. Typing it in and hoping for the best is a failed strategy. Know what is going on. This can not be done at the last minute. You are not in a rush. This is not a sprint. It is a marathon. You need endurance.

When you read, you should have a dictionary nearby.

Esakov and Weiss Hall of Fame

These students are in my Esakov and Weiss Hall of Fame. I hope, as a result of this semester, to add many more students to this hall of fame.

Christopher Johnson
Christopher Adoretti
Elliot Moy
Bruce Malley
Christopher Dietsch

To see how to become a Master of Esakov and Weiss and enter the Hall of Fame see below.

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 will obtain a much clearer view 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.

Articles

Reading Types in C Using the Right Left Walk Method, by Jim Canning, William Moloney, Demetrio Rey, and Ali Rafiemyhr
The No. 1 Skill Teens Need for College, off of Netscape News.
The Perils of Java Schools, by Joel Spolsky
Column 7, Algorithm Design Techniques, by Jon Bentley. Taken from Programming Pearls.

Programming Style Guide

Programs must adhere to the rules and guidelines given in the Programming Style Guide for 91.101/91.102 document.

Prerequisites

Earning a C+ or better in 91.101 Computing I or equivalent. If you earned less than a C+ you are welcome to attend, but please know that you will need to substantially increase your level of commitment. You will need to figure out concepts that you missed in 91.101. I am willing to help you, but you need to make the commitment to master that material. Bring it.

C programming and Unix skills

An ability and desire to work 8-12 hours per week on this course outside of the classroom lecture.

You should be able to maneuver around the UNIX environment. You should be able to program - without too much difficulty - the first 82 programming problems given in Computing I. The only four exceptions to this are problems 61-64 which are a bit more challenging. If you have not completed these assignments, you should work on them before class begins. The following link provides you with a document that contains the programs: Simple C Programming Problems. If class has started and you do not have them done, you should plan to work your way through them systematically as we proceed through the class. You need to be able to demonstrate to me that you can do these programming assignments without too much trouble. You can do this.

You should be able to score at least an 85% on the 91.101 Computing I final exam. You should take the test. For any question that you cannot do, please seek immediate help. There is time for you to get this all straight. The following link provides you with the Computing I final: Computing I Final. You need to show me that you can handle these questions with relative ease. You can do this.

You need the ability to follow the flow of execution of a C program. You need to understand when an address is passed to a function. You need to be able to walk through a program and fill out its associated memory template. If you cannot do this for a variety of small programs you should get immediate help. The variety of programs should include functions being called, arrays being passed, recursive functions being called, space being malloced, and structures being passed.

You should have a working knowledge of how to use the emacs editor, how to use the gdb debugger, and how to form of simple makefiles.

Grading

Your grade will be formed by your evaluation in 16 separate areas. Each area contributes to a percentage of your overall letter grade as indicated by the course grade sheet. Your average within an area is determined by both your out of class performance and your in-class performance. You need to submit your working programs and case studies on time. Late submissions will lose points. Doing well on the first test covering a particular topic is best. If you do poorly on a quiz or test, I cannot guarantee a re-test, but if I do re-test you, then you will not earn full credit. All assigned work and exam questions will contribute to your overall score in one or more of these 16 areas.

Attendance

Class attendance is mandatory. Two points for those who come to class and sign the attendance sheet. Zero points if you do not sign the attendance sheet. If you come in late you run the risk of earning only 1 attendance point. If you are present, but you are not engaged in the discussion, you run the risk of earning only 1 point. Wearing hats in class is discouraged. Coming to class regularly is important. It is your job to be there. As unfair as it may seem, attendance is a binary evaluation. If you are there and if you sign the sheet you earn points. Not being there, no matter how good a reason you may have, will result in not earning any points.

Late Work

I encourage all of you to do all the work. All work should be handed in on time. For each assignment there is a due date. Work handed in after the due date will be discounted. Very late work will be further discounted. No credit will be given for work that is received after the last call date has been announced. It is better to hand your work in late than never. It is not good to get a reputation of frequently handing in late work. Keep up. You can do it. Find your rhythm. Have ankle sway.

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 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.

Quality of Work

Pay attention to the quality of the work you hand in. It is not just about getting the right answer. When your reader (me) reviews your work, the reader should think to himself 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.

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 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 can do it and if you do, you will feel 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 who have accomplished something. 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.

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?

Commitment and Caring

Your enrollment in the course is a statement that you are commited to learning the material. I am committed to explaining it to you. Sustain and strengthen this commitment as we move forward together. Even if you find the material somewhat dry. Stay involved. Stay committed. We need to build your base. Care about your base. View the case studies as mini-adventures. Figure out how they do their job.

The time commitment is substantial. This is a four credit course that meets four times per week. Most experts suggest that you commit to studying 2-3 hours outside of class for every hour you spend inside the classroom. Since this is a programming class and programming requires time, I am inclined to use 3 hours. This means that you should be studying 91.102 Computing II material 12 hours per week outside of our classroom. This studying should be away from distractions. Reading in the hallway of Olsen Hall or on a park bench is not the goal. Reading on your bed is not the goal. Find a way to be efficient and focussed with your reading.

Shortcuts

There are no shortcuts.

Things to Do

Task

Description

Due Date

Comment

Area
See Course Grade Sheet

Deliverable to Pass In?

Make a commitment to become a Master of Esakov and Weiss

Now

You have the ability within yourself to master every morsel of our textbook. I will help you to do this. You need to have a sincere desire to earn the title Master of Esakov and Weiss. It will take time for you to earn this title. You cannot get by just by hanging out in class and then scrambling about to find a bit of time here and there to get the work done. But, do not think for one second that you cannot do it. I invite you to make this commitment. You need to structure your outside of classroom life so that you are able to dedicate yourself to a regular, disciplined program of effective study. The process starts right now. Go get the book and do not wait for class to start. Bring your full effort. Bring it.

91.101 Fall 08 Final

Now

Download a copy of the Fall 2008 91.101 Computing final exam. Take another stab at it. To be a Master of Chapter 1, you need to score 88% or higher on this test.

Acquire a 3 ring binder

Now

Pass your binder into me during the first week of class. The binder should be at least a 3" binder. The binder should have a way to identify your name on the outside of it. Perhaps it has a plastic pocket on the outside. Do not just write your name on it with a pen or magic marker. Your work this semester will be kept in a 3 ring binder. It will be altogether in one place. It will be located in my office. You should get in the habit of three hole punching all of your work before you pass it in. Remember to staple it. Did you buy a stapler recently?

Yes

Obtain the Esakov book.

Now

Online or at the UML Bookstore. Ideally you would obtain this book at least three weeks before class begins. In this way you can read quite a bit of it before you are start taking a full load of courses. Get the book now.

Obtain the Alice Hamachek book.

Now

Online or at the UML Bookstore. You should have already obtained this book from 91.101 Computing. Read this book. Figure out a way to incorporate its messages into your academic life.

Obtain Strunk and White's The Elements of Style.

Now

Strunk's original copy is free online. Still might be nice to have your own personal copy of the "The Little Book". You can get a new one for under $10.00. Then you can keep it in your back pocket. Buy the paperback version.

Obtain a C programming book.

Now

Applications Programming in ANSI C, by Johnsonbaugh and Kalin, is a good referenence book.

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.

Read E.B. White's Introduction.

Jan. 26

Span pages xi - xvii in the 3rd edition of Strunk and White. It starts out: At the close of the first World War, when I was a student ...
Keep this book near you throughout the semester. Take it to lunch with you. Use it when you write.

Read section 1.1 in Esakov.

Jan. 26

Record how long it took you to read it. This section is referred to entitled, Structures. Read it. Then go to your copy of Johnsonbaugh and Kalin's C book and re-read the section pertaining to structures. Do you see what the . operator does? Do you see what the -> operator does? Do you know that ANSI C will pass a copy of an entire structure when it is passed as an argument. Do you see that a function can return a full structure too. Please know that Esakov and Weiss choose to pass the address of the structure throughout their textbook. Your goal is to become a full Master of Chapter 1. To do this you will need to know the basics of the C programming language -- cold. You can do this. Give yourself a chance to excel. Friday nights and Saturdays were made for studying. You need to get in your daily academic workout. Get the rust off.

Obtain a linux user account from UMass Lowell's CS Department

Jan. 26

You should already have one from your Computing I experience, but if you do not, go to Olsen Hall, Room 312 and get one.

(re) Submit paper copies of programs 1-10 of "Jim's Programming Problems" given in Computing I.

Jan. 26

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 the first 10 programs and make sure that they look snappy and that they work. A program that is not "healthy" will not be placed into the binder. Bring your best game.

Yes

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.

Organize your unix account directory

Now

In your UMass Lowell CS Department computer account, create a subdirectory called 102. Move to the 102 subdirectory and create the following eight subdirectories: ch1, ch2, ch3, ch4, ch5, ch6, ch7, and ch8. Do this now. You can do this via "mkdir" command, but you knew that. If you did not know that, then type "man mdkir" at the shell prompt.

By the way, in the list of subdirectory names above, notice that there is a comma just before the "and". Good ole Professor Strunk says "put a comma there", so put that comma there. The comma is not optional. Put it in there.

Furthermore, please know that Bill Russell is the best basketball player of all time. This is a fact. It is not about how many points you score, or how well you can dribble, or you how well you can shoot. There is one measure. It is called the scoreboard. Bill donned the sneakers 13 years in his NBA career. His teams won 11 championships - because of him. He had different players playing with him over the years. It did not matter. His college team was 55-0 in its last 55 games. His college team also won two NCAA titles. His school was not known as a basketball powerhouse. You can become a champion too. Make the commitment to become a champion of Esakov and Weiss. Bring it. (ps: Bill Russell would have won a 12th NBA championship, but he broke his foot in the playoffs. He played and his team was eliminated in the finals.)

Make more subdirectories within your ch8 directory.

Now

Within your ch8 directory, make these subdirectories: sets and sorting. Within your newly created sets subdirectory make these four subdirectories: bitvector, sequential, binary, and hashing.

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.

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

Read Section 1.2

Now

Section 1.2 is called Unions. Read it. It is just over 1/2 page longs. We did not discuss this concept in Computing I. After reading this section go to your C book and read the section about union structures in that book too.

(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

(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.

1,12

Yes

Read Section 3.1

You need to become a master of Chapter 3. You can do this. Your mastery of Chapter 3 starts with a careful and deliberate reading of pages 39 through the top of page 44. What is the title of Chapter 3? What is the title of section 3.1? Take note while you read.

(re) submit your paper copy of problem 74.

In Computing I, you should have submitted a solution to problem 74. I want you to review this submission and then re-submit it to me.

1,3

Yes

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.

1,3

Yes

Read Section 3.2

Section 3.2 is entitled Polymorphic Data Types. Although this section is only 1 page long, it is very important that you read it. Upon first reading you may not get the entire idea. However, after building some polymorphic code, you will need to back and re-read this section. It is important that you fully understand the concepts in this section. You can do it. We will discuss this in class.

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.

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

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

Now

Each of your submissions must look good. Use the 91.101/102 style guide. In order to get full credit for your Chapter 1 work, you need to have these programs entered into your personal 3 ring binder.

Yes

Read Section 5.1

Now

This is about one page long. What is the title of section 5.1? What is the title of the textbook?

Chapter 5 Directories

Now

Use the chdir command and move to your ch5 directory. Make three subdirectories. They are called: paren, grf, and infix. Do this now.

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.

Read Section 5.3

The title of this section is Stack Implementation: Static Arrays. It is less than 3 pages long. As you read through the code do not rush. Doodle a nice picture of what this stack data structure looks like.

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

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

Go back and review your solutions to these ten problems. Do they look snappy. Did you earn 3 points for each of them? Take a moment to get these done and understood. You should not need to obtain too much help from anybody. It would be good to have done all of these before class starts. You will need to have quality looking, working paper copies of these programs placed into your 3-ring binder. Make sure that you undertand how and why each of your solutions work. Could you redo them on your own?

Yes

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

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

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

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

(re) submit paper copies of problems 41-50 of "Jim's Programming Problems" given in Computing I.

Now is a great time to get these out of the way. Make them all look great. Do not forget to call fclose if you need to. Check for spelling errors. Do not have any ragged indents. Make your code breathe. You are working towards becoming a Master of Chapter 1 when you do this.

Yes

Outcomes

       When the course is completed, the student will be able to:

         1) fill out a memory template by manually executing C programs that include: recursion, malloc'ed up space, passing of arrays, and functions calls.
         2) write C programs that use pointers to functions and pointers to generic data to build polymorphic data structures.
         3) write C programs that use recursion.
         4) write C programs that implement the following sorting algorithms: bubblesort, selectionsort, insertionsort, shellsort, and radix sort.
         5) write C programs that implement the following sorting algorithms: quicksort, heapsort, and mergesort.
         6) explain data abstraction in writing.
         7) write small makefiles.
         8) use the GDB symbolic debugger to walk themselves through a program that spans multiple files by using the following GDB commands: bt, break, s, n, display, list, and print.
         9) write three C programs that use backtracking as a programming methodology. The three programs are: Eight Queens, Knight's Tour, and Four in a Row.
       10) write five C programs that use a divide and conquer strategy. The programs are: quicksort, maximum sum subvector, mergesort, recursive Tiling, and Strassen's Matrix Multiply.
       11) write a C program that creates and prints an AVL tree by using polymorphic tree primitives previously built.
       12) write a C program that relies upon a sequential, dynamic array, and polymorphic implementation of sets.
       13) write a C program that relies upon a sequential, linked list, and polymorphic implementation of sets.
       14) write a C program that implements Dijkstra's shortest path algorithm.
       15) write a C program that creates polymorphic binary search trees and traverses them inorder, preorder, postorder, and breadth first order.
       16) Given a binary search tree, produce the inorder, postorder, preorder, and breadth first order traversal of that tree.
       17) write a C program that relies upon polymorphic circularly linked list.
       18) write a C program that relies upon polymorphic queues.
       19) write a C program that relies upon polymorphic doubly linked lists.
       20) write a C program that relies upon polymorphic linked lists.
       21) identify the average case complexity, expressed in big O notation, of sorting algorithms.
       22) score at least 85% on the final exam given in Computing I during the Fall 2007 or Fall 2008 semester.
       23) write a C program that relies upon a hashing implementation of polymorphic sets.

Teaching Assistants

They have not been identified as of yet.

Submitting Your Programs

You need to submit all of your programs to me in hard copy format. It should be nicely three holed punched.

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.

Submit to	Assignment Name	Grader's Name	Electronic Due Date	Program Name
canning	bv	canning	To be determined. Will be mentioned in class.	Bit Vector Representation of Sets
canning	paren	canning	To be determined. Will be mentioned in class.	Parenthesis Checker
	ssort1		To be determined. Will be mentioned in class.	Polymorphic Selection Sort of Strings

Check Lists

Powerpoint Lecture Notes

parenthesischecker.ppt

Previous Exams Given

            Chapter 3 Test
            Chapter 4 Test
            Chapter 4 Test (2007)
            Chapter 6 Test

Becoming a Master of Esakov and Weiss

To become a master of Esakov and Weiss and join the Esakov and Weiss Hall of Fame you need to master each of the following areas.

Area	Percentage of your 91.102 letter grade	Things that you must do to be labelled a master of the area.
Become a Master of Chapter 1	6%	Finish 78 out of the 82 programs given in the Fall 08 offering of 91.101 Computing I. For each program you satisfactorily complete, you will earn a check mark and a point. If you pass in the program late or very late you will earn only 1/2 point and you will not receive a checkmark. All programs must adhere to the 91.101/91.102 programming style and thereby be entered into your binder. Demonstrate the ability to fill in memory templates for a wide variety of simple C programming problems. Earn at least 88% on the Fall 2008 Final exam (retake it if necessary). Earn at least 88% on any additional C programming questions asked to be solved in class and that are assigned to this area. Finish any and all additional programs that I may add to the original 82 programs.
Become a Master of Chapter 2	6%	Finish all programs listed as simple recursive programs on the recursive program checklist (some of these are duplicates). Finish all required programs listed as divide and conquer programs on the recursive program checklist (some of these are duplicates). Finish all four programs listed as backtracking programs on the recursive program checklist (some of these are duplicates). Earn at least 88% of the points on exam/quiz questions related to simple, divide and conquer, and backtracking recursive questions.
Become a Master of Chapter 3	6%	Submit a working complex number module as indicated by the complex number assignment. Submit a working rational number module as indicated by the rationale number assignment. Earn at least 88% of the points on exam questions related to topics discussed in Chapter 3. Submit a working "Frequency of Digits Program for the Nth Fibonacci Number where N > 1000." Be able to coherently explain the two different ways Esakov and Weiss show how to achieve polymorophic data types in the C programming language.
Become a Master of Chapter 4 (Lists)	8%	Submit a working version of the Polynomial Addition Problem. Submit a working version of the Improved List Primitives Assignment ( Exercises 1a, 1d, and 1e) Submit a working version of the Graphical Display Lists Problem. Earn at least 88% of the points on questions pertaining to Section 4.1, 4.2, 4.3, and 4.4 Be able to recreate your solution to programming the equal function.
Become a Master of Chapter 5 (Stacks)	6%	Submit a working parenthesis checker case study. Submit a working graphical region fill case study. Submit a working index to postfix case study. Earn at least 88% of the points on in-class questions which cover topics in Section 5.1, 5.2, 5.3, 5.4, 5.5, 5.6, and 5.7.
Become a Master of Chapter 5 (Queues)	6%	Submit a working Operating System Simulator I case study. Submit a working Operation Systems Simulator II case study. Be able to discuss how these simulators work. Earn at least 88% of the points on in-class questions which cover topics in Section 5.8, 5.9, 5.10, and 5.11
Become a Master of Chapter 6 (Circular Linked List)	6%	Submit a working non-Polymorphic Alligators and Ducks (Hand out in class.) Submit a working Polymorphic Alligators and Ducks. Earn at least 88% of the points on in-class questions which cover topics in Sections 6.1. Submit a working Lisp Subset Interpreter Earn at least 88% of the points on in-class questions pertaining to Section 6.2. In particular, you should be able to doodle the data structures and be able to explain how the Lisp Subset Interpreter code works. Submit a working program that extends the Lisp Subset Interpreter to include exercises 2a and 2b. Be able to explain how you wrote your recursive Equal function (exercise 2b).
Become a Master of Chapter 6 (Doubly Linked List)	6%	Submit a working Simple Line Editor case study. Earn at least 88% of the points on in-class questions pertaining to Section 6.3. Earn at least 88% of the points on in-class questions pertaining to Section 6.4.
Become a Master of Chapter 7 (Trees)	8%	Submit a working Tree Traversal Assignment (Inorder, Preorder, Postorder, Level) Earn at least 88% of the points on in-class questions pertaining to Section 7.1 Earn at least 88% of the points on in-class questions pertaining to Section 7.2 Submit a working Expression Evaluator Assignment Earn at least 88% of the points on in-class questions pertaining to Section 7.3 Submit a working Operating Systems Simulator Assignment (Heaps) Earn at least 88% of the points on in-class questions pertaining to Section 7.4 and Section 7.5 Earn at least 88% of the points on in-class questions pertaining to Section 7.6 Submit a working Four-in-a-Row Game. Earn at least 88% of the points on in-class questions pertaining to Section 7.7
Become a Master of Chapter 7 (Graphs)	8%	Submit a working depth first traversal of a graph (adjacency matrix) Submit a working breadth first traversal of a graph (adjacency matrix) Submit a working version of Dijkstra's shortest path problem (adjacency matrix) Earn at least 88% of the points on questions pertaining to Section 7.8, Section 7.9, Section 7.10, and 7.11
Become a Master of Chapter 8 (Big Oh, Sets, and Searching)	8%	Submit a working Bit Vector Representation of Sets as described in the Bit Vector Assignment. Submit a working Sequential Arrays Representation of Sets as described in the Sequential Array Assignment. Submit a working Sequential List Representation of Sets as described in the List Implementation of Sets Assignments. Submit a working Hashing - Chaining Representation of Sets as described in the Hashing Handout. Be able to formally define the Big Oh notation. Earn at least 88% of the points on in-class questions pertaining to Section 8.1 and Section 8.2
Become a Master of Chapter 8 (Sorting)	8%	Submit working versions of all required sorting algorithms requested on the Sorting Checklist handout. Earn at least 88% of the points on all questions pertaining to Section 8.3 and pertaining to sorting in general. This includes knowledge of their general performance capabilities.
Attendance	4%	Attend at least 88% of the classes in which attendance was formally taken.
Miscellaneous	3%	Submit all miscellaneous assignments in a timely manner.
Unix, Emacs, GDB, Makefile	3%	Pass in makefiles for all programs that span two or more files.
Final Exam	8%	Score at least 88% on the final exam.