Date: Wed, 20 Nov 1996 23:18:35 GMT Server: NCSA/1.5 Content-type: text/html 22C:21 Home Page

22C:21 Algorithms and Data Structures --- Spring 1996

MWF 1:30, Jessup Hall 221

PROFESSOR: Jim Cremer, 201N MacLean, E-mail: cremer@cs.uiowa.edu, Office hours: 2:30-3:30 T, 10:30-11:30 F, or by appointment

TA: Jun Tu, 255D McBride, jun@cs.uiowa.edu, Office Hours: 3:30-4:30 W, 1:30-2:30 Th


WHAT'S NEW (Last updated Monday, 5/13/96)



Prerequisites

22C:17, 22C:18, and 22C:19 (or permission of instructor)

Course goals, content, and schedule

The aim of the course is to gain experience with the major paradigms and data structures used in creating algorithms, and with basic methods for analyzing the time and space requirements of programs. We will cover most of the textbook. The tentative schedule is:

  Week 1              Intro and Ch 1 (math background, induction, recursion)
  Week 2              Ch 2 (algorithm analysis notation and techniques), a bit of 7.6 and 10.2
  Week 3              quick review of Ch3, Ch 4 (trees)
  Week 4              Ch 5 (hashing)
  Weeks 4 and 5       Ch 6 (priority queues)
  Week 6              Ch 7 (sorting)
  Week 7 (February 28)     Exam 1,in class
  Weeks 7 and 8       Ch 8 (disjoint sets)
  Weeks 8 and 9       Ch 9 (graphs)
  Week 10             SPRING BREAK
  Week 11             Ch 9 (graphs), including a bit extra on decidability, tractability, complexity
  Weeks 12 and 13     Ch 10 (algorithm techniques), including greedy methods, dynamic
                          programming, more divide-and-conquer
  Week 14 (April 17)  Exam 2, in class
  Week 15             Ch 10.5 backtracking search/games (TENTATIVE)
  Week 16             Ch 11 (amortized analysis)
  May 10 (Friday)     FINAL EXAM, 9:45 a.m.          

Textbook

Weiss, Data Structures and Algorithm Analysis, Benjamin-Cummings, Second Edition, 1995.

Supplemental Books (on reserve in Math Library)

Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw-Hill, 1990
Aho, Hopcroft, and Ullman, Data Structures and Algorithms, Addison-Wesley, 1983


Requirements and grading

Course grades will be based on ten (or so) homework sets, two midterm exams, and the final exam. There will be some small programming assignments. Programming problems will usually be given as part of regular written homework assignments; there will not be a separate grading category for programming assignments. Class participation and effort may be taken into account in determining grades in borderline situations. The components will be weighted roughly as follows:

		Homeworks assignments         35%
		Midterm exams                 20% each
		Final exam                    25%


Late assignment policy

All assignments are due at the beginning of class. In other cases, assignments turned in within 24 hours will receive a 20% penalty, and those turned in 24 to 48 hours late will receive a 50% penalty. (Exception --- each student may turn in one homework assignment up to two days late with no penalty.) Regrade requests must be made within one week of when the assignments are returned in class.


Policy on collaboration

Homework and programming assignments should be done alone. It is reasonable to discuss general approaches to problem solution or algorithm design with other students but the bulk of the work must be done alone. Working out details, sharing in the write-up or sharing or copying code will be treated as a violation of the academic integrity rules.


Note on Language for Progamming Assignments

Program source code in the book is in Pascal. However, for course programming assignments, you will be free to use your choice of Pascal, C, or C++ (or another language if approved by the instructor).


Homework Assignments


Scores and grades


Homework Solutions, useful code, and miscellaneous stuff