Last updated on 12/4/2003 1:41:12 PM

Dmitri Kaznachey, Ph.D.
Director, Finance
Risk Management Platform, Architecture
Portfolio Analytics
Fannie Mae, Washington, DC
e-mail: dmitri_kaznachey@fanniemae.com; dkaznachey@yahoo.com
(202) 752-3344 work; (703) 278-2849 home

CS 483 Data Structures and Analysis of Algorithms
Fall 2003
002 Wednesday 4:30 p.m. – 7:10 p.m. Lecture Hall, Room 3
Office hours: by appointment (SITE II, Room 435)

Schedule | HW #1 | HW #2 | HW #3 | HW #4

Text Book

Introduction to Algorithms, Second Edition by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, MIT Press, 2001.

Course Description

This course covers concepts associated with design and analysis of algorithms. Algorithms capture fundamental ideas of computational systems and often determine the quality and efficiency of software. Designing efficient algorithms in many cases depends on choosing proper data structures; hence the attention will be paid to both concepts. The main topics include: complexity analysis, important data structures, sorting, dynamic programming and greedy algorithms.

Prerequisites

• CS310: The introductory sequence CS I, II, III is essential as this course will extend, generalize, and abstract ideas from the earlier courses.
• CS330: This course and its prerequisite, MATH125, provide experience with rigorous proof methods underlying the verification and analysis techniques used throughout CS483.
• MATH114: Solid knowledge of series, limits, and functions behavior will be required frequently.

Grading

4 home works (3 best scores):	30%
Midterm exam:	30%
Final exam:	30%
Class participation:	10%

Bonus points worth 10% credit will be awarded for doing some extra work on assignments. Answering challenging questions during the class will result in bonus points (up to 3) for class participation. The maximum possible total score to receive in class is 110.

No make-ups will be offered for exams and home works. Once the grade for homework or a midterm exam is announced, a one-week grace period is allowed to discuss the grade with the instructor. No grade adjustments will be made after the grace period.

Teaching Assistant

Brendan Drew

e-mail: bdrew@cs.gmu.edu

class page: http://cs.gmu.edu/~bdrew/cs483

Office hours:

Monday: 4-7 pm

Wednesday: 7:30-9 pm

Schedule

August 27	Ch.1, 2: Introduction, Insertion sort, Analyzing algorithms
September 3	Ch.2, 3: Merge sort, Asymptotic notation HW1 assigned
September 10	Ch.4: Recurrence and Master theorem HW1 due
September 17	Ch.6: Heapsort
September 24	Ch 7: Quicksort HW2 assigned
October 1	Ch. 7: Quicksort HW2 due
October 8	MIDTERM EXAM
October 15	Ch. 8: Sorting in linear time
October 22	Ch.10: Basic data structures, Midterm exam analysis
October 29	Ch. 10, 11: Basic data structures, Hash tables HW3 assigned
November 5	Ch.11, 12: Hash tables, Binary search trees HW3 due
November 12	Ch. 12, 13: Binary search trees, Red-black trees
November 19	Ch. 15: Dynamic programming HW4 assigned
November 26	NO CLASS - THANKSGIVING
December 3	Ch. 16: Greedy algorithms HW4 due
December 10	Final Exam 4:30 - 7:15