CPSC 411 Design and Analysis of Algorithms

Textbook

Prerequisites

Grading

• Quizzes 9% - Almost every week, there will be a short (about 5-10 minutes) quiz on the current material. Your lowest quiz grade will be dropped.
• Homeworks 35% - Homework will consist of written problems and programming assignments.
• Exams 45% - One midterm exam (worth 20%) and one cumulative final exam will be given (worth 25%).
• Culture reports 5% - This component is to expose you to some of the research being done at TAMU and other places. Attend five seminars and write a short report about each, see below.
• Class partipication 5% - Active participation in class by all students will make it a better experience for all of us. Ask questions, make comments and suggestions, correct errors, find good URLs relating to algorithms for me to post, etc..
• ABET post test 1%

Exam Dates and Assignments

• The midterm exam is tentatively scheduled for Monday, March 2.
• The final exam is scheduled for Monday, May 11, 10:30am-12:30pm.
• All assignments will be announced in class. If you cannot turn in an assignment on time, discuss the situation in advance with the instructor.

Course Goals

• be familiar with fundamental algorithms and algorithmic techniques;
• given a particular application, be able to decide which algorithm among a set of possible choices is best;
• be able to prove correctness and analyze the running time and space complexity of a given algorithm;
• be able to design efficient algorithms for new situations using the techniques learned;
• be able to prove a problem is NP-complete using reduction and understand the implications;
• understand the notion of undecidability, know that some problems are undecidable and comprehend the implications.

Course Content and Tentative Schedule

week of	topic	chapter
8/26	introduction; sorting lower bound	Chs 1 and 3; Ch 8
9/2	divide and conquer algorithms	Chs 2 and 4; Ch 7
9/9	greedy algorithms	Ch 16
9/16, 9/23	dynamic programming	Ch 15
9/30	amortized analysis	Chs 17 and 21
10/7, 10/14	graph algorithms	Chs 23-25
10/21, 10/28	randomized algorithms	Chs 5 and 7
11/4, 11/11	NP-completeness	Chs 34 and 35
11/18, 11/25, 12/2	undecidability	other sources

Academic Integrity

• Definitions of academic misconduct, which includes plagiarism
• List of sanctions that can be applied if academic misconduct is found.

For the assignments in this class, discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. If you use any source other than the text, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever. You MUST write up the solutions in your own words. Copying is strictly forbidden.

Americans with Disabilities Act Policy Statement

Back to beginning

Culture Reports

There is a lot more to Computer Science than you will be exposed to through your normal coursework. The purpose of the culture activities is to give you an opportunity to learn about current research trends in computing. Keeping up with trends and learning to evaluate critically what you hear and read are valuable professional skills.

You are to attend five computer science seminars and write a report on each one. Acceptable seminars are listed below. More details and seminars will be added as they become available. If you are interested in receiving credit for a seminar that is not listed, check with the instructor in advance. Acceptable seminars include:

• Distinguished Lectures (You are especially encouraged to attend these.)
• Departmental Graduate Seminars (CPSC 681) (Mondays and/or Wednesdays at 4:10pm.)
• Parasol Seminars (usually held Fridays at 4pm in 302 HRBB)

Each report is to be one to two pages long, typed, and must include

• date and title of talk, name and affiliation of speaker;
• summary of the talk;
• at least one comment about the paper or question that it raised in your mind, indicating that you have thought critically about the material presented.

If, due to schedule conflicts, you cannot attend any research seminar for a particular culture report deadline, you may instead find, read and write a short report on a Turing award lecture. The appropriate lectures will be posted. The same requirements as for the seminar reports hold regarding content, length, format, plagiarism.

Tips for getting full points on your culture reports:

• TURN IT IN ON TIME.
• Ideally you should learn something from the seminar/article. If the seminar turns out to be too technical (or not well presented), just do the best you can, and feel free to point out what confused you or what you thought could have been done better.
• Don't be too skimpy on your summary.
• Clearly mark your own comments and critical evaluation. Say something at least mildly insightful. "I learned a lot/it made me think" is not enough. What did you like and why? Is there a flaw in the paper? How does it relate to something else you may be aware of? Etc.
• Include the required information about the seminar/paper in your summary.
• Use a spell-checker and grammar checker.

• Culture Report 1 due Mon, Feb 2
• Culture Report 2 due Mon, Feb 16
• Culture Report 3 due Mon, March 2
• Culture Report 4 due Fri, April 3
• Culture Report 5 due Mon, April 20