CPSC 465: Design and Analysis of Algorithms

Spring, 12 week, 2009

Slotterbeck

http://cs.hiram.edu/~obie/cs465

Text: Goodrich, Michael T. and Roberto Tamassia, "Algorithm Design: Foundations, Analysis, and Internet Examples",

Wiley, 2002

In the future, changes will be marked with

SOME RESOURCES ON THE WEB:

Resources provided by the authors

Includes many resources such as the authors' slides, animations, hint servers for some problems, and errata.

CLASS SLIDES:

MISCELLANEOUS CLASS MATERIALS:

Posted	URL	Comments
Sun, 1/11	Chapter0.ppt Introduction.ppt Chapter1.ppt	Syllabus Introduction Algorithm Analysis
Tues, 1/13	Chapter2.ppt	Basic Data Structures -Mostly a review of cpsc 201
Tues, 1/20	Chapter5.ppt	Fundamental Techniques
Tues, 2/3	Chapter6.ppt	Graph Algorithms
Sun, 2/22	Chapter7.ppt	Weighted Graphs
Wed, 3/18	Chapter9.ppt	Text Processing
Fri, 3/20	Chapter13.ppt	P and NP
Wed, 3/25	Chapter10.ppt	Number Theory and Cryptography
Sun, 3/29	Chapter14.ppt	Algorithmic Frameworks
Mon, 4/6	Chapter 12	Convex Hull only

READING ASSIGNMENTS: (In textbooks unless noted otherwise)

Posted	Assigment	Comments
Sun, 1/11	Preface, Chapter 1	Chapter 1 introduces a lot of mathematical concepts. We will cover it rather quickly as we will encounter these ideas throughout the course.
Tues, 1/13	Chapter 2	Mostly a review of cpsc 201
Tues, 1/20	Chapter 5	We're skipping Chapter 3 and 4 for now although we'll dip back into them in the future as needed.
Tues, 2/3	Chapter 6
Sun, 2/22	Chapter 7
Sun, 3/15	Chapter 9	We're skipping Chapter 8
Thurs, 3/19	Chapter 13
Tues, 3/24	Chapter 10
Sun, 3/27	Chapter 14	(starting with 14.2, Parallel Algorithms)

HOMEWORK ASSIGNMENTS: Each week's assignment is due on Friday. Not all assignments will be made at the same time for the week so be sure to check this listing often. All assignments will be posted by Wednesday evening for the week. See the first set of slides for policies on collaboration, format, etc.

FAQ:

Answers to questions about HW

Posted HW solutions

Assigned	Due	Exercises	Comments
Mon,1/12	Fri.1/16	Prove the results on Introduction slides, slides 40 ,65, and 69 and justify the 5n (at least) claim on slide 12 of Chapter 1 slides. Is the other calculation correct?	(i.e. explain why each step follows from the previous ones) .Clearly identify what you can assume and what you have to prove.
Wed, 1/14	Fri, 1/16	Chapter 1: pg 47+, R: 2,6,7,9	(i.e. R2, R6, R7, and R9)
Fri, 1/16	Fri, 1/23	Chapter 1: pg 47+, C: 7,8,17,21,25	Note:These require more thought than R exercises!
Tues, 1/20	Fri, 1/30	Chapter 1: pg 47+, C:27 Chapter 2: pg 131+ ,R: 2,3,10
Thurs, 1/22	Fri,1/30	Chapter2: pg 131+, R: 14 C: 2,10, 29
Mon, 1/26	Fri, 1/30	Chapter 5: pg 282+, R:1,3,4,12	Move R5.4 to 2/6 because college was closed Wed due to the storm.
Wed, 1/28	Fri, 2/6	Chapter 5: pg 282+, C: 1,3,4,5   R4
Tues, 2/3	Fri, 2/6	Chapter 5:pg282+, C6,9	C5.9 was done in class, but be sure you understand the technique used.
Mon, 2/16	Fri, 2/27	Chapter 6: pg.335+, R: 1-14	Note: More time was given for this assignment as it is longer than most
Wed, 3/25	Wed, 4/1	Chapter 9: pg 447+, R:1-5, 7,11; C-1-5
Sun, 4/5	Fri, 4/10	Chapter 10: pg 508+, R:9, 12, 13, 21 and Chapter 13 Pg 638+ R-1,7,12	Last assignment

ANNOUNCEMENTS OF TESTS:

Midterm - take home

Disributed Mon, 3/16

Due (in hard copy) Mon, 3/23 at class time

Get test here (at end of class time on Monday)

DON'T PROCRASTINATE- SEEK HELP IF YOU NEED IT!