Abstract

Programs run much faster than they used to do a few decades ago not only because of better hardware but also because of better algorithms developed for solving problems. In this course we look into algorithms for some traditional problems like sorting, or those related to graph theory. We will also delve into four different styles of algorithm development: divide and conquer, greedy strategy, dynamic programming, and backtracking with some general purpose pruning techniques. Some examples will be worked out in the class for these strategies, and students are expected to be able to hand simulate runing algorithms on problem instances. We also look into different mathematical tools to analyze an algorithm's complexity. The course concludes with a simplistic introduction to the theory of NP-completeness and its significance in computer science.

The syllabus is here,
a rather detailed but tentative course content

Primary means of achieveing the objective of the course are:
(1) Expose many algorithms (around 20),
(2) Dry run on examples, to understand the principles behind these algorithms,
(3) Look at formally written algorithms, for most of them, to practice on how to write algorithms,
(4) Remain sensitive to their asymptotic time-complexity, often analyze them formally, sometimes being sensitive to the space requirement of the algorithms.

Expectations from students are:
(1) Dry run on as many examples as possible for each algorithm,
(2) Analyze and be sensitive to time/steps and space requirements,
(3) Modify a problem and see how a known algorithm should be changed (for advanced algorithms learning),
(4) Map a unknown problem to a known problem and adopt the corresponding known algorithm for the job (we do it occasionally as exercise),
(5) Solve completely unknown problems, using the expertise gained (as one would have to do in the real life).

WARNING: I may use mostly MS Word documents for presentation in the class and from the same notes that are available on the web. I believe this uniformity helps. Apparently my not using Powerpoint-type slides offend some people. Cannot help, sorry!

Pointers to the lecture notes follow:
[THESE NOTES ARE FOR HELPING YOU TO STUDY THE TEXT BOOK. I KEEP UPDATING THESE AND WILL NOT BE RESPONSIBLE IF YOU FIND THAT THE NOTE HAS CHANGED AFTER YOU HAVE PRINTED IT. I TRY TO CHANGE THE ASSOCIATED DATE WHEN I MAKE THE LAST UPDATE.]

The introduction is here. (8/28/08)

Notes on sorting. (9/2/08)

You may also like to read the following modules.
Notes on Recurrence equation. (9/10/02)
Notes on Recursive & Iterative algorithms. (9/27/05)

Notes on Algorithm types (9/25/08),
Some notes on Game search.

Graph algorithms (10/7/08).

On Union-Find (12/02/03).

Notes on String matching algorithms. (11/18/03)

Notes on Linear Programming algorithms. (11/16/06)

Notes on NP-hardness. (11/08)
The course page on Complexity Theory CSE 5610 offered by Drs. Bill Shoaff/ Phil Bernhard.

---------- Fall 2008 ---------
A dated course plan for Fall 2008.

Short Quiz (half hr, closed book) on Sorting Algorithms on 9/2/08.
Short Quiz (half hr, closed book) on Greedy Algorithms on 9/11/08.
Submit your answers as hard copy.
Home Work 1 and Programming Project 1 NOTE: Program Due Oct 7

Home Work 2

Self study Schedule

Programming Project 2

First Exam Questions
Home Work 3 (Due: Oct 28, Pts: 15): Redo Exam-1
Due Nov 4: Exchange with your partner as I assign, and collaboratively write brief comments on each one's each wrong answer (1-2 pages total for both).

DUE NOV 4: ANONYMOUS class feedback: separately on course content - what you would like to exclude, what else to include, etc; and on delivery mechanism, what was good, what I could do to make the course more effective. Print on one sheet total. THANKS.

Programming Project 3

Grades

---------- Fall 2007 ---------
A dated course plan for Fall 2007.

Submit your answers as hard copy.
Home Work 1/ Programming Project 1
Home Work 2/ Programming Project 2
Home Work 3/ Programming Project 3 (Q2 formula corrected)
Home Work 4 (CACM reading assignment)
Home Work 5/ Programming Project 4 NEW
First Exam Questions
Chapters presentation schedule for November'07
Second Exam Questions
Classes on the last week are not cancelled just because we have finished our exams!! We may have a quiz on 12/3/07 Tuesday on the SCC algorithm and the Articulation point algorithm.
Grades

---------- Fall 2006 ---------
Submit your answers as hard copy.
Home Work 0, due 9/3/06
Home Work 1/ Programming Project 1
Home Work 2/ Programming Project 2
Check the Euler ckt algorithm here
Quiz 1
Undergraduate presentations
Graduate class Mid Term, on October 19, Thursday
Graduate class Mid Term II, on November 2, Tuesday
Graduate students' self-study: Prepare for presenting at least three theorems/lemmas and their proofs (of your choice) from this paper, and submit your presentation to me on [Dec 5, Tuesday]
Graduate presentations:
Nov 28: Computational geometry: cross products, segmets-intersect, any-segments-intersect, Graham's scan (Theo, Alexander)
Nov 30: Number theoretic Algorithms (RSA): Chinese remainder theorem, RSA, correctness of RSA, anything else you want to talk on (Montri, Stephen, Nicolas)
Dec 5: Polynomial multiplication, DFT/FFT: polynomial mult, DFT, FFT (Jacek, Asim, Nathan)

Last Assignment, (except question 3 therein, this is Graduate Comprehensive Question for Fall 2006), due Dec 5.

Programming Project 3
Please provide me some feedback about the course in 1 page. Type it and submit it without your name/pointer on it, during the final. Divide the feedback into two groups: on the course content, and on the course delivery. Try to be objective and helpful to me for my future courses. Thanks!

Grad Final answer key
Grades

---------- Fall 2005 ---------
Submit your answers as hard copy. Home Work 0, due 8/30/05
Home Work 1, due 9/8/05
Home Work 2, due 9/20/05
Undergraduae Group Project, due 11/10/05
Graduate Class Project (individual), due 11/10/05
Home Work 3, due 9/29/05 [I NEED THE PAPERS BACK]
Mid Term on Thursday 10/06/05
Self-study on Quantum Computing
Home Work 4, due 11/03/05
Feedback: Thanks!
Final: Thursday 12/15/05 in the respective class rooms: UG: 3:30-5:30 pm, Grad: 6-8 pm. Excluded: Big-O definition, recurrence equation and Initialization-simplex algorithm. Exam is of the same format as before. You are allowed to bring any text book, class note, or your hand written notes from the class, and nothing else. You have to write answers on your own clean papers.
Grad final Grades

---------- Fall 2004 ---------
A quiz on basics.

The Home Work 1, due Tuesday Oct 5 in class.

Graduate Class project will be developed on this link. (11/2/04)

Undergraduate Class project will be developed on this link. (11/2/04)

Midterm exam on Tuesday October 26

Home Work 2 due Nov 11, 2004.

Quiz on November 30, 2004. (Closed book, possibly short questions format)
Syllabus: everything except string matching algorithms
I may take more quizes on any class in December.

Check the current grades here.
For the official cut-off on grades follow the syllabus. I reduce the cut-off from semester to semester in order to accommodate some borderline cases. The reused spreadsheet templates occasionally have older information hanging around through the semester but the issue of cut-off was also discussed in the class repeatedly.

---------- Fall 2003 ---------
Home Work 1. Due 9/9/03 in class, in hard copy.

Home Work 2. Due 10/07/03 in class, in hard copy. Print your name and status (Undergrad/Grad).

Test 1 key.

Home Work 3. Due 11/11/03 in class, in hard copy. Print your name and status (Undergrad/Grad).

Final.

Fall 2003:Grades up to mid term.

Graduate Class project will be developed on this link. (11/18/03)

Undergraduate Class project will be developed on this link. (11/18/03)
A comment on Fall 2003 final exam: except for proving Big-Oh notations and questions from the sorting-chapter, everything else is included.

---------- Fall 2002 ---------
Fall 2002:Key to the Short Test.

Sorry, nothing else is available for Fall02.