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