CS344 ALGORITHMS AND DATA STRUCTURES
SPRING 2009

Lecturer: James F. Lynch
Office: SC-381
Office hours:  TuTh 10:00AM–11:00AM, 12:15PM–1:00PM, 2:15PM–3:00PM
Telephone: 268-2374
email: jlynch@clarkson.edu
Lecture hours:  TuTh 1:00PM–2:15PM, SC–346
Text: A Practical Introduction to Data Structures and Algorithm Analysis, 2nd edition
          by Clifford A. Shaffer
          Prentice-Hall, ISBN 0-13-028446-7
          Book Homepage
Relevant Algorithm Animations/Visualizations


OBJECTIVES

The course will teach students how to use the fundamental data structures of computer science in a wide variety of applications. It will also cover methods for analyzing the advantages and disadvantages of different algorithms so that students can decide which algorithm to choose for a particular application.


ASSESSMENT

Grading will be based on homework assignments and exams. Homework assignments will consist of programming projects and written assignments that will serve as preparation for the exams.  Exams will be in-class, closed book.  Missing an exam will result in a grade of 0 for the exam, unless it was caused by circumstances beyond your control, and you have notified me beforehand, if at all possible.  For example, if you have an officially sanctioned Clarkson activity such as an athletic event that conflicts with an exam, you must discuss this with me before the event, so that we can make other arrangements.  If you are going to miss an exam due to illness, you should contact me before the exam if possible, and I will require certification from the Clarkson dean of student life that you were ill.  The following are not acceptable excuses for missing an exam:  job trips, sleeping through an exam, forgetting an exam, extending a break, and other possibilities too obvious to mention.

Programming projects

24%

Three hourly exams:

51%

Final exam:

25%

Hourly exam dates:

Thursday, February 5

 

Thursday, March 5

 

Thursday, April 9

Final exam date:

 



PROGRAMMING PROJECTS

Program 1: Set ADT implementation 

Program 2:

Program 3: 

Program 4:



SYLLABUS


Week of


Topics


Text


Exercises


January       6

Introduction

Ch. 1

1.3



                 13

Mathematical foundations

Ch. 2

2.2, 2.6, 2.10, 2.17, 2.22, 2.23, 2.27


                
20

Algorithm analysis

Ch. 3

3.3, 3.4, 3.9, 3.10, 3.12



                 27

Lists, stacks, and queues

Ch. 4

4.4, 4.5, 4.6, 4.8, 4.9



February     3

Lists, stacks, and queues

Ch. 4

4.14, 4.19, 4.20


                 10

Binary trees

Ch. 5

5.3, 5.6, 5.9, 5.12, 5.13, 5.18, 5.21


                 17

Binary trees

Ch. 5

 


                 24

Searching

Ch. 9

9.3, 9.9, 9.13, 9.14, 9.16


March         3

Searching

Ch. 9

 


                 10

Internal sorting

Ch. 7

 


                 17


SPRING

 


BREAK


                 24

Internal Sorting

Ch. 7

7.4, 7.9, 7.12, 7.15, 7.16, 7.17, 7.19


                 31

General Trees

Ch. 6

6.1, 6.4, 6.5, 6.7, 6.9, 6.12


April           7

Graphs

Ch. 11

11.1, 11.4, 11.5


                 14

Graphs

Ch. 11

11.8, 11.9, 11.15


                 21

Review