Syllabus for
Computer Science / Computer Engineering 3313

Algorithms
The University of Arkansas
Spring 2001


Instructor: Gordon Beavers
email: beavers@engr.uark.edu
website: http://csce.uark.edu/ beavers/
Office: Engineering Hall 318
Phone: 575-6040
Office Hours: TR 1:00 - 3:00
Grader: Robert Tennyson
email: rtennys@uark.edu
website: http://comp.uark.edu/ rtennys/
Class Time: MWF 12:30 - 1:20
Class Room: Bell 273
Textbook: Introduction to Algorithms, MIT Press 1990
Authors: Cormen, Leiserson, Rivest

Catalog Course Description:

CENG 3313 (FA,SP) (Formerly CSCI 2023 or CSEG 4553) Provides an introductuion to formal techniques for analyzing the complexity of algorithms. The course surveys important classes of algorithms used in computer science and engineering. (Same as CSCE 3313). Prerequisite: CENG 2143 and MATH 2103 and (MATH 2564 or MATH 3103).

Course Objectives: This course introduces the student to a broad range of commonly used computer algorithms and evaluates the efficiency of those algorithms.

Evaluation:

Problem Sets 50% Approximately one each week
Mid-term Exam 20% Friday 9 March
Final Exam 30% Thursday 10 May, 12:30 - 2:30

We shall attempt to cover the following material during this semester.

Introduction (Chapter 1)
Growth of Functions (Chapter 2)
Summations (Chapter 3)
Recurrences (Chapter 4)
Sets, Etc. (Chapter 5)
Heapsort (Chapter 7)
Quicksort (Chapter 8)
Sorting in Linear Time (Chapter 9)
Hash Tables (Chapter 12)
Binary Search Trees (Chapter 13)
Red-Black Trees (Chapter 14)
Augmenting Data Structures (Chapter 15)
Midterm Examination
Dynamic Programming (Chapter 16)
Greedy Algorithms (Chapter 17)
Elementary Graph Algorithms (Chapter 23)
Minimum Spanning Trees (Chapter 24)
Single-Source Shortest Paths (Chapter 25)
All-Pairs Shortest Paths (Chapter 26)
Maximum Flow (Chapter 27)
Computational Geometry (Chapter 35)

Suggestions: Since we have an ambitious schedule and the class is large, you will have to assume considerable responsibility for the mastery of this material. Complete understanding will normally come only with considerable study. Students should expect to spend three hours of individual study for each hour of lecture. Please look over the material before class so that you may ask relevant questions. Should you find that you still have questions after class, or you find that there is a problem you cannot solve on your own, please write the question down and submit it during a following class.

Your grades on the problems sets and the examinations will be based not only on the correctness of your solution, but also on the clarity and precision of your presentation. Discussion of the problems is encouraged, however, problem sets must be completed independently. Please give credit to individuals or other sources from which you have obtained assistance. Class participation will be taken into account in determining grades for borderline cases.

Drill Session There will be an optional drill session conducted each Wednesday afternoon from 4:00 to 5:00 p.m. in ENGR 307. These sessions will provide an extra opportunity for students to get help on assignments from the instructor.

Class Attendance: You are responsible for all material covered in class. If you must miss a class, it is your responsibility to get the notes, handouts, assignments, etc. from someone else in class.

Grade Posting Disclaimer: Final grades in this course will be posted by the last four digits of the student's social security number. If you do not want your final grade posted, please submit a written request.

Academic Honesty: The policy specified in the University of Arkansas Undergraduate Studies Catalog, Academic Regulations, Academic Dishonesty will be followed.

ADA Statement: If any member of the class has a documented disability and needs special accommodations, the instructor will work with the student to provide reasonable accommodation to ensure the student a fair opportunity to perform in this class. Please advise the instructor of the disability and the desired accommodations within the first week of the semester.

Inclement Weather: If the university is officially closed, class will not be held. You will be expected to make every effort to attend class, but not if you don't feel that you can get to campus safely. Assignment due dates will be postponed in case of inclement weather.


Gordon Beavers 2001-02-07