91.102 Section 201 Computing II (Spring 2008)           

Last updated: May 4, 2008

** Changed topological sort assignment.
** Added optional assignments


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

You need to submit these on or before the date stated.

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,

                                        % submit abaumann p9 main.c list.c list.h polynomial.h polynomial.c  list_interface.h list_interface.c globals.h 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 grader

Submit to
Assignment Name
Grader's Name
Electronic Due Date
Program Name
abaumann
p9
Alex Baumann
Saturday, March 15
polynomial addition
mpianted
p10
Michael Piantedosi
Saturday, March 15
radix sort
abaumann
p14
Alex Bauman
Sunday, March 16
ackermann
mpianted
p15
Michael Piantedosi
Sunday, March 16
shell sort
abaumann
p16
Alex Baumann
Monday, March 17
recursive persistence
mpianted
p17
Michael Piantedosi
Monday, March 17
parentheses checker
abaumann
p18
Alex Baumann
Tuesday, March 18
non-polymorphic quicksort
mpianted
p19
Michael Piantedosi
Tuesday, March 18
graphical region fill
abaumann
p20
Alex Baumann
Wednesday, March 19
infix to postfix
mpianted
p21
Michael Piantedosi
Wednesday, March 19
tromino tiling
abaumann
p22
Alex Baumann
Thursday, March 20
knight's tour
mpianted
p23
Michael Piantedosi
Thursday, March 21
eight queens
abaumann
p24
Alex Baumann
Friday, March 22
OS Simulator V1
mpianted
p25
Michael Piantedosi
Friday, March 22
OS Simulator V2
abaumann
p26
Alex Baumann
Wednesday, March 26
Tree Traversal
mpianted
p27
Michael Piantedosi
Sunday, March 30
OS Simulator V3
abaumann
p28
Alex Baumann
Monday, March 31
Mergesort (doubles)
mpianted
p29
Michael Piantedosi
April 10, 2008
Polymorphic Alligators and Ducks.
abaumann
p30
Alex Baumann
April 14, 2008
Heap_sort
mpianted
p31
Michael Piantedosi
April 20, 2008
Polymorphic Quick_Sort
abaumann
p32
Alex Baumann
May 5, 2008
Four in A Row
mpianted
p33
Michael Piantedosi
May 5, 2008
Strassen's Matrix Multiply
abaumann
p34
Alex Baumann
May 11, 2008
Depth First Traversal of a Graph
mpianted
p35
Michael Piantedosi
May 14, 2008
Dijkstra's Shortest Path
abaumann
p36
Alex Baumann
May 14, 2008
Hashing
mpianted
p37
Michael Piantedosi
May 14, 2008
Breadth First Search of a Graph
abaumann
p38
Alex Baumann
May 14, 2008
Topological Sort
canning
GDL
Jim Canning
No later than the day of the final.
Graphical Display Lists
canning
LSS
Jim Canning
No later than the day of the final.
Lisp Subset Interpreter
canning
SLE
Jim Canning
No later than the day of the final.
Simple Line Editor
canning
EXP
Jim Canning
No later than the day of the final.
Expression Evaluator
canning
AVL
Jim Canning
No later than the day of the final.
Polymorphic AVL trees


Powerpoint Lecture Notes
Things to Notice

Notice 4) You need to know how to fill out memory templates. They are not difficult to do, but you need to practice them. Here are some memory template exercises.
 
Notice 3) Read Alice Hamachek's book. It is about study habits and college life. Incorporate her thoughts into your schedule and behavior.

Notice 2) Remember. Download and rework the Computing I final.  You can learn how to do these problems. Once you know them, then you will own them for life. I want you to own it for life. You can do it.

Notice 1)
I am thrilled with the programming effort that most of you are generating. If you have not jumped in yet, please start today. If you are struggling to get started, let me know. You can either come to my office or send an email to me. The goal is to get all of you to feel what is going on.


Instructor: Jim Canning
Office:      Olsen Hall, Room 231
Email:       jim@cs.uml.edu
Office Hours: M, W, F from 10:30 - 12:00 noon

Prerequisites

91.101 Computing I or equivalent. C programming and UNIX skills.
 
A personal commitment to excel in school.

You should be able to maneuver around the UNIX environment. You should be able to program - without too much difficulty - the first 72 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, I think 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 fairly high 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.

Objectives

         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 semester.
       23) write a C program that relies upon a hashing implementation of polymorphic sets.

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 of them. I hope we have time to do many of them in this course.

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 (This book is available free on-line. It would be good for you to have your own copy.)
    
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
Motivating Students to Become Responsible for Learning, Part I, by J. Dirk Nelson
Get it Write: Which or That?

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.

Attendance

Class attendance is mandatory. Two points for those who come to class and sign the attendance sheet. Zero points if you miss class. If you come in late you run the risk of earning only 1 attendance point.

Late Work

I encourage all of you to do all the work. All work should be handed in on time. For each assignment there are due dates. 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.

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.

Reading and Doodling

Reading a textbook for detail is an important academic activity. It is the skill most of you need 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. You should 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 you should make a list of possible questions that could appear on a future exam. You should 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. Slow, but sure, wins the race. Take notes as you read.

Our textbook contains 360 pages spread across eight chapters. The semester contains 108 calendar days. If you average four pages of reading per day you can cover the book. How long does it take to read and fully understand four pages? Sometimes this can go quite fast. Sometimes it moves a bit more slowly. Commit yourself to reading, on average, four pages per day from our textbook. If you skip a day, then you will need to read eight 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.

Programming Skills

I am from the old school. Your programming skills can be sharpened through practice. You must write lots of programs. You must practice.  We are trying to have you build a base of knowledge that will serve you well. The goal is for you to become confident, solid programmers. I do not believe this is difficult. I see this as a significant time investment. I see this as worthwhile. You can do it.

Programming Style Guide

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

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.

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 details. 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 then that really matters. Never mistake activity for achievement. Who said that?

Shortcuts

There are no shortcuts.

Grading

Your grade will be determined from points earned in all activities including: attendance, homeworks, in-class tests, portfolio's produced, programming assignments, quality of all work handed in, and the final exam.

Attitude

Be positive. Try. If you are struggling, try. 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 consistently arrive late. 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. Apply these suggestions to all of your classes.
 
Score Sheets

           Recursive Programming Score Sheet
           Sorting Score Sheet
           Course Score Sheet

Previous Exams Given

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

Topics

            Big O Notation
            C Programming
            Sorting (bubble, selection, insertion, shell, radix, quicksort, heapsort, mergesort, topological)
            Recursion (tail, divide and conquer, backtracking)
            Data Abstraction
            Linked Lists
            Programming Tools( gcc, make, gdb, emacs)
            Sets
            Hashing
            Circular and Doubly Linked Lists
            Queues
            Trees - Binary and N-Ary
            Tree Traversal
            Binary Search Trees
            AVL Trees
            Graphs
           

Things to Do

Task

Description
Due Date
Comment
Estimated Time to Perform the Task
Deliverable to Pass In?
1

Obtain the Esakov book.
Jan. 28
Online or at the UML Bookstore

No
2

Obtain the Alice Hamachek book.
Jan. 28
Online or at the UML Bookstore

No
3

Obtain Strunk and White's The Elements of Style.
Jan. 28
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.

No
4

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

No
5

Read section 8.1 in Esakov.
Jan. 28
Record how long it took you to read it. Place your time in the reading week 1 checklist sheet.
15 minutes
No
6

Read E.B. White's Introduction.
Jan. 28
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 ...
20 minutes
No
7

Read section 1.1 in Esakov.
Jan. 29
Record how long it took you to read it. Fill  out reading checklist entry.
15 minutes
No
8

Read section 1.2 in Esakov.
Jan. 29
Record how long it took you to read it. Fill out reading checklist  entry.
  5 minutes
No
9

Read section 1.3 in Esakov.
Jan. 29
Record how long it took you to read it. Fill out reading checklist entry.
 5 minutes
No
10

Read section 1.4 in Esakov.
Jan. 29
Record how long it took you to read it. Fill out reading checklist entry.
20
No
11

Read RLWM article.
Jan. 29
Record how long it took you to read it. Fill out reading checklist entry.
30
No
12

Read section 2.1 in Esakov.
Jan. 30
Record how long it took you to read it. Fill out reading checklist entry.
25
No
13

Read section 3.1 in Esakov.
Jan. 30
Record how long it took you to read it. Fill out reading checklist entry.
20
No
14

Read section 4.1 in Esakov.
Jan. 30
Record how long it took you to read it. Fill out reading checklist entry.
10
No
15

Pass in week 1 reading checklist
Feb. 4


Yes
16

Homework 1
Jan. 30
Record how long it took you to read it. Fill out homework checklist entry.
30
Yes
17

Program 1 (Factorial)
Jan. 30
Record how long it took you to get this to work. Fill out the programming checklist.
20
Yes
18

Program 2 (Power)
Jan. 30
Record how long it took you to get this to work. Fill out the programming checklist.
20
Yes
19

Program 3 (Minmax)
Jan. 31
Record how long it took you to get this to work. Fill out the programming checklist.
30
Yes
20

Program 4 (GCD)
Jan. 31
Record how long it took you to get this to work. Fill out the programming checklist.
20
Yes
21

Read sections 3.2 - 3.4
Feb. 1
Friday nights are made for studying. Take your time.
45
No
22

Program 5 (Bubble Sort)
Feb. 1
Record how long it took you to get this to work. Fill out the programming checklist.
30
Yes
23

Program 6 (Rational Number)
Feb. 8
Take an hour on Saturday February 2nd and get this done.
60
Yes
24

Homework 2
Feb. 4
Getting you started with the code in Chapter 4 as quickly as possible.
90
      Yes
25

Read section 4.2
Feb. 4
Polynomial Addition using Polymorphic Linked Lists - You need to fully understand this code. No shortcuts.
90

26

Program 7 (Selection Sort)
Feb. 4
Record how long it took you to get this to work. Fill out the programming checklist.
15
Yes
27

Read section 4.3
Feb. 5
Polynomial Addition using Polymorphic Linked Lists
120

28

Program 8 (Insertion Sort)
Feb. 6
Record how long it took you to get this to work. Fill out the programming checklist.
25
Yes
29

Homework 3
Feb. 11
Get started early - this involves the polynomial addition problem in Chapter 4.
w/ Task 26 (4 hours)
Yes
30

Program 9 (Polynomial Addition)
Feb. 11
You need to fully understand this code. You must get the idea. No shortcuts. If you get this base, the rest is easier.
 w/ Task 25
Yes
31

Program 10 (Radix Sort)
Feb. 20
Read Section 8.3.6. We will discuss this in class.
 90 minutes
Yes
32

Program 11 (Print a List)
Feb. 9
This is an easy one. The same one as last semester. I gave it to you. Type it in. Get it to work. Understand it.
25 minutes
Yes
33

Program 12 (Fib of Order 2)
Feb. 10
Easy Peasy - but if you do not fully understand it - you need to get immediate help. You can do it.
10 minutes
Yes
34

Program 13 (Fib of Order 3)
Feb. 11
Easy Peasy - but if you do not fully understand it - you need toget immediate help.  You can do it.
5 minutes
Yes
35

Pass in week 2 Reading checklist
Feb. 11
Carry your book around with you. Read it. Make sure you understand the code in it. If you do not understand something - ask me immediately. You can do this. I know that you can do it.

Yes

36

Program 14(Ackermann)
Feb. 13
You can do this. Code is easy. Time to record information is another thing.
15 minutes to code
longer to fill the table
Yes
37

Program 15(Shell Sort)
Feb. 15
This is not hard to code up. I gave it to you in class.  You need to make sure that you can walk through the code. You need to be able to explain it to me. Do not just type, compile, hand-in, and go. Study it.
    15 minutes to code
longer to mentally and slowly walk through it.
Yes
38

Redo Computing I Final Exam Part I
Feb. 1
I am not collecting this. But, you should print out the 91.101 final exam and work yourself through it. You can ask me any question you wish about it. This is pre-requisite knowledge for the course. If you cannot do the any single question, ask for help immediately. Be your own best champion.

45 minutes
No
39

READ 5.1, 5.2, 5.3
Feb. 16,17
Are you reading 4 pages of your textbook per day? Please try. Make sure that you read sections 5.1, 5.2, and 5.3 during this weekend. Read the sections twice. Doodle pictures of them. You will need code up the parenthesis checker program soon. Read the pages before we talk about it in class. It is only 10 pages.
      90 minutes
No
40

Program 16 (Recursive Persistence)
Feb. 18
Download the Simple C Programming Problems document. The link is found above in the course prerequisites paragraph.  I want you to solve program 28 (Persistence), but this time, craft a recursive solution.
30 minutes
      Yes
41

Program 17 (Parenthesis Checker)
Feb. 25
In section 5.2 of your book the authors give the Parenthesis Checker application. It contains a main function, stack interface routines, and relies upon a static array implementation of stacks. This implementation of stacks is given in  section 5.3. Aworking executable of this program is found in the file:  ~canning/public/102/ch5/parenchecker. Remember to used multiple files. If you can do this program you are definitely getting stronger. If you cannot do this program, you need to seek immediate help to get you oriented. You will need to e-submit this program to a grader. You will need to hardcopy submit this to me.
120 minutes
Yes
42

Redo Computing I Final Exam Part II
Feb. 23
I am not collecting this. But you should do it. It is a Saturday. Find some quiet time and a well-lit space and make sure that you can do every single problem on this test. It you are not able to do this, then you need to ask questions. Be your own best champion. You can do this. Make the time. Get fired up.
45 minutes
No
43

Program 18 (Non -polymorhphic Quicksort)
Feb. 25
You should feel free to hand this program in early. I gave it to you last semester. I gave it to you again this semester. You need to understand how this divide and conquer O(n log n) sort works. Can you explain it to me? Can you explain it to a friend?
30 minutes
Yes
44

Program 19
Graphical Region Fill
Feb.
 27
Read sections 5.4 and 5.5 closely. Then enter this code into your mercury account.  You will have multiple files. The file main.c will contain both the main function and the fill function. It will also contain the #defines listed on page 115.  You will need to create an image .h file and an image.c file. The functions init_image, read_pixel, write_pixel, and display_image will go into image.c  You will use an interface module. Interface.c will contain push_xy and pop_xy. You need to implement and understand the dynamic array implementation of a stack data structure given in section 5.5 We will discusss this in class. But please, get a head start on it now. I think most of you can enter this code and get it working. You can always execute my executable of it. It is located in my public directory.
 4 hours

Do not just type it in. Understand it.
Yes
45

Program 20
Infix to Postfix

Mar. 3
Read section 5.6 and 5.7 closely. Then enter this code into your mercury account. You can do this. You will have multiple files.  Can you determine what they should be? We will discuss this in class.  I have a working executable in my public directory.
4 hours
Yes
46

Review Chapter 4 test
Mar. 1
I have posted two links above which are linked to old chapter 4 exams. Please download these exams and practice them before the test on Wednesday March 5th. You should do this over the weekend.
2-3 hours
No
47

Program 21
Tromino Tiling
Mar. 7
or earlier
This is problem 64 from 91.101 Computing I. We went over this in class on Thursday Feb. 27th. I handed out the problem in class then. You can also obtain the problem by downloading the link at the top of this webpage entitled, Simple C Programming Problems. The base code for this problem can be found in chapter 4 of your Computing I textbook. However, it is necessary to present the solution according to the handout given (problem 64).  This program should use a recursive divide and conquer strategy.  A working executable of this problem can be found in my public directory. A solution is not unique.
1-3 hours
Yes
48

Give yourself a round of applause

If you have made it this far, stand up and give yourself a round of applause. Many of you have come a long long way since September.  You can make it the rest of the way. Spring break is not too far away. That sounds like a great chance to write lots of code without interruption. Squirrel yourself away and get these case studies to work during break. You would come back after vacation feeling great and on top of the world. At least you'd be on top of Mount Monadnock.
10 seconds
No
49


Program 22
Knight's Tour
Mar 10.
A working executable of the knight's tour problem can be found in my public directory. You need to write a recursive, backtracking program that produces a knight's tour of an n x n grid as discussed in class.  To run the program you should present a command line that looks like similar to this: $ a.out 5 1 2.  That is,  the size of the matrix and the x and y coordinates of the starting point.
1-4 hours
Yes
50

Program 23
Eight Queens
Mar 13
You need to create a recursive C program that will find all solutions to the Eight Queens problem. Your program should output the number of correct solutions.
1-4 hours
Yes




Remember the goal. We want to have all 53 students in this class know exactly what they are doing. This is within our reach.


51

Program 24
OS Simulator-V1
Mar. 14
This code is located in chapter 5 of Esakov and Weiss's textbook. The code given does require one or two changes. Can you find them? For this program you should use the queue implementation given in section 5.10
1-3 hours
Yes
52

Program 25
OS Simulator -V2
Mar
14.
This is the same case study as program 24 except that you should remove the queue implementation given in 5.10 and replace it with the queue implementation in section 5.11. Once you have gotten Program 24 to work, there is not much typing or work left to do for this program. However, please make sure that you understand the code. You are not just typing the code in to get it to work. You need to be able to explain what it is doing to another person.
1 hour
Yes
53

Read Section 7.1
Mar 15.
After you have completed both of the OS Simulators, you should sit yourself down and read section 7.1. You should take notes as you do . What is a graph? What is an undirected graph? What is a tree. What is the most common kind of tree used in computer science?
30 minutes if done well.
5 minutes if rushed.
No
54

Read the intro to Section 7.2, read subsection 7.2.1, read
Mar 16
Read these pages closely and slowly. Read them with a pencil in your hand. What is a binary tree? What is the depth of a binary tree? Can you perform an inorder traversal? a preorder? a postorder? a level order?  Get away from any distractions you may have around you. Go to a library and set aside 1 full hour to read this material.  Make up some practice trees and traverse them on your own. Go to the computer science section of the library you are in, find a data structures book and read the section in that book that talks about inorder traversals of a binary tree. Read the example provided in this other textbook. Make sure you understand it. Your campus library is a great place. The one on north campus has the computer science section. Have you found it yet? This is your time to be a student.
1 hour
No
55

Read section 7.2.2
Mar 17
It is only five glorious pages. You need to walk through each of the functions, #defines, and typedef given. Do you see how this code hangs together? There is no main function given so you need to imagine one. The next task will help you understand this code.
2 hours if done well. What else is their to do?
No
56

Program 26 (TreeTraverse)
 Mar.
26
Although this is due after spring break, you should get it done well in advance. You can do this. There will be other assignments to work on in this class. There will be other assignments to work on in your other classes. Get it done early. Put it to bed. You can do it. Do not wait.
4 hours
Yes
57

Read section 7.4
Spring Break or earlie
For now, we will skip over section 7.3 You should read section 7.4 entitled Heaps. It is 8 pages long. We will discuss heaps in class before break so that you will have an orientation. Is it possible for you to come to Olsen Hall over break and doodle the code on a white board? If so - I think that would be wise.  If not, find a white board elsewhere. White boards are useful learning tools. Have you figured this out?  If I gave you a list on numbers can you put them into a heap? Do you see how the code is doing it?
2-4 hours
No
58

Read section 7.5
Spring Break
Just a hair over 3 pages, but if you can understand those three pages and redo the OS Simulator as directed, I welcome you to the top of Mount Monadnock (see task 59). We are going to have a picnic on the mountain, I am bringing the jelly beans. What are you bringing?
1- 2 hours
make sure you get it.
No
59

Program 27
OS Simulator - V3
Mar.
30th
You should make a OSSimulator subdirectory within your ch7 directory. You do have a ch7 directory? Make a copy of your OS simulator code that is in your ch5 directory. This will be a starting point. Remember to make a copy of globals.h and whatever else you need. Do not copy a bunch of stuff over if you do not need it.  Wouldn't it be wonderful to have this all done before spring break is over? You should make this your goal. Some of your classmates already have it done. How about you? We want all 53 students in the class to get this. Not just a few students. The effort you put forth now will help you later.
2-4 hours
Yes
60

Give yourself another round of applause

If you have gotten to this point, then you deserve a huge ovation. I salute you. I do not see anything that can stop you from here on in. You have come a long way since September.
30 seconds
No
61

Read section 8.3.2
Should do this during break week.


This section is entitled mergesort. It is five pages long. We discussed these pages in class on Friday, March 14. A handout was given. Reading these pages implies that you will take the time to fully understand the code. Notice how this code is polymorphic but it does not use generic pointers. It takes advantage of the memcpy function to achieve data independence.
60 minutes
No
62

Program 28
Final Due Date:
May 5th
Using the handout passed out in class as your guide, write a program that will fill an array with 500,000 doubles and then sorts these numbers using the polymorphic mergesort discussed in the book and also given out in class.
     45 minutes
  Yes
63


Should do this during break week
Chapter 6 is entitled Advanced List Structures. It starts off by explaining circularly linked list using a data independent strategy. You should read section 6.1 in its entirety. Reading this section means that you have slowly and thoroughly walked through all seven primitive routines that are given. After reading these routines, you create a ch6 subdirectory within your 102 directory. You should create an alligators subdirectory within your ch6 directory.  You then need to move a copy of globals.h into your alligators directory. You then need to create a circular.h and a circular.c file in this directory and type in the declarations and definitions of these seven circular primitive functions.
3 hours
No
 64


Break week would be ideal.
Ok, now you can jump to section 6.2.9 on page 181. Read it slowly and deeply. It is only 3 pages long. It contains four more circular linked list primitive operations. Type them into your circular.h and circular.c files.
2 hours
No
65

Program 29
Final Due Date:
May 5th
In class I passed out the Alligators and Ducks program from last semester. It is a non-polymorphic implementation. You need to redo this program by using the polymorphic circular linked list primitives. I have done this. The executable version of this is located in my public directory. It is called ducks. As you might imagine, there is not too much typing to do after you have the circular.c and the circular.h files up and running.  Your solution should create an interface module( ducksinterface.h and ducksinterface.h). Much like radix sort, there are two functions in ducksinterface.c. They are: getnextduck and circ_append_duck. It is a fun and fulfilling experience to reflect how to use the circular linked list primitives to accomplish the task. If you need some orientation from me, you can ask -- but I thought you would not want me to take the J out of joy. Your executable should produce the same output that mine produces.
      2 - 3 hours
Yes
66

board.h
As soon as you read this, but no later than March 25th
Go to page 275 in your textbook. This is section 7.7.3 entitled The Game Board. It contains the #defines and typedefs for the FourinaRow program. Create a Fourinarow subdirectory within you ch7 directory. We are going to learn how this program works.  You are going to create a working version of it. For now, I just want you to create board.h. This file contains the #define and typedefs given on page 275. Do this now. This file also contains four function declarations only. The functions definitions are given on pages 275, 276, and 277. Complete board.h by typing in these four function declarations only.
10-20 minutes
No
67

board.c
How about now? It would not take you long to do.
Create your board.c file by entering the four function definitions given on pages 275, 276, and 277.
15 - 30 minutes
No
68

Program 30 Heapsort
April 15th
In the public directory ... 102/ch8 ... there is a file called mainheap.c. Copy this file to your directory and use it. You need to complete the definition of the  compare_ints function.  You need to implement heap.h and heap.c. The function definitions for the heapsort algorithm are given in chapter 8 of your textbook.  You should make sure you understand how the heapsort algorithm does its job. You can do it.
45 - 2 hours
Yes
69

Program 31
Polymorphic
Quicksort
Final Due Date:
May 5th
In chapter 8 of your textbook you will find the code for a polymorphic quicksort algorithm. You can see that this algortihm does not use generic pointers, but rather takes advantage of the sizeof operator to move the appropriate number of bytes. We discussed this in class. Please code this algorithm up. You should re-use the main.c file for task 68 except you should call quick_sort rather than heap_sort.
1 hour
Yes
70

Program 32
Four in A Row
Final Due Date:
May 5th
By now many of you have already passed in the "Four in a Row Program". Thank you. I hope you enjoyed getting it to work.  You need to submit this program electronically too. For those of you who are lagging behind, you have until May 5th to get this code to work and to submit it electronically. Please do it. You should understand how it works too.
3 hours
Yes
71

Program 33
Strassen's Matrix Multiply
Final Due Date:
May 5th
Hi 91.102 students. For those of you who will pick up the challenge of coding up Strassen's Matrix Multiply, you need to hand in your hardcopy and your electronic copy on or before May 5th.

NOTE: In addition, I want you to hand in a nice looking table or graph that shows the times you obtained when multiplying matrices containing floating point doubles of varying sizes of n, where n is a power of 2 (8, 16, 32, 64, 128, etc... ) Your table or graph should also contain timings for the standard order n-cubed code that I handed out in class. This code also used malloc if you recall. At the bottom or top of your graph or table you should clearly tell me where the crossover point is. Where does Strassen's timing start to outperform the timings for the standard approach? Does it?

Remember this problem provide you with an opportunity to practice thinking about divide and conquer and it also gives you practice in mallocing up space for a two-dimensional array. Then you need to practice referencing elements of a a malloced-up two dimensional array.

Have fun! Get cracking.

3 hours
Yes
72

Re-read Section 7.1

Re-read section 7.1. It is about trees and graphs.
15 minutes
No
73

Read Section 7.9

Section 7.9 is about graphs. It provides you with a traverse function and the code for a depth first traversal of a graph. It does not provide you with a main routine that calls the traverse function.  It does not provide code to you for the creation of a breadth first traversal of a graph. You should take the time to read this. You will notice that some of the functions this code calls are located in later sections. Section 7.10 builds the set of graph primitives using an adjacency matrx approach.  Section 7.12 builds the graph primitives using an adjacency list approach.
45 minutes
No
74

Program 34
Depth First Traversal of a Graph
Final Due Date:
May 11
As always, you should create a separate directory within your chapter 7 directory for this assignment. I want you to type in and understand the code for all of the graph primitive functions in section 7.10. How many graph primitive functions are there? Well, isn't it only six: init_graph, destroy_graph, add_edge, delete_edge, isadjacent, graph_size, and edge_iterator? That does not seem too bad. After typing these functions into your system, then you need to type in both the functions in section 7.9. They are traverse_graph and depth_first_search. However, since you have not yet written breadth_first_search, you can comment this out. Now go to my public directory and retrieve my depthmain.c function that I have in there. Use this function as you driver. You final program should perform a depth first traversal of a graph -- using the adjacency matrix strategy outlined in the book.  You will also find a file called graph1 in the ~canning/public/102/ch7 directory. You can use this and you should make up your own data files too.
3 hours
Yes
75

Program 35
Dijkstra's Shortest Path
Final Due Date: May 14
The Esakov and Weiss version of Dijkstra's Shortest Path problem is given in Section 7.11. Three functions are provided. It does not give you a main driver function. I have created the main driver function for you. It is located in the ~canning/public/102/ch7 directory. It is called dijkstramain.c. You need to get all of this together and get it to work like mine. As always submit both paper and electronic copies.

To do this assignment you may re-use the adjacency matrix implementation of a graph that was found in section 7.10.
90 minutes
Yes
76

Program 36
Hashing
FINAL Due
Date: May 14
Chapter 8 of your book is entitled: Sets, Searching, and Sorting. We've covered the sorting portion fairly completely. Now we need to get familiar with the sets and searching piece. For this assignment we are going to implement the material in section 8.2.4. This section is called Hashing. In my public directory, within the 102/ch8 directory there is a hashing subdirectory. It contains a main.c and a textfile1 file. You should use these files. It also contains a binary executable of the working program so you may compare it with yours. You need to code up and assemble the routines found in section 8.2.4 so that your program works like mine. As always, you need to understand the code as you get it to work. Good luck.
2.5 hours
Yes
77

Program 37
Breadth First
FINAL Due
Date: May 14
Your book does not provide code for a breadth traversal of a graph. It would be a good exercise for you to do this. I have a working executable in my public directory. This will complete our implementation of sorting algorithms. You have done a nice job to date. It will be terrific if you can finish it off with this last one. Remember this will require your use of a queue and it is similar to our level traversal of a binary search tree.  Hang in there. You are almost done.
2 hours
Yes
78

Program 38
Topological Sort
Final Due Date: May 14
We will discuss the topological sort in class. This problem is similar to depth first search except you need to keep track of the in-degree of each vertex. Once you've done Program 37, there is not much more to do to get this one done.
1 hour
Yes


OPTIONAL

OPTIONAL:  The assignments listed below are optional. Some of you have already done them. Some of you would be willing to do them.


OPT
1

Program 39
(Optional)
Graphical Display Lists
Hard copy
is due the day of the final exam.
This is an optional assignment.  You should electronically submit this to me.

 In the back half of chapter 4, the Graphical Display Lists application is given. I have a working version in my public directory.   You should electronically submit this to me.


OPT
2

Program 40
(Optional)
Lisp Subset Interpreter
Hard copy is due the day of the final.
This is an optional assignment. You should electronically submit this to me.

The first application given in chapter 6 is the Lisp Subset Interpreter. Get this code to work. Some of you have already done so. It would be great if more of you did this. This is a wonderful program for you to learn. If you can do this before the final, great. If you cannot -- then I encourage you to work on this after the semester is over. If you ever get it done, feel free to let me know.


OPT
3

Program 41
(Optional)
Simple Line Editor


Hard copy is due the day of the final.
This is an optional assignment. You should electronically submit this to me.

The second application given in chapter 6 is the Simple Line Editor. It relies on doubly linked lists. Get this code to work. Some of you have already done so. It would be great if more of you did this. If you cannot do this program before classes let out, then I encourage you to get it done after school lets out.


OPT
4

Program 42
(Optional)
Expression Evaluator
Hard copy is due the day of the final
This is an optional assignment. You should electronically submit this to me.

We have done almost all the applications within chapter 7. One application we did not do was the Expression Evaluator. Get this code to work. Understand it. Read it and Feel it. At least one of you has already done this program. I am hoping that more of you will do it.


OPT
5

Program 43
(Optional
AVL trees0

Implement polymorphic AVL trees.