1.1 Structures and Section 9.1 of your best friend
2.1 What is Recursion? (Review)
5.1 The Stack
5.2 Application: Parenthesis Checker
5.3 Stack Implementation: Static Array
|ix - xi
|The Perils of Java Schools
1.2 Unions and Section 9.8 from your best friend
2.2 The Towers of Hanoi
|1.3 Enumerated Types
2.3 Fibonacci Numbers
|1.4 Function Invocation
5.4 Application: Graphical Region Fill
5.5 Stack Implementation: Dynamic Arrays
|1.5 Pointers ( partial: Intro )
|1.5.1 Using Pointers to Return
4.1 List Concepts
4.2 Linked Lists (partial: Intro, 4.2.1, 4.2.2, 4.2.3 )
|1.5.2 Pointer and Arrays
4.2.4 Primitive Operations on Linked Lists
4.3.5 Additional List Primitive Operations
|1.5.3 Pointers and Structures
4.3.1 Polynomial Addition Program Design
4.3.2 Polynomial Driver
||1.5.4 Pointer Arithmetic
4.3.3 Polynomial Data Type Implementation
8.3.6 Radix Sorting
||1.6 Pointers to Functions
4.3.4 List Interface Routines for Polynomials
7.1 Trees and Graph Concepts
7.2 Binary Trees Intro
7.2.1 Traversing a Binary Tree
7.2.2 C Representation of Binary Trees
||1.8 Dynamic Memory Allocation
7.2.3 Primitive Operations on Binary Trees
Binary Search Trees
||5.8 The Queue
5.10 Queue Implementation: List Functions
3.1 Abstract Data Types
||6.1 Circular Lists Intro
3.2 Polymorphic Data Tyypes
||6.1.1 Primitive Operations on
3.3 Software Development and Life Cycle ( first part)
||Old Exams +
||Advanced C Constructs
||101 Programs 1-25
101 Programs 26-30
101 Programs 31-35
101 Programs 36-40
101 Programs 41-45
101 Programs 46-50
101 Programs 51-55
101 Programs 56-60
101 Programs 61-65
101 Programs 66-70
101 Programs 71-75
101 Programs 76-80
101 Programs 81-85
101 Programs 86-90
101 Programs 91-95
101 Programs 96-101
|Monday, Feb. 1
Monday, Feb. 8
Monday, Feb. 15
Monday, Feb. 22
Monday, March 1
Monday, March 8
Friday, March 12
Monday, March 22
Monday, March 22
Monday, March 29
Monday, April 5
Monday, April 12
Monday, April 19
Monday, April 26
Monday, May 3rd
Monday, May 10th
|Fall 2008 91.101 Computing Final|
|Section 2.1 (pp. 29-33)
Section 2.2 (pp. 33-35)
Section 2.3 (pp. 35-36)
Section 2.4 (pp. 36-37)
|Study Guide and Worksheet
||Data Structures and Software
|Study Guide and Worksheet
Powerpoint Slides 1
Chapter 3 Test
|Study Guide and Worksheet 1
Study Guide and Worksheet 2
|Chapter 4 Test
Chapter 4 Test (2007)
||Stacks and Queues
|Study Guide and Worksheet 1
Study Guide and Worksheet 2
Infix to Postfix 1
Infix to Postfix 2
Oper. System Sim 1
Oper. System Sim 2
||Advanced List Structures
Alligators and Ducks
Doubly Linked Lists
Simple Line Editor 1
|Chapter 6 Test|
||Trees and Graphs
Expr. Eval A
Expr. Eval B
Expr. Eval C
Graph Primitives AM
||Sets, Searching, and Sorting
|Bit Vector Assignment
Poly. Radix sort
||Read section 8.1 in Esakov.
||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 the four introductory
paragraphs that start Section 8.2
||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.
||Read Subsection 8.2.1
||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
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.
||(re) submit paper copies of
problems 11-20 of "Jim's Programming Problems" given in Computing I
||(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.
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
||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.
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.
||Read Section 5.2
||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.
stack.h, stack.c for the Parenthesis Checker Case Study.
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.
||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.
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.
||Selection Sort - the non
||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
Sort of Strings
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.
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
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.