Last day to withdraw: Monday April 26.

Tuesday February 23 and Wednesday March 24 are Wellness Days(no Class or Lab) Last Class Lecture: Monday, April 26. Last Lab Tuesday April 20

Instructor: Dr. James F. Korsh
Office: SERC 322  Phone: 204-8199  Email: korsh@temple.edu
Office Hours: To be decided at the start of classes.

Prerequisite: At least a C- in CIS 1068 and in CIS 1166.
Text (optional) and References:
Objects, Abstraction, Data Structures and Design Using Java - Wiley,   Koffman and Wolfgang
JAVA An Introduction to Problem Solving & Programming - 5^th Edition Pearson/Prentice Hall,  Savitch and Carrano
Java: How to Program - Prentice Hall,  Deitel and Deitel
Data Structures and Abstractions with Java - Pearson/Prentice Hall,  Carrano and Savitch
Date Structures and Algorithms in JAVA, 4th ed. - Wiley,  Goodrich and Tamassia

Assignments: There will be a series of programming assignments (5-7). Each will normally build upon previous assignments. You must write each program yourself but are encouraged to obtain help -  from fellow students, the laboratory instructor or the instructor - to get to the point that you can do so. The assignments are to be handed in on time or credit may be lost. You may develop the programs on any system but the program must end up on our system so it can be accessed, edited, and run in the laboratory.

Laboratory: You are expected to attend and use the laboratory equipment to access, edit, and run programs and to know how to use the programming environment it provides. A significant part of your grade will be based on your performance in the laboratory which includes your assignment grades. The laboratory provides for your interaction with other students as well as the Lab instructor.

Grades: Determined by a combination of performance in the Laboratory, on quizes, on the Mid Term and on the Final Examination. You should expect a short quiz each week. To obtain a passing grade a student MUST submit satisfactory assignments and get credit for each one. This means that first, the assignments must be turned in, be properly documented and execute correctly. Secondly, and most important, it is the responsibility of the student to arrange to meet with the lab instructor (in lab or during office hours or at a specially determined time) to run their program, explain it, and answer any questions about it. How well you do this determines your Laboratory grade for the assignment. NO CREDIT is given for an assignment unless this second requirement is carried out.

Late-to-class or missed class: It is the student’s responsibility to find out what material or announcements were missed. After reviewing this material,, if more help is needed, then the student can see the instructor or lab instructor.

Notes:
1. Since this is a lower division course, it is subject to midsemester evaluation.
2. You will be enrolled in this course on Canvas where much of the material and other information needed for this course is located. Canvas can be accessed through the TUPortal
3. Access to the Temple Technology USAGE policy can be obtained through http://policies.temple.edu/list_docs.asp#T.
4. Any student who has a need for accommodation based on the impact of a disability should contact me privately to discuss the specific situation as soon as possible. Contact Disability Resources and Serrvices at 215-204-1280.
5. Freedom to teach and to learn are inseparable facets of academic freedom. The University hasd a policy on Student and Faculty and Academic Rights and Responsibilities which can be accessed through http://policies.temple.edu/getdoc.asp?policy_no=03.70.02.

Description: The purpose of this course is to stress three main themes
- Basic Internal Data Structures and their impact on programs.
- The use of Data Abstractions and the implementation of Data Abstractions in Java using classes.
- Problem Solving Methodology and Algorithms and and their impact on programs.

This course covers basic data structures, important algorithms for carrying out needed operations on them, and illustrates the positive effect a proper choice of data structure can have on an application. The data structures will include arrays, linked lists, stacks and queues, binary trees, binary search trees, hash tables, min and max heaps, trees and graphs. The worst cast execution time of algorithm involving these data structures will be emphasized. The course will illustrate the use of recursion, a special case of top-down problem solving, in developing algorithms. Sorting will be covered including insertionsort, mergesort, heapsort and quicksort. The application of binary trees and heaps to sorting will used to develop heapsort and also for Huffman coding. Stacks will be used to determine valid parenthes strings. Graphs will be used in solving mazes. The Intcoll class will be introduced as a vehicle to demonstrate the use and implementaion of classes and numerous versions of it will be built. Each version uses either integer arrays, boolean arrays, a simple linked lists, generic linked lists, binary search trees, or hash tables. The Intcoll class will be generalized to a MultiIntcoll class and will be used as the starting point for developing a Stringcoll class and a MultiStringcoll class. The MultiIntcoll class will be used to demonstrate the significant impact of data structure choice on program execution time. The MultiStringcoll class will be used to count the number of occurrences of words in text and to again illustrate again the significant impact of data structure choice on program execution time. Inheritance will be applied to derive another version of the Stringcoll class from the Multistringcoll class.

The outline below should  give some idea  of what we will do and when we will do it, however, do not expect it to necessarily be rigidly followed. Be sure to talk with me about this at the start of classes if any significant deviation will present a problem to you.

OUTLINE Week:
1-2  Review of fundamentals of Java and its data structures. Discussion of programming style, problem solving methodology, and the top-down approach. The use of drivers. Introduction to data abstraction. Discussion of the Intcoll class and its use in the positive(P), negative(N), last(L) application. Three versions of this class are built - two using integer arrays and one using boolean arrays. Another application of the Intcoll class to a puzzle is discussed.
3-4   Introduction to linked lists. A simple linked list version and a generic LinkedList class version of Intcoll. Stacks and queues and the application of stacks to valid strings of parentheses.
5-6   Introduction to binary trees and binary search trees. A binary search tree version of Intcoll. Recursion. Binary tree traversals and searching, inserting and deleting algorithms for binary search trees.
7   Sorting - insertionsort, mergesort, quicksort.
8-9   Hash Tables. The MultiIntcoll class and comparison of different versions of it. The Stringcoll class and the MultiStringcoll class. Inheritance and the derived version of the Stringcoll class from the MultiStringcoll class.
10-11   Min and max heaps and their application to sorting (heapsort).
12   Trees and graphs and mazes.
13-14   Comparison of different versions of MultiStringcoll. Application of binary trees and heaps to Huffman coding. Review.