King Fahd University of Petroleum and Minerals

Department of Information and Computer Science

ICS 353-01: Design and Analysis of Algorithms – Summer 2003 (023)

Location: (24) 141

Meeting Times: 09:20-10:20pm, SUMTW

======

Instructor: Dr. Wasfi Al-Khatib (office: (22) 133-1, phone: x1715).

e-mail:

URL:

Office hours:SMW 10:30 – 11:30 a.m.UT 12:00 - 01:00 p.m.

Textbook: Introduction to Algorithms: Design Techniques and analysis, M. Alsuwaiyel.

Prerequisite:ICS 202: Data Structures

Prerequisites by Topic:

  1. Data structures including linked lists, arrays, stacks, queues, trees, and graphs, and
  2. Knowledge of a high level structured language.

Course Goals:

To provide the students with the following:

1)The fundamentals of algorithms and algorithmic techniques,

2)The ability to decide on the suitability of a specific technique for a given problem,

3)The ability to analyze the complexity of a given algorithm,

4)The ability to design efficient algorithms for new situations, using as building blocks the techniques learned, and

5)Introducing the concept of NP-complete problems.

Current Catalog Description:

Introduction to algorithms and review of data structure; Time and space analysis; Algorithm design techniques: divide-and-conquer, greedy algorithms, dynamic programming, search techniques; NP-complete problems and approximation algorithms.

Course Contents (tentative):

1)Basic Concepts in Algorithmic Analysis, Chapter1

2)Mathematical preliminaries, Chapter 2

3)Review of Data Structures, Chapter 3

4)Advanced Data Structures, Chapter 4

5)Induction, Chapter 5

6)Divide and Conquer, Chapter 6

7)Dynamic Programming, Chapter 7

8)Greedy Algorithms, Chapter 8

9)Graph Traversal, Chapter 9

10) NP- Complete Problems, Chapter 10

Grading Policy:

Quizes / 15%
Pop Quizes / 15%
Two Major Exams / 30%
Project / 10%
Final Exam / 30%
Absences / -6%

IMPORTANT DATES:

Task / Date [and Time] / Location / Weight
Quiz 1 / Tuesday July 8, 2003at end of class / In class / 3%
Class / Thursday July 10, 2003 / In class / -?%
Quiz 2 / MondayJuly 14, 2003 at end of class / In class / 3%
Review Session / Sunday July 20, 20038:30-10:00pm / In class / N/A
Major Exam I / Monday July 21, 20035:00-6:30pm / In class / 15%
Quiz 3 / Monday July 28, 2003 at end of class / In class / 3%
Quiz 4 / MondayAugust 4, 2003 at end of class / In class / 3%
Review Session / Sunday August 10, 20038:30-10:00pm / In class / N/A
Major Exam II / Monday August11, 20035:00-6:30pm / In class / 15%
Quiz 5 / Monday August 18, 2003 at end of class / In class / 3%
Review Session / Thursday August 21, 20038:00-10:00pm / In class / N/A
Final Exam / TBA / TBA / 30%

IMPORTANT NOTES:

  • KFUPM regulations and standards will be enforced.
  • Attendance will be checked each class.
  • Unexcused Absences Policies:
  • The first THREE absences are FREE of charge.
  • The forth absence is worth -3 of your maximum 100 total.
  • Each subsequent absence, up to the ninth absence, is worth -0.5 of your maximum 100 total.
  • The tenth absence will result in an automatic DN grade.
  • An unexcused absence can become an excused absence ONLY by an official letter from the Dean of Student’s office.
  • Students are expected to be courteous toward the instructor and their classmates throughout the duration of this course.
  • All cell phones and pagers must be turned off during class and exams.
  • Quizzes: 10-15 minute. Each covers material given since the last quiz or major exam.
  • PopQuizzes: 10 minute.Each covers material given during the same lecture.
  • ZERO-TOLERANCEfor CHEATING.
  • Homeworks are optional, BUT CRUCIAL for learning and for obtaining good grades.
  • One has 24 hours to object to the grade of a [pop] quiz or a major from the end of the class time in which the graded exam papers have been distributed. If for some reason you cannot contact me within this period, send me an email requesting an appointment. The email should be sent within the 24-hour time period.
  • Exams and quizes are generallyCHALLENGING.