CSC 2400 (Design of Algorithms)

image created by Wordle

Syllabus (pdf format)

Practice Problems

1. Chapter 1 Problems
2. Chapter 2 Problems
3. Chapter 3 Problems
4. Chapter 4 Problems
5. Chapter 5 Problems
6. Chapter 8 Problems
7. Chapter 9 Problems

Interesting Articles

• Wikipedia article on the bisection algorithm for root finding
• Wikipedia article on Karatsuba algorithm for large integer multiplication
• Implementation and experiments with Karatsuba's algorithm
• Tuning Strassen's Algorithm for Memory Efficiency by Thottethodi et al.
• Fast Matrix Multiplication on Apple G4, by Crandall and Klivington, discusses Strassen's algorithm
• Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken
• Microsoft's TrueSkill(TM) ranking algorithm for Xbox Live gaming system
• Should Program Algorithms Be Patented?
• Email traffic patterns can reveal ringleaders
• Who Loves Ya, Baby? (about software for social networks)

Programming Assignments

1. Program 1
   • Program 1a (Microsoft Word format)
     • sample 8x8 table
     • another sample 8x8 table
   • Program 1b (Microsoft Word format)
2. Program 2
   • Program 2a
   • Program 2b

Late Policy for Programming Assignments

Algorithm Visualizations Developed by Fall 2003 and 2005 CSC 4400/5400 classes

Visualization of Brute-Force and Quickhull Algorithms for Convex Hull

Visualization of Jarvis' March (Giftwrapping) Algorithm for Convex Hull

Complete Collection of Algorithm Animations (from Hope College)

Dictionary of Algorithms and Data Structures (from National Institute of Standards and Technology)

Dynamic Programming Algorithm Information

• Dynamic Programming Poem (from Brandeis University)
• Animation of Floyd's Algorithm (from the University of Patras, Greece)
• Animation of Matrix Chain Algorithm (from the University of Auckland, New Zealand)
• Java source code for matrix chain multiplication, adapted from Neapolitan textbook
• Animation of Optimal Binary Search Tree Algorithm (from the Univ. of Auckland, New Zealand)
• Optimal Binary Search Trees (from the University of Manchester in the UK)
• Interactive Applet for Optimal Binary Search Trees (from ETH-Zurich in Switzerland)
• Dynamic Programming notes (from Iowa State University)
• Longest Common Subsequence algorithm notes (from Iowa State University)
• Some Realistic Word Lists (without frequencies)

Greedy Algorithm Information

• Animation of Prim's Minimum Spanning Tree Algorithm (from the University of Patras, Greece)
• Animation of Kruskal's Minimum Spanning Tree Algorithm (from the University of Patras, Greece)
• Animation of Kruskal's Minimum Spanning Tree Algorithm (from the Univ. of Western Australia)
• Michael Dipperstein's Huffman Code Page

Backtracking and Branch-and-Bound Algorithm Information

• Java Program for N-Queens problem with GUI
• crown picture for above program
• Java implementation of subset sum algorithm
• Java implementation of Hamiltonian Cycle algorithm
• Breadth-First and Best-First Branch-and-Bound Java implementations for the Knapsack Problem (zip file)

Traveling Salesman Problem page (from Princeton University)