957507 - Computer Algorithms, Spring 2009, DSU

957507 - Computer Algorithms, Spring 2009

"Computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better."
(Donald Knuth)

Announcements

May. 29 - The presentation schedule on June 9 (Tuesday) is as follows:
- 13:00 ~ 13:30 - Lee
- 13:30 ~ 14:00 - Tan
- 14:00 ~ 14:30 - Chai
- 14:30 ~ 15:00 - Singh
- 15:00 ~ 15:30 - Liew
- 15:30 ~ 16:00 - Ong
Note that I used List Randomizer. If you want to change the order, let me know.
May. 29 - Deadline of HW3 is extended to June 12.
Term paper presentation
- Singh will present PRIMES is in P.
- Liew will present A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles.
- Tan will present Dancing Links.
- Ong will present Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity.
- Chai will present Infinite versions of minesweeper are Turing complete
- Lee will present Some Minesweeper Configurations
May. 13 - Check the lecture notes - Shortest Path Supplemental Notes, Greedy Algorithm Supplemental Notes, Dynamic Programming, Sequence Alignment.
May. 9 - Check the term paper presentation section at the bottom.
May. 1 - HW3 (due May 31) posted.
Apr. 28 - Check the term paper presentation section at the bottom.
Apr. 10 - Check the lecture notes - Sorting Algorithms
Apr. 8 - Check the lecture notes - Asymptotic Complexity, Graph Algorithms, Sequence Alignment.
Apr. 8 - HW2 (due April 30) posted.
Mar. 24 - Advertisement: Google Summer of Code 2009 (due April 3).
- In order to promote the participation, the instructor will give A+ to the student with the accepted proposal to Google SoC.
- FAQ
- Timeline
- According to Google Summer of Code™ Terms of Service
  - "Google will provide a stipend of 5000 USD per developer, of which 4500 USD goes to the student and 500 USD to the Mentor Organization upon successful completion of a project. Students will be paid 500 USD upon start of coding work provided they are in good standing with their Mentor Organization, 2000 USD mid-Program provided sufficient progress has been made on their project, and 2000 USD at the close of the Program provided their project has been completed. "
Mar. 10 - HW1 (due March 31) posted.
Feb. 16 - This homepage is created.

Course Information

Course Objectives and Backgrounds - We will focus on a study of basic techniques for design and analysis of efficient algorithms. We emphasize on learning to formulate algorithmic problems and on developing problem-solving skills. Based on those above-mentioned objectives, fundamental techniques and concepts such as sorting, searching, graph algorithms, string processing and NP-completeness will be explored. We will also discuss design techniques such as dynamic programming as well as the greedy method, and asymptotic, worst-case, average-case and amortized analyses. We will cover data structures including heaps, hash tables, binary search trees and red-black trees.
Course Description
- Algorithms with numbers
- Randomized algorithms
- Divide-and-conquer algorithms
- Decompositions of graphs
- Paths in graphs
- Greedy algorithms
- Dynamic programming
- Linear programming and reductions
- NP-complete problems
- Coping with NP-completeness
- Quantum algorithms