Description:  Studies basic algorithms and their relationships to common abstract data types.  Covers the notions of abstract data types and the distinction between an abstract data type and an implementation of that data type.  The complexity analysis of common algorithms using asymptotic (big "0") notation is emphasized.  Topics include sorting and searching techniques, basic graph algorithms, and algorithm design techniques.  Abstract data types covered include priority queues, dictionaries, disjoint sets, heaps, balanced trees, and hashing.  Familiarity with C, Java, and Unix is assumed.

 

Prerequisites:  CMPS 012B and CMPE 016; and either MATH 019B or MATH 011B or ECON 011B; and either MATH 021 or MATH 022 or MATH 023A.

 

Time and Place:  MWF  12:30 – 1:40    J Baskin Engineer 152  

Class Webpage: http://www.soe.ucsc.edu/classes/cmps101/Winter04/

Class News Group: ucsc.class.cmps101

 

Instructor:   Slim Ouni   (http://mambo.ucsc.edu/psl/slim)

Office:   Social Sciences II – 429G

Office Hours:  MW  2:00pm – 3:00pm,  and by appointment.

Email:   slim@fuzzy.ucsc.edu   (You must add     [CMPS101]  in the subject of your email)

Phone:   831-459-2655



Teaching Assistants:


Lab-Discussion Sections: Will be used by the teaching assistants to clarify some points in the course, providing some examples, discuss programming projects, homework problems, and to prepare for exams. At least one section during the week will be used as a theory section. Attendance of the theory sections is required (your TAs will determine which sections will be theory sections and they will maintain a record for the student attendance). Attendance of the other sections is highly recommended.  It is very important to note that lab-discussion sections are a part of the course: Attending only the lectures is not sufficient to pass the class.

(See with the teaching assistants for any changes in the schedule)


Schedule:

 

 

Required Text:

Introduction to Algorithms, second edition, by Cormen, Leiserson, Rivest, & Stein.  McGraw-Hill, 2001. 

Optional Text:

Computer algorithms: introduction to design and analysis  by Sara Baase & Allen Van Gelder, Addison-Wesley, 2000.

 

Having the required textbook is very important to get a very detailed explanation of the material presented in lectures. I will ask you very often to read some sections in the book that will be a part of the course material.

 

The following reading schedule is a rough guide to what we will discuss and when. It is subject to change. We may add more sections or remove some sections. Although the required textbook will be used, what we will discuss in class is the basis of all evaluations.

Week                                                Topics

1                                                            Introduction-Analyzing algorithms

2                                                            ADT –list, trees, stacks and queues

3                                            Asymptotic growth rates of functions                                           

4                                                     Recursive proc, Induction proofs

5                                                             Insertion, divide and conquer, Quicksort

6                                                             MergeSort, Heapsort

7                                                             Red-black trees, Hashing

8                                                             Graph algorithms, DFS, Strongly Connected Comp

9                                                             Prim’s min span., Single source shortest paths

10                                                         All-pairs shortest paths in graphs

 

Programming Language

For all the programming assignments, we will use C language. 

 

Coursework and Evaluation:  (Please read carefully)

(1) Homework consists of written assignments related to sections presented and discussed in class or related to a reading section. These written assignments are mandatory. All the written assignments must be returned otherwise the homework grade will be zero (the personal work will not be validated unless all the written assignments are returned).

 

(2) We will have several programming Assignments. It is very important to answer exactly to the different questions: use exactly the function names as presented in the specification. Use exactly the same input and produce the same output as required in the assignment. The respect of the deadline for each programming assignment will be reinforced this quarter. There will not be any exception (excuses like: power outage, disc crash, system crash, last minute health problem, missed the bus, etc will not be accepted). You have to start working on your programming assignment as soon as possible. Make multiple copies of your work and always keep the latest version in a safe place.

 

(3) We will have two midterms and one Final Exam. All the exams are comprehensive.

 

(4) This class will not be considered complete if you do not:

             - Return all the written assignments AND all the programming assignments

             - Attend the midterm exams AND the final exam.

(4') Incomplete in (4) means  you will get the grade F

(5) In extraordinary circumstances (justified illness with a medical note), you will be required to complete an alternative assignment. Any negligence in doing the homework will be recorded and mentioned in the evaluations.

 

(6) Coursework will be weighted as follows:

Homework                                             10 %

Programming Assignments                    30%

Midterm Exam 1                                    15%

Midterm Exam 2                                    15%

Final Exam                                             30%

 

(7) Midterm Exam 1 date: Friday, January 30th

      Midterm Exam 2 date: Friday, February 20th

      Final Exam date : Thursday, March 18th

 

(8) To pass the class you need to obtain 70% ( grade C). Any grade less than 70% (even if it is 69.9%) will not be adjusted to 70%

The letter grades will be as follow:

               A             90% - 100%

               B             80% - 89.99%

               C             70% - 79.99%

               D             60% - 69.99%

               F             less than 60%

 

(9) All students are assumed to read the above points. If you cannot attend the lectures or the lab-sections, if you cannot return your homework and programming assignments on time for ANY reason, if you cannot attend the midterms and final, it is better for you to drop the class. No makeup exam will be offered for any reason (except point (5)). All grades are final.

 

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 Baskin School of Engineering has a zero tolerance policy towards 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 to these sanctions, 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.

Academic Integrity

http://www.ucsc.edu/academics/academic_integrity/undergraduate_students/index.html