# Algorithms

Info | Assignments | Syllabus | Resources | Roster

Info
 An examination of some of the classic recipes of computer science, such as searching methods and data structures, hashes, monte carlo methods, parsing,and cryptography. Expect some math. Other topics may include Turing machines and cellular automata. When: Tu/Thur 11:30-12:50 Where: Sci 117 Faculty: Jim Mahoney Text: Mastering Algorithms with C by Kyle Loudon. Credits: 4 ( 9 hours/week outside class ) Prereq: none

Assignments
1. 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?

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

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

4. (Haven't managed to keep up with putting assignments here, though I have given them out in class.)

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

Syllabus

The 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

Jim Mahoney (mahoney@marlboro.edu)