Second required programming course in the CS Major (after CIS1068). Program style, organization and design with continued emphasis on the object-oriented design paradigm. Understanding and use of data abstraction through Java classes and class libraries. Understanding of generic programming. Introduction to GUIs and event-oriented programming. Understanding and use of the following Abstract Data Types: strings, stacks, queues, priority queues, lists, linked lists, trees, heaps, and hash tables. Introduction to expression evaluation and other applications. Introduction to recursion. Comparative analysis of searching and sorting algorithms and data structures. Sorting algorithms include insertion sort, mergesort, heapsort,and quicksort. Searching algorithms include binary search, hashing, and Huffman coding. At the end of the course students are expected to be able to develop good quality (~1000 lines) programs that solve interesting and relevant problems using the data structures we have studied. They should demonstrate understanding of careful development, testing, informal justifications of correctness, and some performance estimation.
Prerequisite: Grade of C or better in CIS1068 Additional information about this course can be found on WWW at URL http://www.cis.temple.edu/~ingargio/cis68/.
Instructor: Dr. Giorgio Ingargiola
- Office : Wachman Hall, Room 1038
- Phone : (215)204-6825
- E-Mail : giorgio@temple.edu
- Contact Hours : Wednesday from Noon to 1:30pm, Thursday from 2:30 to 4:00 or by appointment, or take your chances and drop by.
- Lecture Time: Tuesday and Thursday: 9:30am to 10:50am in Tuttleman 302
- Laboratory: Thursday from 12:30pm to 2:20pm in Wachman 200
Teaching Assistant: Vladan Radosavljevic
- Office : Wachman Room TBS
- Phone : 215-204-TBS
- E-Mail for homeworks: vladan@ist.temple.edu
- Help Homepage: www.ist.temple.edu/~vladan/
- Contact Hours : Monday 10-12, Tuesday 3-5, Friday 10-12
Miscellaneous: Our first class (Section 1) is on Tuesday August 31and the last class is on Tuesday, December 7. The last day to drop the course (and get tuition refund) is Tuesday , September 14. The last day to withdraw from the course (no refund) is Monday, November 1. Students who have previously withdrawn from this course, or who have already withdrawn from 5 courses since September 2003 may not withdraw. Each student should have a general Temple email address. Important student information is accessible from http://owlnet.temple.edu/ Any student who has a need for accomodation based on the impact of a disability should contact me privately to discuss the specific situation as soon as possible. Students with documented disabilities should contact Disability Resources and Services at 215-204-1280 in 100 Ritter Hall to coordinate reasonable accomodations. Freedom to teach and freedom to learn are inseparable facets of academic freedom. The University has adopted a policy on Student and Faculty Academic Rights and Responsibilities (Policy # 03.70.02) which can be accessed through the following link: http://policies.temple.edu/getdoc.asp?policy_no=03.70.02 Students should be familiar with the University’s Statement on Academic Honesty [http://www.temple.edu/bulletin/Responsibilities_rights/responsibilities/responsibilities.shtm#honesty]and the Student Code of Conduct [http://policies.temple.edu/getdoc.asp?policy_no=03.70.12]or should contact the Student Orientation Office, 215-204-8531
Textbook: DATA STRUCTURES: ABSTRACTION and DESIGN using Java, 2nd Edition By Koffman/Wolfgang, Wiley, 2010
GRADING
- Weekly : 18% 10 minute tests: Eleven tests, given each week, only your top ten scores will count
- Midterm 1 : 10% Thursday, September 30
- Midterm 2 : 12% Thursday, October 28
- Final : 35% From 3:30 to 5:30am on December 15 in Tuttleman 303AB
- Homeworks : 25%
Disastrous performance in either the exams, or in the homeworks, will result in a Fail grade. Class attendance is required. Absence in more than 20% of the classes will result in a penalty of at least half a letter grade. Students who are more than 30 minutes late will not be admitted to class that day.
Attendance to the laboratory is MANDATORY. Absence from more than four labs will result in the loss of at least one letter grade.
EXAMS: The exams are closed book. Their content is cumulative, i.e. they address the material covered up to the day of the exam. If a student misses a midterm for an emergency [as agreed with instructor], there will be no makeup exam: the final will become proportionally more important. If you miss a midterm without previous agreement and without definite proof as to the medical or legal reasons, you will get a zero for that exam. Weekly 10-minute tests that are missed will not be made up. The final exam is mandatory on the scheduled day.
HOMEWORKS: Each homework must be completed on time and sent by e-mail to the Teaching Assistant (TA). For each homework, you must submit a design document along with the program and a test of the program (once we have shown you how to do this!). The design document will show the steps you took to design the algorithm and will follow the software development method used in the text. The homeworks will be graded, commented upon, and returned by e-mail by the TA usually before the next homework is due. Homeworks late up to 24 hours will be penalized 2 points (out of 10 possible). Homeworks that are late by more than 24 hours will not be accepted by the TA; the instructor may accept them in case of emergencies. You are expected to work and complete all the homeworks on your own. Plagiarism will be severely punished. See the University Policy on Plagiarism and Academic Cheating.
COURSE LEARNING OBJECTIVES:
A. Review
- Basic concepts of Java
- Abstraction, classes, inheritance and the class hierarchy, polymorphism
- Interfaces, abstract classes
- Exception classes
B. GUIs and Object Oriented Programming
- Overview of events and event oriented programming
- Events, listeners, call backs
- Overview of the AWT and Swing hierarchy, components and containers
- Swing components
C. Recursion
- Recursive thinking
- Examples of recursion
- Recursive data structures
- Problem solving with recursion
- Backtracking
D. Careful Software Development
- The Waterfall model
- The Unified Model
- Agile Models
- UML Class hierarchy
- Testing and the JUnit framework
- Reasoning about programs
E.Generic Programming
- Generic types, bounded type parameters, subtyping, wildcards
- Type erasure
F. Lists
- Array lists, linked lists, doubly linked lists, iterators
G. Collection Framework
- Objectives of the Collection Framework
- Collection, Iterable, and Iterator interfaces
- Collection implementations
H. Stack and Queues
- The Stack abstract data type
- Stack applications
- Stack implementations
- The Queue abstract data type
- Queue applications
- Queue implementations
I. Trees
- Tree terminology and applications
- Tree traversals
- Binary Search Trees
- Heaps and Priority Queues
- Huffman Trees
J. Sets, Maps, Hashing, and Hash Tables
- Sets and the Set Interface
- Maps and the Map interface
- Hashing
- Hash Tables
K. Sorting
- Elementary sorting methods: Selection, Insertion, Bubble
- Efficient sorting methods: Heapsort, Quicksort, MergeSort
L. Graphs
- Graph Definitions
- Graph ADT and its Implementations
- Graph Traversals