Contents of CSE 259 Home Page

• Course description and syllabus
• Course policy
• Homeworks and handouts
• Lecture notes & schedule
• Useful links

Course Description and Syllabus

A theoretical computer science course. Complexity analysis; algorithmic techniques (divide-and-conquer, greedy algorithms, dynamic programming). Trees, hash tables, heaps, graphs. Fast sorting algorithms, graph algorithms. The role of mathematical induction in correctness proofs. Investigation of examples from fields such as internet, computational geometry, and artificial intelligence.

Textbook: Algorithm Design, by Goodrich and Tamassia, Wiley 2002. ISBN: 0-471-38365-1

Prerequisite: CSE 254 and CSE 134. CSE 124 can replace CSE 134, if taken in Spring 2003 or earlier (or if transferred from outside of Storrs).

Course Policy

There will be homeworks (paper-and-pencil as well as programming projects), two midterms, and a final exam. The final grade will be computed as follows:

homeworks                 35%
midterms                     30%
final exam                   30%

class participation       5%

Homework should be turned in during class the day it is due. You are allowed to submit late (at the following lecture) one homework, which will account for anyone having problems with illness, emergency, etc. No other late homeworks will be accepted. 

Outside of lectures, we will communicate with you via the "announcements" page, linked at the top of this homepage.  Please check for new announcements daily.

Collaboration: You are encouraged to discuss problems and projects in a group. However, you must write up the solutions/programs in your own words. Copying is strictly forbidden. If you use any source other than the text, reference it/him/her in your solution/program, whether it be a person, a book, a solution set, a web page or whatever.

Homeworks and handouts

All homeworks will be handed out on-line, in this section. The following criteria are important for judging the quality of problem solutions:

     correctness (of the whole solution, not just the final answer);
     clarity (being able to state your thoughts clearly using proper terminology);
     conciseness (do not include unnecessary or irrelevant information).

Homework problems will be turned in in class, on paper, unless there are different instructions provided with the homework.

1. (1/19/05) Questionnaire (homework 0) - due 1/21/05 before class
2. (1/25/05) Homework 1 - to hand in on 2/1/05 in class
3. (2/01/05) Homework 2 - to hand in on 2/08/05 in class
4. (2/08/05) Homework 3 - to hand in on 2/15/05 in class
5. (2/17/05) Homework 4 - to hand in on 2/22/05 in class
6. (2/23/05) Homework 5 - to hand in on 3/01/05 in class
7. (3/16/05) Homework 6 - to hand in on 3/25/05 in class
8. (3/26/05) Homework 7 - to hand in on 3/31/05 in class
9. (4/01/05) Homework 8 - to hand in on 4/07/05 in class
10. (4/16/05) Homework 9 (MS Word) - to hand in on 4/21/05 in class
11. (4/22/05) Homework 10 - to hand in on 4/28/05 in class

Please refer to the Course Policy section for our collaboration policy.

Lecture Notes

Below is a tentative schedule for the semester. There will be lecture notes posted here after each lecture. Note: these notes may be incomplete. They are NOT a substitute for coming to class.

• Lecture 1, 1/18/05: Introduction
• Lecture 2, 1/20/05: Big-OH (PDF file, note reading assignment at end)
• Lecture 3, 1/25/05: More Big-OH (PDF file, note reading assignment at end)
• Lecture 4, 1/27/05: Analyzing Recursive Algorithms
• Lecture 5, 2/01/05: Analyzing Recursive Algorithms II
• Lecture 6, 2/03/05: Selection, Generic Sort
• Lecture 7, 2/08/05: Intro to ADTs
• Lecture 8, 2/10/05: Extendable Arrays, Amortized Time Analysis (PowerPoint)
• Lecture 9, 2/15/05: Priority Queues, Trees (PowerPoint)
• Lecture 10, 2/17/05: Binary Search Trees
• Lecture 11, 2/22/05: Heaps, HeapSort (PowerPoint)
• Lecture 12, 2/24/05: In-Place Sort, QuickSort (PowerPoint)
• Lecture 13, 3/01/05: QuickSelect (PowerPoint), Midterm Review
• Lecture 14, 3/03/05: Midterm I (on material through homework 5)
• Lecture 15, 3/15/05: Hash Tables I (PowerPoint)
• Lecture 16, 3/17/05: Midterm Discussion; Breadth-First Tree Traversal
• Lecture 17, 3/17/05: Hash Tables II, Radix Sort (PowerPoint)
• Lecture 18, 3/24/05: Sets and Set Operations
• Lecture 19, 3/29/05: AVL Trees
• Lecture 20, 3/31/05: Multi-Search Trees, Graph Intro (PowerPoint)
• Lecture 21, 4/05/05: Graph Implementations (PowerPoint)
• Lecture 22, 4/07/05: Undirected Graph Search (PowerPoint)
• Lecture 22a, 4/12/05: Midterm II
• Lecture 23, 4/14/05: Shortest Paths (PowerPoint)
• Lecture 24, 4/19/05: Minimum Spanning Trees (PowerPoint)
• Lecture 25, 4/21/05: Dynamic Programming (PowerPoint)
• Lecture 26, 4/26/05: More Dynamic Programming
• Lecture 27, 4/28/05: Hard Problems
• Review Session, 5/02/05: 12:30-1:45PM, room ITEB 127
• Final Exam, 5/06/05: 1-3PM, HEW 220

Useful Links

• Demos of data structures and graph algorithms
• Demo of 4 Sort Algorithms (note: it does not work for some versions of the browser)
• Spring 2005 UConn academic calendar
• Spring 2005 Schedule of CSE Courses

Other links will be added here throughout the semester.