Antelope Valley College, Instructor Charles Costarella

CIS 113 Data Structures - (available only in the Spring semester)
Spring Semester 2011
CRN 35149 CIS 113 Monday 06:00pm - 10:05pm BE 324 02/07/2011 to 06/03/2011
Charles Costarella, Adjunct Faculty
661.400.4623  Cell and Voice Mail
avccis113@gmail.com

ANNOUNCEMENTS:

Announcements will be posted in this section. Check this section at least 1 or 2 times each week in case of last minute changes.
Date Announcement
Week 1 There is a CIS-111 Yahoo discussion group located at: http://groups.yahoo.com/group/avccis111. While it is primarily there for the CIS-111 students, as a CIS-113 student you are welcome to join this group and participate in the forum if you want to. I would expect you to take more of a mentor role in the group, meaning that you could answer questions and help out the CIS-111 students as well as get information for your own projects. Do not give out extensive code examples or do anyone's homework for them. You need a Yahoo email to join this group, but once in, you can use any email you like.
Week 1 Currently, office hours for adjunct faculty have been discontinued due to budget cuts. More information may be available the first few days of the semester, so please ask for an update in class. I may find some limited office hours for those students with special needs on a case by case basis and at my discretion. I strongly suggest you utilize one on one time with me during the lab portion of the class meetings.
Week 1 Please note the email address to be used for this course is NOT an AVC email address. For organizational reasons, you must use the class email address. Send all assignments and other email to: avccis113@gmail.com

Required Materials:

Course Requisites:
CIS Computer Information Science Spring 2010 CIS 113 Prerequisite: Completion of CIS 111 or CIS 161. Advisory: Eligibility for ENGL 099, READ 099 and MATH 130, and Completion of CIS 121. This course continues the introduction to programming and algorithms begun in CIS 111, with a particular focus on the ideas of data abstraction and object-oriented programming. Topics include object-oriented programming, fundamental data structures, design and implementation of abstract data types, common types of collections (such as stacks, queues, lists, graphs, trees and sets), algorithm analysis and complexity, search and sort algorithms, and the use of recursion. Students plan and create programs using data structures and collection types to solve problems frequently encountered by professional computer scientists. This course is intended for students majoring in CIS. (Engineering and science majors consult counselors) (CSU, UC, AVC) Course Corequisites: NONE

Course Description:
This is a second course for students planning or exploring a career in software development. This course emphasizes a disciplined approach to computer programming. Problem solving through stepwise development of algorithms is presented. Students will learn more advanced language syntax, coding, logic, and testing. You will study the more advanced mechanisms of Object Oriented Programming, and use them in your programming assignments. We will use Java as the implementation language. Topics covered will include static and dynamic data structures and utilization of ADT (abstract data type) techniques. Programming assignments will utilize Object Oriented design and implementation of multiple classes/modules with focus on configuration management, code reuse, and advanced Java language techniques including exception handling, inheritance, polymorphism, interfaces and abstract classes, inner classes, persistance and object serialization. We will only work with elements of Java that are considered standard. Object Oriented Programming will be strongly emphasized.

Course Objectives:
Upon completion of the course, the successful student will be able to:

  1. Explain the philosophy of object-oriented design and the concepts of encapsulation, inheritance, and polymorphism.
  2. Design, implement, test, debug, and document user-defined data structures in an object-oriented programming language.
  3. Determine the time and space complexity of simple algorithms and express them in Big-O notation.
  4. Discuss the computational efficiency of the principle algorithms for sorting, searching, and hashing,
  5. Compare alternative implementations of abstract data types with respect to performance.
  6. Evaluate the tradeoffs between time and space efficiencies when implementing an algorithm.
  7. Choose the appropriate type of collection for modeling a given problem.
  8. Describe common applications for each type of collection.
  9. Solve problems using the fundamental data structures and the common collection types and write programs to implement those solutions.
  10. Explain the value of application programming interfaces (APIs) in software development.
  11. Describe the divide-and-conquer and backtracking approaches to solving problems.
  12. Demonstrate different traversal methods for trees and graphs.
  13. Describe how iterators access the elements of a collection.

Rules for Submitting Assignments:
During the semester, you will have 4 or 5 program assignments. All will be complete Java programs that you write. Some will include work that we will begin together in a hands-on lab. For each assignment, there will be different deliverables that you must submit to me to receive credit. I will cover this in detail when I make each assignment. Programming assignments will include elements from all stages of software development including requirements gathering, high and low level specifications, design, implmentation, debugging, unit testing, integration testing, acceptance testing, demonstrating program correctness, and even modification/maintenance. Many of the programming assignments we work on will depend and expand on the work you produced in earlier programming assignments, so lab and class attendance is critical.

  • You must email your assignments to me as attachments. (Do not insert the text or source code into the body of the email.)
  • The email Subject MUST identify the assignment for you to receive credit for your work.
  • Use a business like email address that has some form of your actual name in it for the duration of the semester. This will help me recognize who you are on my roll sheet. If you insist on using a vanity email address with a cryptic name that I cannot resolve with my roll sheet, it is your responsibility to identify yourself so that credit for your work ends up in the right place. I suggest that you DO NOT use your school supplied AVC email address due to the extra steps involved in attaching files.
  • Send your email before the beginning of class the date the assignment is due. Late work will not earn full credit. It is not fair to those students who submit work on time.
  • You are required to keep electronic copies of ALL assignments for the duration of the semester. This is for your own protection in case of lost or corrupted email, network problems, etc. I am not responsible for backing up or archiving your work, even after you turn it in to me. Please do not trust a flash drive for this important task. A copy of your work is good but 2 copies are better. Networks fail. Cables, routers, satellites and modems break. All the mechanical devices in the world will eventually fail. This is a mathematical certainty. Plan ahead for failure, and have an A, B, and a C plan. Network and other mechanical failures are not valid excuses for missing a deadline. I suggest getting one or more GMail accounts because of the large amount of storage they provide. When you send me an assignment (or more often if you want), you can CC a copy to your GMail address for backup.
  • For some assignments, you may be required to demonstrate a running program to me during the lab portion of the course. Prepare by having your program and any other relevant files already loaded on your computer and setup to run before you ask me to stop by your workstation for the demo.

IMPORTANT INFO IF YOU WANT FULL CREDIT ON A PROGRAM ASSIGNMENT
  • Your programs will be graded on appearance as well as functionality.
  • Code layout must follow examples in the text.
  • You will usually have one or two weeks to complete assignments. I will make the deadline clear for each program when I assign it.
  • The first thing in the comment section at the top of each file will be:
    1. A complete sentence describing the module's function or purpose, or role in the overall system.
    2. Your name and the date (javadoc users can use the date for version)
    3. The chapter number and program name
    4. The page where it is located in the book and the number of the assigned problem(s). 
    Here is an example: 
    /**
 * A class to manipulate thermostats in the NuclearReactor program.
 * @author Chuck Costarella
 * @version 2011.03.15.01
 * Chapter 6 - NuclearReactor Program
 * Page 435 - Exercise 6.13 and 6.15
 */
  • You can use the standard Javadoc type comments with the standard tags for author and version, or you can follow the textbook's examples using C++ comments. I don't care which you use, but be consistent within a program.
  • Assignments must be emailed before the BEGINNING of class on the day they are due or before to receive full credit.
  • Concepts studied for an assignment must be demonstrated in that program assignment. Do exactly what is asked for. I encourage you to work ahead on your own, but do not include this advanced material in any program assignments until that material is assigned to the class.
  • Code generation tools may not be used in this course. If your Java IDE of choice is a Rapid Application Development tool, make sure you are writing all code that you submit yourself. Generated code will not be accepted for any graded assignments.
  • All identifiers should be self-documenting.

Exams:
Two exams (a midterm and a final) will be given. They will be evenly spaced during the semester. The final is cumulative and will require succcessful mastery of the course subject. You must tell me ahead of time if you are going to miss an exam, so other arrangements can be made. There may be a programming project assigned in place of an exam at the instructor's discretion. This project would be of a scope and difficulty level that would substitute for the exam.

Extra Credit:
There will be extra credit available from time to time on some assignments and exams. It will be of a very specific nature and only as I assign it.

Programs and assignments 4 or 5 at 20 to 25 points each 100 points
Quizes Undisclosed number of pop quizes at 5 to 10 pts. each ?? points
Exams 2 exams/projects at 50 points each 100 points
Total possible    200+ points

Letter Grade Total points range
A 180 - 200
B 160 - 179
C 140 - 159
D 120 - 139
F 0 - 119

Attendance:
Class attendance is extremely important for successful performance in the class. There will be information given in the lectures that will not be found in the text, the discussion group, or on this website. Assignments are given in class and are not available elsewhere or ahead of time. You will be responsible for all class instruction information. I strongly advise attending class. If you miss more than the equivalent of 3 weeks of class, you may be dropped for poor attendance.

Web Resources for Data Structures and Advanced Java Programming
There is a ton of information available on the web on Data Structures and Java Programming. I hope you find one or more of these useful.

Java Applets Center, University of Canterbury Animated Java Applets showing the behavior of the fundamental linear and hierarchical structures we will study.
Trees, trees, trees Animated Java Applets showing the behavior of all kinds of tree structures.
Programming in Java, by Robert Sedgewick, Princeton University This is the section of Sedgewick's book covering data structures, but the entire thing is excellent. The book's approach is very much coming from a scientific analysis and real world problem solving point of view. Real world problems and applied solutions using Java but very little emphasis on Java for the sake of Java. I feel one of this book's particular strengths is the use of large and real world data sets as input files. These are issues you will have to deal with in the working world. Just as one example, the complete text of the Bible is here in a text file. Sedgewick is one of my favorite authors and educators and is one of the inventors of the Red-Black tree. The Red-Black tree is the underlying implementation used throughout most of the Java platform's standard library of data structures. There is no Nobel Peace Prize for Computer Science (hey, what's up with that?), but Sedgewick has won the equivalent.
Data Structures and Algorithms in Java, 2nd Edition by Robert Lafore The complete text. Use this for another point of view from the Malik text that we are using. This book includes more advanced material, but also has very good coverage of the foundations.
Data Structures and Algorithms in Java, 2nd Edition by Robert Lafore Here are the example applets that go with the above text.
Java Structures by Duane Bailey, Williams College Prof. Bailey teaches at Williams College in Williamstown, MA. This is his complete Java Data Structures textbook, available as a PDF. He gives you full license to use it and print it for your own use if you want.
Towers of Hanoi Puzzle Well known computer science problem used to demonstrate the use of recursion to solve a problem (usually in place of iteration - looping).
Godfried Toussaint, McGill University Specific Course Material for COMP-251 as taught by Godfried Toussaint. Actually this is a lot more than just one course. Great reference for all kinds of Computer Science topics.
Great Java resource page Maybe this is Frode Haug's webpage? Not really sure what his name is or what language is being spoken/written, but the resources are great and he refers to Robert Sedgewick's C++ and Java books, which are among my favorites. Sedgewick teaches at Princeton (see above)
Eclipse Eclipse is an open source IDE for Java development formed by IBM Visual Age for Java and Borland JBuilder IDEs. Eclipse is a professional level tool and it is completely free and tons of Java development shops use it. This is the logical step up from JCreator when you feel like you are ready to grow.

Americans With Disabilities Act (ADA): Reasonable Accommodation
If you have a legally protected disability under the Americans with Disabilities Act (ADA) or California discrimination law, and you believe you need reasonable accommodation to participate fully in this class, please make an appointment to see me during my office hours to discuss your need.