CS 470 Fall 2004 -- Syllabus

Syllabus

Course:

CS 470 Introduction to Computer Algorithms, Fall 2004

Where and when:

Lecture: EE 110, Mon/Wed/Fri 10:00AM-10:50AM; first class meets on Wednesday 8/25/04 at 10:00AM !!!
Labs: Houser 120, EE 116, MIB room 333, Hardaway 255

Instructor:

Grzegorz Malewicz
116 Houser Hall
Phone: (205) 348-4038
Email: greg@cs.ua.edu

Required text:

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms (2nd Edition). MIT Press (2001) book web page

Additional reading (not required):

Knuth, D.E.: The Art of Computer Programming, Volumes 1,2 and 3. Addison-Wesley book web page

Office hours:

Fridays 11:00AM-1:00PM; also by appointment or just come to my office

Course web page:

http://www.cs.ua.edu/470/fall2004/

Prerequisite:

CS 325, CS 357, ECE 383, and MATH 301

Course description:

How to design an algorithm that solves a computational problem? What techniques can help you discover an efficient solution? The Introduction to Computer Algorithms course will present a range of techniques that algorithm designers can use when trying to develop an efficient algorithm for a computational problem. The techniques will be exemplified on many common computational problems. You will improve your understanding of course material by solving theoretical problems and implementing algorithms on a computer. The course will be fairly rigorous (i.e., theorems will be proven).

Course objectives:
At the end of the course, a student who successfully completes the course will

* know several existing algorithms and be able to analyze their efficiency,

* be able to design an algorithm to solve a moderately difficult computational problem and analyze the efficiency of the algorithm,

* improve analytical skills and ability to think rigorously,

* improve programming skills.

Official university catalog description

Construction of efficient algorithms for computer implementation.

Outline of topics covered during the semester and planned number and timing of major examinations and assignments (these may change):

8/25 - 9/29 Foundations (book chapters 1,2,3 and 4), and Sorting (book chapters 6,7 and 8)

10/1 First midterm

10/4-10/29 Order Statistics (book chapter 9) and Dynamic Programming (book chapter 15)

11/1 Second midterm

11/3-12/10 Graph Algorithms and Greediness (book chapters 22,23,24 and 25); NP-Completeness and Approximation Algorithms (book chapters 34 and 35)

12/13-12/17 Final on one day during the examination session

You can expect one set of problems per week with a one week deadline. You are responsible for reading the parts of the text assigned by the instructor.

Attendance policy:

It is expected that you attend each lecture. Any missed lecture may reduce your grade by 0.1% (1/10 of a percent).

Grading policy:

30% two midterms (each worth 15%)

20% final

24% several practical programming projects (usually assigned once a week)

24% several theoretical exercises (usually assigned once a week)

1% for talking to me during office hours, or other appointment, on or before the first midterm (grade disputes do not count)

1% for coming up with a course related problem/question and talking to me about it during office hours, or other appointment, after the first midterm (grade disputes do not count)

-4% up to minus 4% for skipping lectures

The policy for making up missed course work and examinations:

If you miss any homework deadline for any excused reason, then you can request to be assigned an extra task to perform. The task will be of equal value, weight and difficulty. If you miss any midterm or exam for any excused reason, then you can take an extra comprehensive make–up exam administered at the end of the semester. The exam will be of equal value, weight and difficulty.

Remarks:

* you can bring a letter-size page of your own hand-written notes, written on any of the two sides of the page, to each midterm, and three such pages to the final; no other material will be permitted,

* each programming project should be written in C++, using Visual Studio .Net,

* homeworks should be submitted electronically to cs470@cs.ua.edu, questions about homeworks and questions requiring immediate attention should be sent to the instructor greg@cs.ua.edu (the email former email address will be checked infrequently)

* any work that you submit must be written entirely by you; you can discuss solutions with other students, however, you cannot copy solutions to exercises or any code from other students; you cannot plagiarize from the Internet; if you do not comply, you will be severely penalized,

* when work is submitted x hours after midnight of the day it is due, and x<=50, the work will be penalized 2% times the ceiling of x; work submitted 50 hours, or more, after the deadline will not receive any points,

* do homework diligently and meticulously as you can expect similar problems on midterms and the final,

* if you decide to dispute your grade, do it via email ONLY (do not dispute any grade verbally in my office); write a convincing argument explaining why you believe your grade should be different; this email will be your only chance to dispute a given grade,

* you must obey the University's honor code,

* to request disability accommodation, please contact the Office of Disability Services (348-4285); after initial arrangements have been made with that office, please contact me.

	*	know several existing algorithms and be able to analyze their efficiency,
	*	be able to design an algorithm to solve a moderately difficult computational problem and analyze the efficiency of the algorithm,
	*	improve analytical skills and ability to think rigorously,
	*	improve programming skills.

	8/25 - 9/29	Foundations (book chapters 1,2,3 and 4), and Sorting (book chapters 6,7 and 8)
	10/1	First midterm
	10/4-10/29	Order Statistics (book chapter 9) and Dynamic Programming (book chapter 15)
	11/1	Second midterm
	11/3-12/10	Graph Algorithms and Greediness (book chapters 22,23,24 and 25); NP-Completeness and Approximation Algorithms (book chapters 34 and 35)
	12/13-12/17	Final on one day during the examination session

	30%	two midterms (each worth 15%)
	20%	final
	24%	several practical programming projects (usually assigned once a week)
	24%	several theoretical exercises (usually assigned once a week)
	1%	for talking to me during office hours, or other appointment, on or before the first midterm (grade disputes do not count)
	1%	for coming up with a course related problem/question and talking to me about it during office hours, or other appointment, after the first midterm (grade disputes do not count)
	-4%	up to minus 4% for skipping lectures

	*	you can bring a letter-size page of your own hand-written notes, written on any of the two sides of the page, to each midterm, and three such pages to the final; no other material will be permitted,
	*	each programming project should be written in C++, using Visual Studio .Net,
	*	homeworks should be submitted electronically to cs470@cs.ua.edu, questions about homeworks and questions requiring immediate attention should be sent to the instructor greg@cs.ua.edu (the email former email address will be checked infrequently)
	*	any work that you submit must be written entirely by you; you can discuss solutions with other students, however, you cannot copy solutions to exercises or any code from other students; you cannot plagiarize from the Internet; if you do not comply, you will be severely penalized,
	*	when work is submitted x hours after midnight of the day it is due, and x<=50, the work will be penalized 2% times the ceiling of x; work submitted 50 hours, or more, after the deadline will not receive any points,
	*	do homework diligently and meticulously as you can expect similar problems on midterms and the final,
	*	if you decide to dispute your grade, do it via email ONLY (do not dispute any grade verbally in my office); write a convincing argument explaining why you believe your grade should be different; this email will be your only chance to dispute a given grade,
	*	you must obey the University's honor code,
	*	to request disability accommodation, please contact the Office of Disability Services (348-4285); after initial arrangements have been made with that office, please contact me.