CIS1068: PROGRAM DESIGN AND ABSTRACTION [Spring 2010]

First required programming course in the CS Major. Problem solving and programming in Java, introduction to software engineering, procedural and data abstraction, and elementary object-oriented programming. Data types covered include primitive data types, strings, classes, arrays, array lists, and streams. Programming techniques include at least one technique for searching and sorting an array and an introduction to file processing. At the end of the course students are expected to be able write good quality small (100..200 lines) programs that solve small interesting and relevant problems.

Prerequisite: Grade of C or better in Mathematics 1021 (C073) or higher, or placement into Mathematics 1022 (C074). Grade of C or better in C+IN SC 1053 (0061) or 1057 (C071) or a passing score on a placement exam given during the first week of class.

Additional information about this course can be found on WWW at URL http://www.cis.temple.edu/~ingargio/cis67/.

Instructor: Dr. Giorgio Ingargiola

Lecture Time: Laboratory: Section 1: Teaching Assistant: Vuk Malbasa Section 3: Teaching Assistant: Vladan Radosavljevic Miscellaneous: Our first class (Section 1) is on Tuesday, January 19 and the last class is on Monday, May 3. The last day to drop the course (and get tuition refund) is Monday, February 1. The last day to withdraw from the course (no refund) is Monday , March 29. 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 statement on academic honesty found at the following link http://www.temple.edu/bulletin/Responsibilities_rights/responsibilities/responsibilities.shtml

Textbook: Cay Horstmann: Big Java, 4th edition, John Wiley 2010

GRADING

Disastrous performance in either the exams, or in the homeworks, will result in a Fail grade. Class attendance is required. Absence in more than 25% of the classes will result in a penalty of at least half a letter grade. 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

You will be assigned one homework each week. Each assignment must be completed on time and sent by e-mail to the Teaching Assistant (TA). 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.

LABORATORIES

Laboratories are lead by the Teaching Assistant. Attendance to the laboratory is Mandatory. In the laboratory you will be helped to learn how to use the programming environment: command language, editor, compiler, and debugger. You will be presented examples related to the material discussed in class and you will examine common errors and how to avoid them. Part of the laboratory time will be dedicated to work on your programming assignments. In the laboratory initially we will use command line commands javac, java, text editor. Later you will be encouraged to use a graphic interactive development environment like Eclipse

COURSE LEARNING OBJECTIVES:

A. INTRODUCTORY CONCEPTS

  1. Describe the basic components of a computer system: CPU, main memory, secondary memory, I/O, bus.
  2. Introduce performance measures of time, memory, speed.
  3. Examine the role of a compiler in the programming process.
  4. Describe the role of the Java Virtual Machine [JVM]
  5. Create and edit a program using a text editor.
  6. Compile a program using the command-line in a terminal window.
  7. Run a program using the command-line in a terminal window.
  8. See example of use of an IDE.

B. PRIMITIVE DATA TYPES AND VARIABLES

  1. Describe the primitive data types in Java: representation, operations and range of each primitive data type.
  2. Use positional notation to convert an integer to a base 10 numeral and viceversa
  3. Experiment with ASCII representation of characters and see some example of Unicode characters.
  4. Declare and initialize variables of each primitive data type.
  5. Write and evaluate expressions containing unary and binary operators, +, -, *, /, %, &&, ||, !, <, <=, ==, !=, >=, ==, ++ [pre and post increment], -- [pre and post decrement], using operator precedence rules.
  6. Write and experiment with short hand [||, &&] and complete [|, &] evaluation of conjuctions and disjunctions.
  7. Learn to use shorthand operators like +=, -=, *=, /=.
  8. Define and give examples of assignments.
  9. Write and evaluate expressions and assignments requiring conversions between primitive data types, some implicit, some needing type casting.
  10. Explain why overflow can take place when computing with integer [long, int, short, byte] variables.
  11. Explain why round-off error can take place when computing with real [float, double] variables.

C. PROGRAM FLOW AND CONTROL

  1. Use conditional statements [if, if..else, switch].
  2. Write, evaluate, and debug complex conditional statements [e.g. nested conditionals, sequences of conditionals, dangling if].
  3. Write, evaluate, and debug three loop statements [while, do/while and for].
  4. Show that do/while and for loops can be implemented using the while loop.
  5. Show how to control the number of times a loop is executed, experiment with various termination conditions, use sentinel values, recognise infinite loops.
  6. Learn to use when appropriate continue and break statements within loops.
  7. Learn to read code containing conditional expressions.

D. USING PREDEFINED CLASSES

  1. Recognize fundamental distinction in Java between primitive data types and reference types.
  2. Learn to use the Java API and to import chosen classes.
  3. Write code to use the Math class: abs, sqrt, random
  4. Write code to use the String class: charAt, compareTo, equals, indexOf, length, substring, and the concatenation operator.
  5. Write code to explore the consequences of Strings being immutable in Java. For example see that building a very long string a character at a time will be very time consuming. That instead substrings can be computed rapidly.
  6. See examples of use of the class StringBuilder and how it differs from String.
  7. Write code to use the Integer [MIN_VALUE, MAX_VALUE, parseInt], Character [isDigit, isLetter, toUpperCase], Double [NaN, parseDouble] classes
  8. Learn to use in the System class the objects in and out and the methods arraycopy and exit.
  9. Recognize that the instances referenced from reference variables have to be allocated and later taken care by garbage collection.

E. ARRAYS AND ARRAYLISTS

  1. Declare an array reference for a one-dimensional array of a given element type [both primitive types and reference types] and size using the keyword new.
  2. Recognize that an array reference can be null or it can reference an empty array.
  3. Declare and initialize a one-dimensional array with specific values using the {} notation. For example int[] a = {1,2,3}; and later a = new int[]{7,8,9,2,3};
  4. Understand the String[] formal parameter of the main method and write programs that use command-line parameters.
  5. Write code to access and set specific elements of an array. Use the length property to determine the number of elements in an array.
  6. Use a loop to traverse a given array and set its elements to some desired values.
  7. Write code to determine simple properties of an array of numbers, for example the smallest value and the average value.
  8. Write code to transform a given array, for example, reverse its content.
  9. Declare a two dimensional array and experiment to see that it is really a one dimensional array of one dimensional arrays and it can be jagged.
  10. Write code to traverse a two-dimensional array of scalars to compute some basic property [count, average, smallest value]
  11. Write code to transform a given two-dimensional array, for example, transpose a square matrix.
  12. Program with ArrayLists to deal with unknown numbers of elements. Recognize that the elements of ArrayLists must be reference.
  13. Use autoboxing and deboxing to facilitate the use of ArrayLists to store unknown numbers of primitive type values.
  14. Learn to transfer the content of an ArrayList to an array.
  15. Use the enhanced for loop statement to traverse arrays and ArrayLists

F. INPUT/OUTPUT AND FILES

  1. Write code to print to the screen strings and other data [System.out.println, System.out.print, System.out.printf].
  2. Write code to perform simple formatted output of integers, reals, strings and characters.
  3. Write code to read different kinds of data from the keyboard using the Scanner class: hasNextLine, nextLine, hasNext, next, nextInt, nextDouble, useDelimiter.
  4. Give examples of text and binary files and explain their differences.
  5. Write code to output to a text file instead than to the terminal, using the PrintWriter class. See how a PrintWriter is constructed, associated to an external file. Use on a PrintWriter the methods print, println, printf, as we did with System.out.
  6. Write code to input strings and other data from a text file, instead than from the keyboard, using the Scanner class. See that a Scanner has to be constructed on an existing file and used with the same methods that we used on System.in.
  7. Write code to use the Scanner class to obtain substrings and other data from a string.

G. EXCEPTION HANDLING

  1. Define what is an exception and understand the distinction between checked and unchecked exceptions.
  2. Write code that requires the use of the try..catch..finally statement, of the throws clause, and the throw statement.
  3. Write code that deals with the exceptions FileNotFoundException, IOException, NullPointerException, ArrayIndexOutOfBoundException, StringIndexOutOfBoundsException, InputMismatchException.
  4. Define and use a new exception class. For example define an exception to report that the user is unable/unwilling to enter a specific data value.

G. STATIC METHODS

  1. Explain the computational purpose of a static method, including the main method, in Java.
  2. Define the signature of a static method
  3. Identify the formal parameters in the signature of a static method.
  4. Show how a static method is called and how actual parameters correspond to the formal parameters.
  5. Identify the return type in the signature of a method and explain the use of the keyword void as a return type.
  6. Explain the principle of method overloading and identify two examples from the Java API where overloading occurs.
  7. Explain that parameters are passed by value and see what this means in the case that the parameter type is primitive and in the case that it is a reference type.

H. OBJECTS, INSTANCE METHODS, AND CLASSES

  1. Define as classes some common objects, for example, fractions, bank accounts, and DVDs.
  2. Understand the distinction between an idea/concept/prototype, and its instances. For example the distinction between the idea of a DVD and my "No Country for Old Men" DVD.
  3. Understand the state and behavior of a common everyday class of objects [e.g. a bank account].
  4. Define the terms: data field, constructor, accessor and mutator and identify examples of their use.
  5. Write data fields for a Java class to represent the state of a specific object.
  6. Define and implement classes that have static and instance data members and static and instance methods.
  7. Understand the role of the hidden parameter in the definition of instance methods and be able to give examples of its use.
  8. Repeat and apply to instance methods concepts encountered discussing static methods, such as signature, formal parameters, actual parameters, return value, parameter passing, overloading.
  9. Write code that uses the keyword this.
  10. Define and implement a number of constructors for a number of classes, including default and copy constructors.
  11. Define and implement the accessor methods for the fields for a class.
  12. Define and implement a number of mutator methods for a class.
  13. Implement the toString(), equals(), and clone() methods for at least a class.
  14. Create instances of a class in a separately compiled class, and invoke both instance and static methods from the separately compiled class.
  15. Examine the role of Object as the supremum of the Java class hierarchy.
  16. Understand the default implementations in the Object class of the equals and clone methods.
  17. Write for some classes implementations of toString, equals, and clone that overrides the corresponding methods inherited from the Object Class.
  18. Write code to experiment with deep vs. shallow equals and clone.

J. ALGORITHMS

  1. Write code to swap the content of two variables.
  2. Write the algorithm and then code the euclidean algorithm to compute the greatest common divisor of two numbers.
  3. Write the algorithm and then code algorithms that
  4. Write code to rotate the content of an array n positions to the right.
  5. Write code to traverse a one-dimensional array of numerical data to compute each of the following:
  6. Write code that traverses a one-dimensional array of object references using the compareTo method to compute each of the following:
  7. Write the algorithm and the code for the insertion sort algorithm for an array of integers and for an array of comparable object references.
  8. Write the algorithm and the code for the selection sort algorithm for an array of integers and for an array of comparable object references.
  9. Write the algorithm and the code for the linear search algorithm and the binary search algorithm.
  10. Write the algorithm and the code for the merge algorithm of arrays and files.
  11. Write the algorithm and the code to generate random permutations of n values.
  12. Write algorithms and code that use random number to solve mathematical problems, for example to compute PI and examine the birthday paradox.
  13. Understand how long an algorithm will take to complete its work. For example, understand that a linear search will take time proportional to the size on the input array, that a binary search will take proportional to the logarithm of the size of the input array, and that both selection and insertion sort will take time proportional to the square of the size of the input array.

K. CAREFUL SOFTWARE DEVELOPMENT

  1. Define the phases of software development [requirements, analysis, design, implementation, and testing] and give examples from your homeworks.
  2. Learn to develop programs carefully and gradually, using stubs [trivial initial implementations for complex methods] and drivers [code to test existing methods and classes].
  3. Write well indented, well spaced programs using a consistent style.
  4. Use meaningful names for variables, methods, classes.
  5. Be aware of the scope of each identifier, be it of a variable, a method, or a class.
  6. Learn to trace carefully by hand [or using a debugger] the execution of important portions of your programs.
  7. Use access attributes [public, protected, private] to control the visibility of names.
  8. Be aware of the role of packages and of the import statements, though you will write programs that exist in a single directory [package].
  9. Document your program by commenting each class, each method, each data field. Use other comments on variables, loops, computations as appropriate to facilitate comprehension by a reader.
  10. Have an understanding of the use of Javadoc [/**..*/, @param, @return]
  11. Understand different kinds of errors, syntax [ for example, x + 3 = y; ], semantic [ for example, "0123456".substring(1,3) is "123"], logical [for example, off-by-1 errors], pragmatic [for example, not reading integers and not taking into account the possibility of alphabetic data].
  12. Learn to correct compile-time errors [use line indication associated to the error message]and run-time errors [use information about cause and location of error from the stack trace of the error].
  13. Define preconditions and postconditions for the methods you write.
  14. Define some class invariant for at least some the classes you write.
  15. Define the loop invariant for many of the loops you write.
  16. Be able to make convincing arguments to show that your code does what it was intended to do.