CMPS 102

Introduction to Analysis of Algorithms

Fall 2002   

 

Description:  Methods for the systematic construction and mathematical analysis of algorithms. Order notation, the RAM model of computation, lower bounds, and recurrence relations are covered. The algorithm design techniques include divide-and-conquer, branch and bound, and dynamic programming. Applications to combinatorial, graph, string, and geometric algorithms.

Prerequisite:  CMPS 101

 

Time and Place:  Tu Th   10:00 – 11:45 am    Kresge 327  

Class Webpage: http://www.soe.ucsc.edu/classes/cmps102/Fall02/

Class News Group: ucsc.class.cmps102

 

Instructor:  Ram Charan

Email:  rcharan@soe.ucsc.edu

Office:  Baskin Engineering  189A

Office Hours:  TTh   12:30-2:15 PM

Phone:  831-459-1653

 

Teaching Assistant: Svetlana Kagan (lighty@soe.ucsc.edu)

Discussion Sections: Places and times will be posted on the webpage shortly.  These secondary meetings will be used by TA to discuss homework problems and to help students prepare for exams. 

 

Required Text:  

Introduction to Algorithms by Cormen, Leiserson, Rivest, & Stein; 2^nd edition, published by McGraw Hill (2001).

 

Optional Texts: 

Fundamentals of Algorithmics by Brassard and Bratley, published by Prentice Hall (1996).

Computer Algorithms by Baase and van Gelder, 3^rd edition, published by Addison Wesley (2000).

 

Syllabus and Readings:  I plan to cover the following topics: 

• Asymptotic Growth of Functions

• Induction Proofs

• Recurrences

• Divide and Conquer

• Dynamic Programming

• Greedy Methods

• Lower Bounds

• Backtracking

• Branch and Bound

  

Coursework and Evaluation:

Homework due dates will be announced in class and on the web page.  No late papers will be accepted. 

Midterm Exam will be held in class on  Thursday, October 24th, 2002

Final Exam will be held on  Wednesday December 4, 2002     8:00 to 11:00 am

 

Course work will be weighted as follows:

 

Homework                                        25%

Quizzes                                             10%

Midterm Exam                                 25%

Final Exam                                       40%

 

 

Academic Honesty:

In recent years, there has been an increased number of cheating incidents in many UC campuses, and unfortunately, UCSC is no exception.  The Computer Science Department of UCSC has a zero tolerance policy for any incident of academic dishonesty.   If cheating occurs, consequences within the context of the course may range from getting zero on a particular assignment, to failing the course.   In addition, every case of academic dishonesty is referred to the students’ college Provost, who sets in motion an official disciplinary process.  Cheating in any part of the course may lead to failing the course and suspension or dismissal from the university.

 

What is cheating?  In short, it is presenting someone else’s work as your own.  Examples would include copying another student's written homework assignment, or allowing your own work to be copied.  Although you may discuss problems with fellow students, your collaboration must be at the level of ideas only.  Legitimate collaboration ends when you "lend", "borrow", or "trade" written solutions to problems, or in any way share in the act of writing your answers.  If you do collaborate (legitimately) or receive help from anyone, you must credit them by placing their name(s) at the top of your paper.

 

The following is from the Winter 2002 Schedule of classes under General Information:

 

Academic Integrity

All members of the UCSC academic community have an explicit responsibility to present as their original work only that which is truly their own. Cheating, plagiarism, and other forms of academic dishonesty are contrary to the ideals and purposes of a university and will not be tolerated. Note that plagiarism includes the deliberate misrepresentation of someone else's words and ideas as your own, as well as paraphrasing without footnoting the source. Students and faculty are jointly responsible for assuring that the integrity of scholarship is valued and preserved.

 

To view the full text of the new policy on academic integrity on the Web, see:

http://www.ucsc.edu/academics/academic_integrity/

 

Due Process

Students charged with academic dishonesty have the right to due process through established policies and regulations concerning student conduct and discipline. Copies of these policies and regulations can be found in the Rule Book (http://www2.ucsc.edu/judicial) which is available at the offices of each college provost, the dean of graduate studies, and the Vice Chancellor of Student Affairs.