Assignments
- for Thur Sep 12
- read chapters 2 (pointers) and 3 (recursion)
- The Fibonnaci numbers F(n) are 1,1,2,3,5,8,... where
each number is the sum of the previous two.
- Write a C program that allocates a block of memory
for the first 100 Fibonacci numbers, and then finds them
and copies them into sequential memory locations, refering
to them with pointers.
- Write another C program that calculates F(n) with
recursion explicitly and the idea that F(n) = F(n-1) + F(n-2)
- Which of these is faster? Can you measure their
speed? What is their behaviour as n gets bigger?
Can you plot a graph of how fast they run
as a function of how high n is for your code?
Which takes more memory? Can you measure this?
- for Thur Sep 17 (or Tues of following?)
- Read chapters 5, 6, 7, on Lists, Queues, and Sets
- Write a C program which reads some number N of words
from the dictionary file /usr/share/lib/dict/words on akbar.
and stores them as a list.
Let the characters 0..9a..zA..Z have the values
0-9, 10-36, 37-63. Write an algorithm to search your list
for the largest word. How long does this take to run
as a function of N, the number of words in your table?
("gprof" may be the tool to help you see how long it takes to run.)
- Using this same numeric value for each word, alter your
program to put each word into the correct sequential place
in the list, using a simple "look down the list" approach.
How does this run time behave?
- for Thurs Oct 3
- An example of the last assignment is
in this directory
- Read pgs 303-305 of the text, on Insertion Sort.
Expand the linked list example from last time
to include sorting the list. Again, find the
time it takes to run as a function of nWords.
What is its behavior on this data?
- Modify the program again so that it stores the data
in an array rather than a list. Does this
make it faster or slower? What are the advantages
or disadvantages?
- Read chapter 8 on Hash Tables. Coming up soon:
counting word frequencies in a large file
using a hash. (If you'd like to start on an implementation,
go ahead.)
- (Haven't managed to keep up with putting assignments here, though
I have given them out in class.)
- End of Term project
- Choose one of the topics we've covered this semester
(or a related issue such as one of the NP-complete problems)
to look at more closely. Either write a research paper on
that topic or (preferably) write some code (including
documentation, as discussed in class) that explores
and illustrates the topic. Talk with me about your choice of topic.
|