CSC 413/513 Fall 2007 Syllabus

Algorithms

By Prof. Jonathan Z. Sun

General Information

Coursework. Coursework will consist of weekly homework assignments, two midterm exams, and a comprehensive final exam. The course letter grade will be determined on a curve, combining numerical scores for homework (30%), midterm (20%+20%), and final (30%).

Attendance. Class attendance is strongly suggested. There might be in class exercises, discussions and quizzes that count for bonus points towards your final grade. Contents lectured in class will not be replayed to any individual student after the class.

Homework Submission. Homework will be due every Monday before class starts. Homework can be submitted in classroom, via email, or to Prof. Sun’s mailbox in the main office (TEC 214). No late submission will be granted.

Homework Return. Your graded homework will be returned on Wednesday in class. Homework returns that are unclaimed in class will be left at the front desk in the main office (TEC 214) for pick up.

Homework Grading. For both fairness and timeliness, your homework will be graded by Prof. Sun on a 3-point basis. Homework solutions will be demonstrated on Wednesday in class. Please check the correctness of your answers by yourself at the time.

3 points: correct or with minor errors.
2 points: make sense on some problems.
1 point: showed effort, but need help.
0 point: no submission or no serious try.

Text. Introduction to Algorithms, 2^nd edition, by Cormen, Leiserson, Rivest, and Stein. The MIT Press.

Time/Place. The course meets Mondays and Wednesdays, 3:30 - 4:45 in WSB 120. Prof. Sun is available for office hours Mondays and Wednesdays 12:30 - 2:00 and Tuesdays and Thursdays 10:00 - 11:00, in my office TEC 211.

Plagiarism. The university policy about academic honesty is in page 31-32 of the Student Handbook. A failure with dignity is much better than an abject success. Nevertheless, I seldom fail anyone who has tried his/her best.

The prerequisite and a brief course description of CSC413 and CSC513 are available in http://www.usm.edu/computing/cs/programs.php.

Tentative Schedule

Monday

Wednesday

Week 1 (08/22)

Introduction

- Computational Thinking

- Algorithms in the real world

Week 2 (08/27-29)

Getting started

- Insertion sort v.s. merge sort

- Algorithm design &. analysis

- Asymptotic notations

Recurrences

Homework 1

Week 3

(09/03-05)

Labor Day. No class.

Recurrences

Homework 2

Week 4

(09/10-12)

Probabilistic analysis and randomized algorithms

Homework 3

Week 5

(09/17-19)

Heaps and heap sort

Quick sort

Homework 4

Week 6

(09/24/26)

Sorting in linear time

Midterm I

Week 7

(10/01-03)

- Elementary data structures

- Hash tables

Homework 5

Football Day. Class rescheduled.

Week 8

(10/08-10)

Binary search trees

Homework 6

Red-black trees

Week 9

(10/15-17)

Red-black trees

Homework 7

Dynamic programming

Week 10

(10/22-24)

Dynamic programming

Homework 8

Greedy algorithms

Week 11

(10/29-10/31)

Greedy algorithms

Homework 9

Midterm II

Week 12

(11/05-07)

- Graph representation

- BFS, DFS

- topological sorting

Minimum spanning tree: Prim and Kruskal

Homework 10

Week 13

(11/12-14)

Single source shortest path: Bellman-Ford

Single source shortest path: Dijkstra

Homework 11

Week 14

(11/19-21)

Maximum flow: Ford-Fulkerson

Thanksgiving. No class.

Week 15

(11/26-28)

String matching

Advanced Topics*: amortized analysis

Week 16

(12/03-05)

Advanced Topics*: disjoint sets

Final Review

*: Contents are not covered in midterm and final exams.

Final Exam: Tuesday, Dec. 11, 5:00 pm - 7:30 pm.