| ||

## AlgorithmsInfo | Assignments | Syllabus | Resources | Roster | ||

Info
| ||

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

SyllabusThe syllabus isn't really set yet - we'll see what pace through the text feels comfortable, and what other topics you folks are interested in. | ||

Resources
- brief gprof notes
- book code
see this Makefile for Jim's adaptaion of something that compiled on akbar with "make". - listWords - Jim's code and make files
- Java Applet Sorting Demo
- Jim's Compression notes
- See
**cs.marlboro.edu/~mahoney/algorithms/** - Theory: NP-complete, Turing machines, and all that
- Godel's Incompleteness Theorem
- AMS Turing Machine Description
- Virtual Turing Machine
- Turing Test in Practice
- ALICE : state-of-the-art conversation
- slashdot interview with ALICE programmer
- A Compendium of NP optimization problems
- Wikipedia readings
- Game of Life
- Dijekstra's minumum graph path
An example of an interesting algorithm, and what the documentation of a project might look like. - a few notes on images and image compression
- JPEG description in the wikipedia, as well as other
- Discrete Cosine Transform notes. Also ColorFAQ.html in the same directory.
- JPEG specs and JFIF File Foramt
- Random Numbers
| ||

Jim Mahoney (mahoney@marlboro.edu)Last modified: Thu Dec 5 01:16:19 EST 2002 |