Abstract Data Types

Fall  2003

• Announcements: (12/05/03) 12:00AM
  

• Handouts

• HeapSort notes (incomplete)

• Quicksort notes (incomplete)

• Binary Search trees and Red-Black trees (incomplete)

• Minimum Spanning Trees (incomplete)

• Graphs and Graph Traversals

• Induction and Recursion (Complete but not final version) Other parts are covered only during lecturespart 1 part 2 part 3

• Growth of Functions

• Abstract Data Type and Modules in C

• From Java To C : A Supplement to Computer Algorithms, Third Edition

This document may help those of you who are more familiar with Java than C.

• MergeSort Example (Design and Analysis)

Second part of the first chapter (Divide & Conquer example).

• Homework Assignments

  • Homework Assignment 1 (due at 11am on 10/06/03 in the class) Solution

  • Homework Assignment 2 (due at 11am on 10/20/03 in the class) Solution

  • Homework Assignment 3 (due at 11am on 11/14/03 in the class)Solution

  • Homework Assignment 4 (due at 11am on 12/03/03 in the class)Solution(pdf) (doc file in case some figures are missing in the pdf)

  • Midterm - Review Exercises (these exercies cover a big part of all the lectures)Solution

  • Quiz #1 solution

  • Quiz #2 solution

  • Midterm solution

  • Quiz #3 solution

  • Quiz #4 solution

• Programming assignments
• Programming assignment 1 (Due at 12:00 (midnight) on 10/13/03 (The end of the day)
• Programming assignment 2 (Due at 11:59pm on 10/29/03)
• Programming assignment 3 (Due at 11:59pm on 11/19/03)
• Programming assignment 4(Due at 11:59pm on 12/03/03)
• Submission instructions
• You will find here some resources that may help you to prepare this assignment: A review of ADT (pdf) also a complete example is included that goes with this document (1 2 3 4)
  
• Pseudo-code convetions (recommendation on how to write algorithms for the written assignments) PDF
• How to write a Makefile (Some basic concepts on makefiles)

• Genral Information
  

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  11:00 – 12:10    J Baskin Engineer 152  

Class Webpage: http://www.soe.ucsc.edu/classes/cmps101/Fall03-02/

Class News Group: ucsc.class.cmps101

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

Office:   Social Sciences II – 429G

Office Hours:  MWF  2:00pm – 4: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:

• Suma Potluri (suma@cse.ucsc.edu)
• Hemanth Singamsetty (hemanth@cse.ucsc.edu)

MSI Sessions:

• Learning Assistant: Nikhil Bobb (nbobb@ucsc.edu)

Schedule
Monday         5:00-6:10pm         ARCenter Room 203
Tuesday         4:00-5:15pm         Baskin White Boards
Wednesday     12:30-1:40pm         Baskin White Boards

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.  Attendance is highly recommended.  (See with the teaching assistants for any changes in the schedule)

Schedule:

01A      LBS                 F          2:30PM           4:00PM            J Baskin Engineer 105

01B      LBS                 W        02:00PM          03:30PM          J Baskin Engineer 105

01C     LBS                 F          04:00PM          05:30PM          J Baskin Engineer 105

01D     LBS                 M         07:00PM          08:30PM          J Baskin Engineer 105

01E      LBS                 R          03:30PM          05:00PM          J Baskin Engineer 105

01F      LBS                 R         11:30            01:00PM          J Baskin Engineer 105

Required Text:

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

Optional Text:

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

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               Sections                                               Topics

1                                                    1.3,1.4                      Math Background-Analyzing algorithms

2                                                    1.5                            Asymptotic growth rates of functions

3                                                    2.1-2.5                      ADT –list, trees, stacks and queues

4                                                    3.1-3.4,3.6,3.7          Recursive proc, Induction proofs

5                                                    4.2-4.4                      Insertion, divide and conquer, Quicksort

6                                                    4.5-4.8                      MergeSort, Heapsort

7                                                    6.4-6.5                      Red-black trees, Hashing

8                                                    7.1-7.6                      Graph algorithms, DFS, Strongly Connected Comp

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

10                                                9.4                            All-pairs shortest paths in graphs

Programming Language

For all the programming assignments, we will use C language (for one or two programs, we may introduce C++). However, as the required textbook uses Java-Based pseudo-code conventions, I assume that you are familiar with Java; in other words, you are able to read a Java program (or Java-Base pseudo-code)

Coursework and Evaluation:

Homework consists of written assignments related to some sections presented and discussed in class or related to a reading section. These written assignments are mandatory. Each homework will be followed by a quiz in class. We will have Programming Assignments almost each two weeks. We will have one Midterm and one Final Exam. This class will not be considered complete if you do not attend the midterm exam AND the final exam. 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.

Coursework will be weighted as follows:

Personal Work                                     20 %

Programming Assignments                    30%

Midterm Exam                                      20%

Final Exam                                           30%

By “personal work”, we mean homework, quizzes and other evaluations. We (the instructor and the TAs) will evaluate for each student how much work does he/she actually have done. We may ask you more specific questions to better evaluate your work. This will be the case for programming assignments, too.

Mid-term Exam : Monday, November 3rd

Final Exam date : Monday, December 8 12:00–3:00 P.M.

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