Instructor: Dr. John Dalbey	Office: 14-203
Phone: 756-2921 SMS to email: (805) 776-3543	Office Hours:  MWF 1100  Th 10-12
CSc Dept: 756-2824	E-mail:

Catalog Course Description

Introduction to data structures and analysis of algorithms. Abstract Data Types. Specification and implementation of advanced data structures. Theoretical and empirical analysis and proofs of properties of recursive and iterative algorithms. Software performance evaluation and testing techniques. 3 lectures, 1 laboratory.

Prerequisites:
1) Grade C- or higher in CSC102 - Fundamentals of Computer Science II. 
 You are expected to be knowledgeable and experienced in problem solving and software development using an object-oriented programming language.
2) Grade C- or higher in CSC141 - Discrete Structures I.
You are expected to know and be able to apply mathematical concepts, formulas and proof techniques learned in CSC141

Required Textbooks

Required Equipment

Course Objectives

• Meet the University Learning Objectives and the Computer Science Department Objectives.
• To be able to select and design appropriate data structures for the solution of a software problem. (example)
• To know the structure, operations, and implementation of "classic" data structures:  Lists, Stacks, Queues, Priority Queues, Sets, Maps, hash tables, Trees, and Graphs.
• To create software applications that use "classic" data structures using the object-oriented paradigm.
  
• To learn how to analyze and evaluate algorithm performance and compare different algorithms.

Major Course Topics

Class Structure

Coursework

Readings

There will be assigned readings in the textbook and other resources.   The readings are to be completed by the date shown on the calendar.  Not all material in the reading will be covered in lecture or lab but you are still responsible for knowing it for quizzes and exams.  Come to class prepared with any questions from the reading that you would like addressed.  Your preparation will be assessed by your lab partner on a weekly basis.

Homework

There will be homework problems assigned for each reading assignment.  The problems are to be completed by the date shown on the calendar.  The homework is to help you assess your comprehension of the reading material and prepare you for the class discussion, quizzes, and exams.   It is permissible to discuss the homework with other students.
The solutions to most of the problems will be made available so you can check your work.   Usually you will not have to submit your work to the instructor, but you may be called on during class to present your work on the board. In the rare event when you must submit your solution it will be noted in the assignment.

The purpose of the lab is to implement, test and analyze data structures and algorithms introduced during the lecture. During the lab hour you will complete structured hands-on activities on the computer. The assignments are designed to be completed during the allotted lab time, but you may occasionally find you need more time to complete them, in which case you may finish the activity outside of class time at home or in some other lab. 

All labs activities are completed by a team of two, and thus attendance is required. Partners will be assigned each week by the instructor.  Two students will share a single workstation, and each will be assigned a role, either "driver" or "navigator."  The navigator is the person who leads the problem solving effort.  The driver is the person who operates the keyboard.  (Of course the driver may assist in solving the problem).   Each person will submit a separate copy of the solution. 

Labs are graded credit/no credit.  To receive credit for the lab

• arrive on time
• be an active participant
• submit a solution before the deadline that shows a reasonable attempt to solve the problem.

The labs are intended to be a collaborative effort. Do not begin work on the lab activity prior to the lab even if it is posted in advance. If you complete the lab during the hour, show your solution to the instructor before leaving.

Each lab team is required to bring a Java reference and the Weiss textbook to each lab activity.

Programming Activities

Programming activities are in-class structured assignments to practice a variety of software development tasks:  analysis, system design, class design, method design, system test case creation, unit testing, code tracing, implementation, testing, and debugging. 

Programming Projects

There are several programming projects to be completed during the course. The projects are where you will demonstrate your software development skills and your ability to apply the course concepts. You will be given a software specification and you need to write a design and implement the solution.  Your projects will be graded on their functionality as well as design and coding quality. You must work on the projects outside of class time. You can use computing facilities of the university, or you can choose to work at home. 

These projects will be specified by the instructor and will include fairly comprehensive and detailed design requirements.  Your program will be graded by an automatic, web-based grading system called Web-CAT.   If you would like instructor feedback about your work you may visit the instructor during office hours, or submit a printout of your solution during class on the due date (printout requirements).  These are individual assignments.  Collaboration of any kind is not allowed.   (See below.) 

You must score an average of 60% on the projects to earn a passing grade in the course.

Exams

There will be a midterm examination and a comprehensive final examination.  The midterm exam has three parts.  The "theory" part (closed book) takes place during lecture hour and will contain problems just like the homework problems; the "design" part (usually closed book) is also a written exam where you are given a programming problem and must create one or more designs to solve it.  The "implementation"  part (on the computer, usually open book) takes place during the lab hour.  This lab exam requires you to implement a design provided by the instructor and provide working tests of its correctness.

If your cumulative score in the course before the final exam is so low that earning 100% on the final would not enable you to pass, you are not eligible to take the final.

The department has a 1st year cumulative assessment that takes place during the last week of class.  This is a test of everything you've learned during the first year CSc courses.  It counts for only a tiny part of your grade but may help you to identify any areas of weakness you want to work on.

Extra Credit

Students may complete optional assignments for extra credit.  Occasionally there will be specific extra credit opportunities announced.   In general you may visit the instructor any time to discuss extra credit.

Grading

Letter Grades are determined on a straight percentage basis, as follows:

    A    90% - 100%,    B    80%-89%,    C     70%-79%,    D     60%-69%,    F    59% and below
 NOTE: You must earn a grade of C- or better to be able to enroll in CSc 308.
(The instructor may scale these ranges as appropriate). Borderline scores will receive a Plus/Minus grade. 

• Why this course is important for software developers.
• Where Mr. Dalbey's teaching style falls on the spectrum of theoretical/applied.

Administrative Policies

ATTENDANCE

DEADLINES

Due dates for all coursework are shown on the course calendar. Late work receives no credit.

If you anticipate some unexpected circumstances will prevent you from submitting your assignment before the deadline, you may request an extension. Send an email message to the instructor before the due time asking for an extension of the due date.  (Use a subject line of "Extension request".) You don't need to provide a reason or justification.  (Limit: 1 project extension, 1 lab/other.).   The default extension is 24 hours, but you may ask for more.

ACADEMIC INTEGRITY

This course involves both individual work and collaborative work. It is your responsibility to understand the guidelines that apply to each kind of work, and to be clear about which assignments are individual assignments and which are collaborative.

Activities not designated as cooperative assignments in this course are to be done individually. Individual work is to be carried out entirely and solely by an individual. You may not "work together" on individual assignments. The content of the assignment is not to be discussed or shared in any way with other students.  There is to be no conversation about individual assignments except with the instructor or a department-designated tutor.  This policy will be rigorously enforced.  Programs will be checked for plagiarism using both computer and human similarity checkers.  Take extreme precautions that your individual work is not viewed by other students.  This includes deleting all your computer files from public workstations when you are finished,  retaining private permissions on your Unix files, destroying printouts of source code, and not letting other students use your personal computer where you store your coursework.  

Assignments which appear to be the result of a "group effort", or appear to have been copied from another student, will be considered plagiarized. Violations of this policy may result in being failed from the course and a letter placed in your record at the Office of Judical Affairs.. See the campus statement on Academic Dishonesty: Cheating and Plagiarism (C.A.M. 684)

A number of important class documents will be made available in electronic form (e.g. assignments, due dates). They can be accessed via a WWW browser through the link from the instructor's home page. These files should be considered as evolving documents, as they will be refined and updated as the course proceeds.  It is your responsibility to be sure that you are working from the most current document.  You may access documents on the course web site only via hyperlinks.  You are not authorized to view other documents that may exist but have no hyperlink to them.

The instructor will not read email whose "Sender" field is not an actual student name. Don't use nicknames in mail you send to the instructor or it will be returned to you unread.

Students are expected to learn and abide by the principles of ethical use of computers as determined by the ACM (Assoc. for Computing Machinery) Code of Ethics and Professional Conduct, the Campus computing and Communication Policies, Calif. state laws (see Penal Code Section 502), and federal laws. 

Grader UNIX account : ~graderjd

This account contains certain documents and sample programs you will need to complete the class assignments. Campus computing policies (as well as state and federal laws) prohibit you from reading files in other user's accounts, regardless of whether the file permissions allow such actions, unless you have been given specific authorization to do so.  You may access only those files to which the instructor or account owner has specifically given you verbal or written authorization.

GETTING ASSISTANCE

Study Groups:
The university organizes study groups for this course. 

Tutoring:
Computer Science department is organizing free tutoring for CPE101/102/103 courses.

Office hours: 
One of the great benefits of attending Cal Poly, as opposed to a University of California, is the opportunity to interact directly with your instructors. You are invited to take advantage of this opportunity by visiting the instructor during office hours, even if you are not having difficulties with the course. Of course if you are having difficulties, you should see the instructor as soon as possible.  If you need help with any form of programming activity, you should bring a current hardcopy of your source code.  If schedule office hours are not convenient for you, other times can be reserved by arrangement.

Email:
The instructor will read his email daily (except weekends) and email is a good vehicle for certain kinds of communications.  Use e-mail to report errors on the class web site, to report problems in your electronic submission, to clarify assignment requirements, to reserve an appointment, to ask concise technical questions, or to ask short questions that can be responded to with a short answer (a sentence or two).  Complex questions or abstract questions are best dealt with in person. Many programming problems, including debugging, are best handled during office hours.  It is probably not the best use of email to send your entire program and say "I can't figure out what's wrong."  

HOW TO ADDRESS THE INSTRUCTOR

Frequently I've heard students address me and other professors by last name without honorific.  They do this completely unselfconsciously even  when they aren't that comfortable with first name address.  (e.g. students will call me "Dalbey", not "Mr. Dalbey" when they would never  call me "John." ).  In "my generation", no-honorific last-name address is permitted only between people of common age and gender, between close friends or within a military or athletic context.  Buddies in college would call me "Dalbey", and fellow athletes would call me "Dalbey".  But that's it.  It's very analagous to "du" address in German, or second-person address in Latin languages.  Being addressed as "Dalbey" by students feels rude to me. My preferred form of address is "Mr. Dalbey."

CLASSROOM CLIMATE
It is a core value of academic discourse to be tolerant of views different than our own and to treat others with respect. 

In addition, an atmosphere conducive to learning can be fostered by minimizing distractions for others who are trying to  concentrate.  Common courtesies include:

• Arrive on time.  Students may arrive up to five minutes after the official class start time without penalty, if they enter quietly and take a seat in the row nearest the door.  Do not walk in front of the class. If you have some urgent need you must attend to that requires you leave the classroom in the middle of lecture, please follow the same courtesy and take a seat near the door when you return.  Of course if you have some special situation such that you anticipate in advance that you will be tardy, please make arrangements with me and you can avoid any penalty.
  
• Smartphones, tablets, and other portable devices are prohibited in the classroom.  It doesn't matter if it's before class.  If you feel you must use your device prior to class, do so in the hallway. (If you have a legitimate need, see the instructor).
• Do not use a notebook computer during lecture. (If you have a legitimate need, see the instructor).
• Don't wear headphones or earphones and don't listen to portable devices in classroom or lab.
• Only one person speaks at a time during discussions; no side conversations.
• Wait until class has been dismissed before packing up.
• The use of audio-visual recording devices of any kind (camera, tape recorder, etc) is not allowed without the instructor's permission
• Student are expected to behave in a professional and respectful manner towards their peers and faculty.  This includes appropriate verbal and written speech.  Profanity is not acceptable during any class function.   "Appropriate speech" also applies to computer source code, comments, test cases, etc; never use rude or insulting remarks in professional documents.