CS216--Data Structures--Fall 2010
Tues, Thurs, Period Q (2-3:15 PM)






The Textbook


Course Description


Course Objectives


Course Policies


Grading System


Course Schedule
        

Prof. Thomas A. Easton


Photo of Professor Easton
        
OFFICE: Rm. 108

OFFICE HOURS: 12-3 PM MW, 9:30-12 AM TTh

OFFICE PHONE: 859-1331

HOME PHONE: 338-1074

CANCELLATION PHONE NUMBER: 859-1140

Click here to email me:


THE TEXTBOOK

Algorithm Design,
Michael T. Goodrich and Roberto Tamassia
John Wiley & Sons, 2002 (0-471-38365-1)







This course provides an introduction to algorithm analysis, abstract data types, and data structures. Topics include lists, queues, priority queues, trees, and graphs. The impact of these structures on algorithm design is explored. External memory management is discussed.

See "Course policies" below for details on testing and grading.







Upon completion of this course, students will:
  1. Understand how to analyze algorithms.
  2. Be able to apply the following basic data structures (among others) to solve problems:
    1. Stacks
    2. Queues
    3. Lists
    4. Trees
  3. Understand how merge, quick, bucket, and radix sorts work.
  4. Be able to apply the greedy method, divide-and-conquer, and dynamic programming to algorithm design.
  5. Understand the nature and uses of graph structures.
Assessment will be by means of quizzes and exams, as specified below.






Students should always read their assignments and come to class prepared to discuss and/or work on the material. Each student may be absent twice without penalty. Each additional two absences without a medical excuse (no others are acceptable) will cost the student three points on the course grade.

Grades will be based upon 3 quizzes (worth 10% each) and 2 exams (worth 20% each) and a final (worth 30%).

See the Course Schedule for details.



Students who plagiarize tests and projects will receive zeros for the work in question, with no makeup opportunities.





GRADING SYSTEM

A (94 - 100)      A- (90 - 93)
B+ (87 - 89)     B (83 - 86)    B- (80 - 82)
C+ (77 - 79)     C (73 - 76)     C- (70 - 72)
D+ (67 - 69)     D (63 - 66)    D- (60 - 62)
F (below 60)





COURSE SCHEDULE

CAUTION: COURSE SCHEDULE SUBJECT TO CHANGE WITHOUT WARNING!


DATETOPICASSIGNMENT
  
Tues Aug 31 MethodologiesRead Ch. 1.1
 
Thurs Sept 2 Asymptotic Notation Read Ch. 1.2
 Homework due Sept 7: R-1.2, 1.3, 1.7, 1.10, 1.11, 1.12, 1.27
 
Tues Sept 7 Math Review Read Ch. 1.3
 
Thurs Sept 9 Two Prefix Averages Algorithms Read Ch. 1.4
 
Tues Sept 14 Amortization and ExperimentationRead Ch. 1.5, 1.6
 
Thurs Thurs 16 Review and Quiz #1
 
Tues Sept 21 Stacks & Queues; Vectors Read Ch. 2.1, 2.2.1
 
Thurs Sept 23 Lists & Sequences Read Ch. 2.2.2, 2.2.3
 Homework due Oct 7: R-2.1, 2.2, 2.5, 2.8, 2.10, 2.11, 2-19
 
Tues Sept 28 Trees Read Ch. 2.3
 
Thurs Sept 30 Priority Queues & Heaps Read Ch. 2.4
 
Tues Oct 5 Dictionaries & Hash Tables Read Ch. 2.5
 
Thurs Oct 7 Review for Exam
 
Tues Oct 12 COLUMBUS DAY -- NO CLASS
 
Thurs Oct 14 Exam #1
 
Tues Oct 19 Ordered Dictionaries & Binary Search Trees Read Ch. 3.1
 
Thurs Oct 21 AVL & Bounded-Depth Trees Read Ch. 3.2, 3.3
 Homework due Oct 28: R-3.1, 3.2, 3.3, 3.5, 3.7, 3.11, 3.15
 
Tues Oct 26 Splay Trees & Skip Lists Read Ch. 3.4, 3.5
 
Thurs Oct 28 Review and Quiz #2  
  Drop Date:  After Nov 3 you cannot drop the course without getting a grade. 
No W or L!
    
Tues Nov 2 Merge-Sort & The Set ADT Read Ch. 4.1, 4.2
 Homework due Nov 11: R-4.1, 4.2, 4.5, 4.9, 4.11, 4.17
 
Thurs Nov 4 Quick-Sort & Lower Bounds Read Ch. 4.3, 4.4
 
Tues Nov 9 Buckets, Radices, & Selection Read Ch. 4.5, 4.6, 4.7
 
Thurs Nov 11 Review for Exam
 
Tues Nov 16 Exam #2
 
Thurs Nov 18 The Greedy Method Read Ch. 5.1
 
Tues Nov 23 Divide and Conquer Read Ch. 5.2
 Homework due Dec 2: R-5.1, 5.3, 5.5, 5.7
    
Wed Nov 24 -- Fri Nov 26 Thanksgiving Vacation
    
Tues Nov 30 Dynamic Programming Read Ch. 5.3
 
Thurs Dec 2 Review & Quiz #3
 
Tues Dec 7 Graphs Read Ch. 6.1, 6.2
 Homework due Dec 9: R-6.1, 6.2, 6.3
 
Thurs Dec 9 Graph Traversal Read Ch. 6.3
 
Mon Dec 13 FINAL EXAMS BEGIN
 
EXAM DAY FINAL EXAM
 






Syllabus last modified April 29, 2010.
ADMISSIONS  |  ABOUT US  |  ACADEMICS  |  STUDENT LIFE  |  ATHLETICS  |  ALUMNI  |  HOME  |  SITE MAP  |  CONTACT US  |