CIS1068: PROGRAM DESIGN AND ABSTRACTION [Spring 2010]

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

• Office : Wachman Hall, Room 1038
• Phone : (215)204-6825
• E-Mail : giorgio@temple.edu
• Contact Hours : Tuesday and Thursday from 11:15am to 12:45pm, or by appointment, or take your chances and drop by.

• Tuesday and Thursday: 8:00am to 9:20am in Tuttleman 302

• Section 1: Wednesday from 10:00am to 11:50am in Wachman 104
• Section 3: Monday from 3:00pm to 4:50pm in Wachman 104

• Office : Wachman Room 1000M
• Phone : 215-204-3950
• E-Mail for homeworks: vmalbasa@gmail.com
• Help Homepage: www.vukmalbasa.com
• Contact Hours : Monday 3 to 5pm, Wednesday, Friday: 2 to 4 pm

• Office : Wachman Room 1000M
• Phone : 215-204-3950
• E-Mail for homeworks: vladan@ist.temple.edu
• Help Homepage: www.ist.temple.edu/~vladan/
• Contact Hours : Wednesday 12-1:30pm, Thursday 2 to 4pm

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

GRADING

• Weekly : 18% 10 minute tests: Eleven tests, given each week, only your top ten scores will count
• Midterm 1 : 10% Tuesday, February 16
• Midterm 2 : 12% Tuesday, March 23
• Final : 35% Common exam from 3:30 to 5:30pm on May 10
• Homeworks : 25%

EXAMS

HOMEWORKS

LABORATORIES

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
   • Compute the n-th power of a number
   • Determine if a number is a power of 2
   • Determine if a number is a prime
   • Determine the written representation of a number in various bases
   • Determine, given the written representation of a number in various bases, what is the corresponding number.
   • Print the first n Fibonacci numbers.
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:
   • the maximum value
   • the minimum value
   • index of the maximum value
   • index of the minimum value
   • the total sum
   • the average of all values
   • the count of the number of values that match a specific property [e.g. odd, positive, greater than some value, etc.]
6. Write code that traverses a one-dimensional array of object references using the compareTo method to compute each of the following:
   • the maximum object
   • the minimum object
   • index of the maximum object
   • index of the minimum object
   • the count of the number of objects that match a specific property based on given field(s).
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.