CS500 - Computer Science for CIT

Summer/2000

Classes: TR 05:30-09:15 p.m., 208 Maria Sanford Hall
Instructor: Dr. Zdravko Markov, MS 203, (860)-832-2711, http://www.cs.ccsu.edu/~markov/, e-mail: markovz@ccsu.edu
Office hours: MTWR 04:00-05:00 p.m., or by appointment

Description: This is a transition courses for students without Computer Science undergraduate degree. The course is designed to acquaint the students with the main ideas and techniques they need to know for taking the core courses in the CIT curriculum. The course consists of three parts. The first part is an introduction to computer architecture at the assembly language level. It is based on the MIPS processor, a simple clean RISC processor whose architecture is easy to learn and understand. The second part of the course discusses the fundamental concepts of programming through Java. This is the major part of the course where the basic programming structures and object-oriented methodology are studied. In the end of the course a short introduction to the Web and HTML is provided.

Textbook: John Lewis and William Loftus, Java Software Solutions, Second edition, Addison Wesley, 2000.

Recommended reading: John Waldron, Introduction to RISC Assembly Language Programming, Addison-Wesley, 1999.

Programming: The first part of the course teaches assembly programming on a SPIM simulator. This is a MIPS machine simulator available as a free software for Unix, DOS, and Windows. The second part of the course uses Java Development Kit, a software system for developing Java programs also available as a free software for various platforms and operating systems.

WEB resources:

Assignments and grading: There will be 4 programming assignments totaling 100 points. The letter grade will be calculated according to the following table:
 
A A- B+ B B- C+ C C- D+ D D- F
95-100 90-94 87-89 84-86 80-83 77-79 74-76 70-73 67-69 64-66 60-63 0-59

Tentative schedule of classes and assignments

  1. Computer organization and design - hardware software interface
  2. MIPS assembly programming
  3. Project 1 due. Object-oriented programming in Java.  Objects and primitive data. Read Chapter 2.
  4. Program structure: statements, control, loops. Read Chapter 3.
  5. More control structures: for loop, if-else, switch, use of boolean variables.
  6. Project 2 due. Writing classes. Read Chapter 4.
  7. Data structures: string decomposition and using the stack
  8. Project 3 due. Arrays, vectors and sorting. Read Chapter 6.
  9. Enhancing classes. Read Chapter 5.
  10. Project 4 due. The Web and HTML. Read Appendix J

CS500 - Class #1

Computer organization and design - hardware software interface

  1. Levels of abstraction in describing computers
  2. Levels of computer architecture in more depth
  3. Basic components of the computer
  4. Stored program concept: programs and data, fetch&execute cycle
  5. MIPS architecture (SPIM simulator)
  6. Representing instructions and data
  7. First MIPS program (Random.asm)

Exercises

  1. Write a program to calculate the average of three numbers entered by the user.
  2. Write a program to calculate the age of a person in years and months by using DOB and today's date both entered as two integers - month and year.

CS500 - Class #2

MIPS assembly programming

  1. Control flow structures - branches: leap year example (Leap.asm)
  2. Loops: Euclid's algorithm (Euclid.asm)

Exercises

  1. Write a program to print N random numbers, where N is entered by the user.
  2. Write a program to calculate the average of  N random numbers, where N is entered by the user.

CS500 - Class #3

Object-oriented programming in Java.  Objects and primitive data

  1. Objects and overall program structure (first program in Java)
  2. String concatenation and arithmetic addition (Addoperator.java)
  3. Numeric input, constants, variables, type conversions, casting (Celsius.java)
  4. Arithmetic expressions (Arithmetic.java)
  5. Using class methods, strings (Jumble.java)

Exercises

  1. Write a program to calculate the average of three numbers entered by the user.
  2. Write a program to calculate the age of a person in years and months by using DOB and today's date both entered as two integers - month and year.

CS500 - Class #4

Program structure: statements, control, loops

  1. Do-while loop (Dice.java)
  2. Applets (DiceApplet.java and Dice.html)
  3. While loop (Euclid-gcd.java). See an applet implementation of Euclid here.

Exercises

  1. Write a program that generates a random number and then asks the user to guess this number. The program reads the user input in a loop and prints whether the number entered is greater or less than the generated random number until the user guesses the number.
  2. Implement the version of the Euclid's algorithm based on subtraction. The basic idea is the following: to find the GCD of two numbers by this algorithm, repeatedly replace the larger by subtracting the smaller from it until the two numbers are equal. For example: 132, 168 -> 132, 36 -> 96, 36 -> 60, 36 -> 24, 36 -> 24, 12 -> 12, 12 so the GCD of 132 and 168 is 12. This implementation of GCD is based on the fact that gcd(a, b) = gcd(a-b, b).

CS500 - Class #5

More control structures: for loop, if-else, switch, use of boolean variables

  1. Monte Carlo algorithm for calculating Pi (Pi.java)
  2. Iterative approximation of Pi (iteration.java)
  3. Nested loops (primes.java). For more information about prime numbers see this link.
  4. Converting string to integer (str2int.java)
  5. Simple calculator (calc.java)

Exercises

  1. Use the digits.java program to prove experimentally that if the sum of the digits of a number is 9, then the number is multiple of 9 (what about the inverse?).
  2. Modify the str2int.java program to convert hexadecimal numbers to decimal. Add a loop to repeat the input if it is wrong.
  3. Include the str2int.java code into calc.java program to read and verify the numbers (to avoid the standard exception if a wrong argument is entered). Add a loop to repeat the calculator execution.

CS500 - Class #6

Writing classes

  1. Defining new classes (euclid.java) and using them (use_euclid.java). Parameter passing and returning values.
  2. Encapsulation, visibility modifiers (rational.java and use_rational.java).
  3. Using new objects as parameters (series.java).

Exercises

  1. Write a method for rational.java to read a rational number from the keyboard (read two integers - numerator and denominator). Modify use_rational.java to use this method.
  2. Write a class "student" that represents the student name and the names and grades for three courses he/she is taking. The class should provide the following methods:
    3. Write a class that creates 3 student objects and prints their class information and gpa's.

CS500 - Class #7

Data structures: string decomposition and using the stack

  1. String decomposition, StringTokenizer class (reverse.java).
  2. Using the stack: reverse1.java
  3. Printing the stack: mystack.java and reverse2.java
  4. Using a stack to evaluate postfix expressions: Reverse Polish calculator (polish.java)

Exercises

  1. Modify calc.java to work with expressions entered on a single line.
  2. Write a program that evaluates expressions of the following type: a/b + c/d or a/b - c/d (a, b, c, d and the result are floating point numbers). Use StringTokenizer class.

CS500 - Class #8

Arrays, vectors and sorting

  1. Arrays of primitive data: min, max, bubble sort (array.java).
  2. Initialization of arrays, searching arrays (index.java).
  3. Dynamic arrays (vectors): implementing a stack (vect.java).
  4. Arrays of objects, sorting strings, using a vector for sorting (online.java).

Exercises

  1. Write a program to translate a letter grade (A, A-, B+, ...) into a point grade (0-4).
  2. Use the bubble sort algorithm to sort strings. Use compareTo(String str) method.

CS500 - Class #9

Enhancing classes

  1. Objects and references: simple linked list of objects (List.java)
  2. List methods: list constructor, add, append, print (List1.java)
  3. Trees and recursion (Tree.java)
  4. Event programming, listeners, interfaces, polymorphism: creating an applet with text input and output (Gcd.java and Gcd.html)

Exercises

  1. Create a linked list of strings by an interactive input and print the list in normal and reverse order.
  2. Create and print the tree for the expression a * b + c - d / f
  3. Add input data validation to the Gcd applet.
  4. Add a label and a TextField for the applet output.

CS500 - Class #10

The Web and HTML

  1. A little history
  2. The client side
  3. The server side
  4. Writing Web pages in HTML
  5. Java
  6. Locating information on the Web

Project 1

Write a MIPS program to print the minimum, maximum and the average of N random numbers. N is an integer entered by the user. Use the code from Random.asm  to generate the random numbers.

Project 2

Write a program (application in Java) to calculate the sum of the series 1+1/2+1/3+...+1/n in rational numbers (i.e.
represented as fractions). The value of n is a parameter entered by the user. The following restrictions apply:
  1. The program must use integer arithmetic only.
  2. The sum of the series must be a rational number (fraction) in its canonical (reduced) form. For example if the sum is 50/24 it must be reduced to 25/12.
  3. The reduction to canonical form must be done by using the Euclid's algorithm.
Example: n=5, that is calculate 1+1/2+1/3+1/4+1/5. The program must do the following:
  1. Ask the user to enter the number of terms in the series.
  2. The user enters 5
  3. Calculate the sum of the fractions 1+1/2+1/3+1/4+1/5 = 274/120
  4. Use the Euclid's algorithm to find the GCD of 274 and 120 (which is 2).
  5. Simplify the fraction 274/120, i.e. 274/2 = 137 and 120/2 = 60
  6. Print 137/60

Project 3

Write a program "calculator", that works with rational numbers. Use a control structure similar to calc.java and for the calculations use the methods from rational.java. The calculator should accept the following operations: +, -, *, /. In addition operations for comparing rationals should be implemented (>, <, =) . These operations should produce a boolean result (true/false). All operations should be implemented as methods of the class rational.java.

Examples (the user input is in italics):

Numerator: 2
Denominator: 4
Operation: +
Numerator: 6
Denominator: 8
Result: 2/4 + 6/8 = 5/4

Numerator: 2
Denominator: 4
Operation: <
Numerator: 6
Denominator: 8
Result: 2/4 < 6/8 = true

Extra credit: Implement single line input for each rational number and a new operation called ? (to check for <, > or =). Example:
2/4
?
6/9
Result: 2/4 < 6/8

Project 4

Write a program that creates an array of objects of class "student" (Class #6, Exercise #2) and then prints the information for all students (by using get_info() method) sorted by student's name (lexicographic order) and by student's gpa (greatest first). Use the bubble sort method for sorting. Two version of this program are acceptable:

Version 1 (maximum 80 pts. out of 100): Create an array of 5 students directly in the program by using constants for the student constructor method. For example: st[0] = new student("John Smith", "CS500", "A-", "IT501","C+", "CS501","B"); Then print the sorted array by student name.

Version 2 (maximum 100 pts. out of 100): Implement a loop to enter the student information interactively, i.e. implement commands for adding a student and print the list of all students sorted by name and by gpa.

Example of Version 2: student.java and use_student.java implemented by Salahuddin Akand.