Transcript Computer Science Fundamentals

Computer Science Fundamentals
A topics course in Computer Science
Topics we hope to cover
•
•
•
•
•
•
•
•
•
Data representation (especially binary and hex), arithmetic, base change
algorithms
Operating systems (including an introduction to Threads of execution)
Boolean algebra and switching functions
Combinational and flip-flop circuitry (an introduction to architecture)
Computer communication (an introduction to sockets and/or datagrams)
Theory of computation (an introduction to automata and computability)
Assembly language programming
Program translation
We’ll also learn some java programming!
Data representation
• Information in the computer is represented in base 2 (binary),
although, for convenience, base 16 is also sometimes used.
• In radix positional notation, a digit d, located in position p, in a number
base b, represents d*bp. So, the decimal value 8352 represents
8*(1000)+3*(100)+5*(10)+2*1. Similarly, the binary value 1011101
represents the value 1*64+0*32+1*16+1*8+1*4+0*2+1*1.
• Note that the powers base 2 are 1,2,4,8,16,32,… 20=1, 21=2, etc.
Make sure you are familiar with the two-powers.
You will need to memorize the values 0..15 in binary and hex
Decimal
Binary
decimal
binary
hex
8
1000
8
0
0
1
1
9
1001
9
2
10
10
1010
A
3
11
11
1011
B
4
100
12
1100
C
5
101
13
1101
D
14
1110
E
15
1111
F
6
7
110
111
Kinds of data
• There are many types of data stored in
computer memory. Some memory cells
hold instructions, some hold integers, some
hold float values, some hold char data, other
store composite data types.
Char data is stored internally using the ASCII
(or UNICODE) collating sequence
• You can find a complete ASCII table in most
computer texts.
• Exercise: In C++ or Java, print your own ASCII
table: print the int value x = 32…255 in the left
column of a table and print (char)(x) in the right
column.
• You will need to know the collating sequence
values for some characters like ‘0’, ‘1’, … also
‘a’,’b’, … and ‘A’, ‘B’, …
• Exercise: write these values in binary.
Int data
• Integers may be stored internally in one of
several formats:
• BCD (binary coded decimal) often used in
spreadsheet programs
• Unsigned int: a positive binary value
• Signed int: positive or negative value
BCD
• BCD allocates 4 bits (a nibble) of binary
storage for each decimal digit to be
represented.
• Example: 598 in decimal will require
3digits*4bits each =12 bits. In BCD it
looks like this: 010110011000
• Practice converting a few decimals to BCD
Unsigned ints
• In unsigned (positive) representations, all bits are
used to indicate the value.
• In 4 bits of binary, you can represent decimal
values 0,…,15. (see table a few slides back.)
What values could be represented in 5 bits? In 8
bits? In 16 bits?
• What is the general rule?
• Represent values 0, 48, 65, 97, and 127 in 8 bits.
Example: 48 decimal is 00110000 in 8 binary bits.
• 8 bits is called a byte.
Quick conversion between bases:
From base b to decimal
• To convert from any base to decimal, use Horner’s
algorithm for polynomial evaluation. A number in base b
can be regarded as a polynomial p in the variable b. Let
P(b)= anbn + a n-1 b n-1+…+a1b1+a0b0
• This would be written as the series of (coefficient) digits.
For example, the base 6 value 32501 represents
3*(64)+2*(63)+5*(62)+0*(61)+1*(60)
• Using nested multiplication we can rewrite this without
needing to compute exponentials of the base:
((((3*6)+2)*6+5)*6+0)*6+1
Base b to decimal via Horner
• If a value in a base b is entered as a String in a TextField
named input, and the base is entered in a TextField called
basefield, we could use the following Java code to do the
conversion:
•
•
•
•
•
•
•
String value;
int b, answer;
answer=0;
b=Integer.parseInt(basefield.getText());
value=input.getText();
for(int j=0;j<value.length();j++)
answer = answer*base+ (int) (value.charAt(j)-48);
Remarks on this code & exercises
• Note that the length of a String in Java can be obtained
using the class method length(). The String method
charAt(p) returns the char in position of a String. The
TextField method getText() returns the String entered into
a TextField.
• For which bases would the java code fragment not provide
the correct answer? Why?
• Fix this problem.
• Complete the JApplet. Write a JApplet which provides
labels and textfields for a base, a value and an answer and
performs the conversion from base b to base 10.
Converting from decimal to other bases
• In determining what a decimal value would look like if
represented in another base (b), we need to figure out what
digit in base b goes in each position of the representation.
• Suppose n=295 and b=2, ie., we are trying to convert to
binary. The 1s place will have a 1 in it since 295 is odd.
• 295 (10) == ???..??1(2)
• But how many other bits are there, and what are each of
their values? Since positions in the binary representation
indicate powers of two, having figured out the ones place
means we have only half of n (295/2= 147) left to
represent.
Example: convert 295 decimal to binary
•
•
•
295 is odd…least significant bit is a 1: 295(10) = ???..?1(2)
295/2= 147. Since 147 is odd, 2s bit is also a 1: 295(10) = ???..?11(2)
147/2 =73. Since this is odd, next bit is also a 1: 295(10) = ???..111(2)
•
73/2=36. Even, so next bit is a zero: 295(10) = ???..0111(2)
•
36/2=18, which is even. 295(10) = ???…00111(2)
•
18/2=9, odd. 295(10) = ???100111(2)
•
9/2=4 even. ??0100111(2)
•
4/2=2 even. ?00100111(2)
•
•
2/2=1 0dd. 100100111(2)
½=0 stop.
Decimal to any other base
• Convert from decimal to any base using the
remainder/division algorithm described previously. Each
remainder operation generates one digit of the answer.
Then divide the number by the base and continue.
• String answer=””;
• int base =Integer.parseInt(basefield.getText());
• int value = Integer.parseInt(input.getText());
• while (value!=0){
• answer= value%base+answer;
• value/=base;}
Remarks & Exercises
• Note, we use the static Integer method parseInt() to convert a String to
an int value.
• For what input values would this Java code not work properly? Why?
• Can you fix this problem to convert decimal values into values in any
other base?
• Write the JApplet which would provide labels, textfields and buttons
enabling the user to enter a decimal int and a new base value and
convert the decimal int to the new base.
• Practice doing these conversions by hand.
Base conversions: base b to base bn
• If you are converting between bases where one base is a power of the
other, like binary to hex, or binary to octal, or base 3 to base 9 then the
conversion may be done very easily. n digits of base b will be needed
for each 1 digit of base bn .
• Consider converting A6E9 in base 16 to binary. Each hex digit will
generate 4 binary bits. If you have not memorized your hex digits yet,
this is a good time to start. In decimal A is 10, B is 11, C is 12, …F is
15. So A= 1010(2), etc.
• A6E9 (16) = 1010011011101001 (2)
• Convert this number (right hand side above) to base 8 and base 4.
• Convert the base 9 value 783361 to base 3.
An introduction to Java
• Java syntax is the same as C++. In other words, an assignment
statement, an if, a while, or a for statement in Java looks the same as in
C++.
• Java class methods are called, like in C++, using the dot ‘.’ operator:
• ClassInstance.methodName(parameters);
• To get a String which a user has entered into a TextField named input
we might use the code:
• String value= input.getText();//getText is a TextField method
• Java methods (functions) have return types, parameters, and their
definitions are enclosed in a block {}, like in C++ programming.
Prototypes are not used in Java.
An introduction to Java
•
•
•
•
•
•
•
•
•
•
Java provides components (classes) buttons, textfields, and labels, among
many others. These three are called JTextField, JLabel, and JButton in Java
1.2 and higher. These classes must be instantiated with “new”. Example:
JButton b=new JButton(“press me”);
In a small program, declarations are typically global (not inside a method) and
data allocation occurs in the JApplet method init(). The init method is
executed when a browser loads an applet.
All java applets and applications must consist of an outer class:
//sample Java JApplet
import javax.swing.*; //contains Java2 classes
public class OuterClass extends JApplet
{//open block
//methods, declarations go in here
}//close outer block
JApplet with JLabel, JTextField and JButton
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
import javax.swing.*;
public class OuterClass extends JApplet
{//global applet declarations typically go here:
public JLabel label;
public JTextField text;
public JButton button;
public void init(){//first method browser will execute
Container c=getContentPane();//get the panel for this applet
c.setLayout(new FlowLayout());//one sort of layout
button=new JButton(“press me”);
label =new JLabel (“enter value”);
text=new JTextField(20);
c.add(label);//components appear in the order they were added to the panel
c.add(text);
c.add(button);
}//end init
}//end applet
JApplet structure
• Note that imports appear the top of a java Applet. These are like
includes in C++.
• Applets may have many user defined methods.
• They may also override the Applet methods init(), paint(), start(),
stop(), and many others.
• A Java applet or an application must consist of an outer class (with a
block) and any data fields, and methods (with their blocks) defined
inside the outer block.
Applet deployment
•
1.
2.
3.
4.
We must perform a number of steps in order to deploy an applet to our
webspace so a visitor there could run it.
Type the code into an editor or IDE
Compile the .java file. This process will check syntax. If it is successful, a
.class file will be created which has the same name as the original java
source file. Ie. Prog.java when compiled with generate a file called
prog.class. Create an appropriate html file to point a browser to your class
file.
Check things out on your desktop by running the applet in appletviewer.
Use FTP to send appropriate html and class files to your webspace
Using an editor
Type the java source code into an editor or IDE (integrated development
environment like JBuilder) and save it as a .java file.
The filename must be the same as the outerclass name.
We will use TextPad, a shareware program, as our editing environment, although
you can also use the Borland C++ editor or Word. (If you use MS Word,
make sure the file is saved as ASCII text format and has the extension .java)
TextPad can be downloaded on your own computer. It is produced by Helios.com
TextPad has some features of an IDE: you can compile and run java applets and
applications from TextPad.
TextPad is available in the campus labs.
Compile the .java file.
•
This process will check syntax. If it is successful, a .class file will be created which
has the same name as the original java source file. Ie. Prog.java when compiled with
generate a file called Prog.class.
Java is case sensitive.
•
Compile in TextPad by selecting compile from the tools menu.
•
•
Alternative. If you’ve downloaded JDK1.3.X onto your own computer, you have
java, the java compiler as part of the kit. Open a DOS window (run
command.com)and navigate to your jdk bin directory where you should have saved
your .java file. At the prompt, type: java Prog.java
This will create a file called Prog.class.
A class file is not an executable, it contains portable byte-code. It requires a java
interpreter (named java) to be executed.
Create an appropriate html file to point a browser to
your class file
•
•
•
•
•
•
Sample html:
<html>
<applet code =”Prog.class” height=300 width=500>
</applet>
</html>
This must be typed into a file and saved with the .html extension. You
could call this file Prog.html to make it easier to remember which
applet it pointed to.
A possible problem with the html and current
browser versions (IE & Netscape)
• Depending on what browser you use, and its version, it may require a
plugin to run java2. The html file will then need to be modified to tell
the browser to go load the plug in. Campus labs have the plugin
already downloaded.
• There should also be a java program called HTMLConverter you can
use to convert the html file we created into a more complicated one
that tells the browser it needs to load a plugin to run the applet.
• My class page has examples of this converted html file format – you
can cut and paste from the examples there to create a new html.
• See class notes about this topic.
Check things out on your desktop by running the
applet in appletviewer
• If you can get into DOS (on your own computer) and have
downloaded the jdk you can use the simple html file format I presented
earlier to check whether your applet works now.
• Assuming you have an applet called Prog.java, a class file named
Prog.class and an html file named Prog.html, navigate to the bin
directory and type: appletviewer Prog.html
• appletviewer is a program in the jdk which will run your applet as a
browser would, so you can check if it works ok.
• Textpad is also configured to run appletviewer in the labs. If you’ve
created an html file for your applet, select appletviewer from the
textpad tool menu. You may need to have saved these files in
particular directories, like the java/bin directory, for this to work
properly in the labs. See class notes on this.
Use FTP to send appropriate html and class files to
your webspace
• I have a screen shot of how to configure your WinFTP session to ship
files to your webspace on our class pages.
• Make sure to send .class files as type binary. Later, you’ll use binary
type for jpg and wav files also.
• HTML can be sent as ascii.
• Type your applet url into the browser to go visit your applet. It will be
something like
• http://www.webserver2/students/smitxy87/Prog.html
An applet with a listener
• Applets are event-driven programs. This means things happen when
the user click buttons, moves the mouse, or enters values into fields.
• It is up to the programmer to insure the applet listens for button clicks
(or whatever) and does what needs to be done if a button is clicked.
• This is done by means of listeners in Java. There are many (!)
listeners. One of the simplest is the one which checks if values have
been entered into textfields or if a button is clicked. It is called
ActionListener.
• Listeners are types of interfaces. A java applet or application program
may use many interfaces.
Implementing the ActionListener
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
import javax.swing.*;
public class OuterClass extends Japplet implements ActionListener
{//global applet declarations typically go here:
public JLabel label;
public JTextField text1, text2;
public JButton button;
public void init(){//first method browser will execute
Container c=getContentPane();//get the panel for this applet
c.setLayout(new FlowLayout());//one sort of layout
button=new JButton(“press me”);
label =new JLabel (“enter value”);
text1=new JTextField(20);
Text2=new JTextField(20);
c.add(label);//components appear in the order they were added to the panel
c.add(text1); c.add(text2);
button.addActionListener(this);//button is listening now for user to press it
c.add(button);
}//end init
//see next slide!
ActionListener interface requires the programmer to
define the method actionPerformed(…)
• The above applet is not complete. It is missing the outer close block,
but even so, will not compile without the definition of the method
actionPerformed which tells the aplet what to do if the button is
pressed.
•
•
•
•
•
•
•
public void actionPerformed(ActionEvent x){
int z= Integer.parseInt(text1.getText());//get int entered by user
int p =2*z;// do elaborate computations
text2.setText(“”+p);
//when button is clicked, 2*input value is calculated and displayed
}//end actionPerformed
}//end outer class