TOPICS The Internet HTML Tags References Ethernets and routing The Web Connecting multiple computers by passing through different networks Programming in Java Java as a programming language "Java is a simple, object-oriented, distributes, interpreted, robust, secure, architecture-neutral, portablem high-performance, multi-threaded, and dynamic language." Basics Applets HTML tags for applets Compiling and executing applets Necessary Java syntax import init and actionPerformed methods Statements Syntax (ending with semicolons) Compound statements (delimited by curly braces {}) Variables and assignment Declaring variables ; int num; Primitive datatypes int, double, char, boolean Objects String, Button, TextField, DoubleField, ActionEvent Button b; b = new Button("Push Me"); Decision Trees Drawing decision trees Question: Draw decision tree from paper, rock, scissors game from lab? Question: What would the first few layers of the number guessing game decision tree look like? Logical statements and operators ==, <, >, ... Numeric Computation Datatypes Operations int +,-,*,/,% double +,-,*,/ Text Manipulation Strings String constants "Hello World" Manipulating methods int length() String substring(int start, int end) indexOf(String s) Subroutines/Methods declaring methods return type (void, int, etc) and values public int doSomething() { ... } arguments public int doSomethingWithArg(int num) { if (num == 1) ... } Loops/Iteration While loops Loop counters Arrays Declaring arrays []; int nums[]; Allocating arrays = new []; nums = new int[10]; setting array elements [] = ; nums[3] = 4 + 4; accessing array elements [] x = nums[3]; Array bounds errors arrays indices go from 0 to size-1 Your applet will crash (stop) if you go beyond those bounds nums[10] = 4; nums[-2] = 3; TwelveDays questions: Add code so that it puts in "and" before "A Partidge in a Pear Tree" Add code that adds an extra field and extra button to start on other days besides the first day. Grammars Used to determine the validity of statements Top-down approach Start from abstract (e.g. ) and work down to actual syntax (e.g. num = num + 1;) Bottom-up approach Question: Does more than one parsing exist for a particular statement? Should the bottom up and top down approaches yield the same applications of rules (in reverse order)? Top-Down Programming, Subroutines, and a Database Application Getting Information In and Out of Functions Class Data; Known within class. Formal Parameters/Arguments Syntax: Using a Function Functions that Return Values Syntax: Defining a Function Larger Problems: How to Deal with the Complexity Divide and Conquer Design: Stepwise Refinement Top-Down Implementation "Parallel" Arrays or "Corresponding" Arrays Model Phone Book Capability Typical Access by Name Access by other Fields (other arrays) Extend Idea to Database Basic Data Base Functions Wild Card Retrieval Used Car Database Relational Data Bases Recursion Factorial (N!) Iterative Approach for Factorial Towers of Hanoi Graphics, Classes, and Objects A Touch of Graphics (By Example) Basic Stuff Canvas class, Graphics class, pixels, Coordinates Graphics Methods void drawLine(int x1, int y1, int x2, int y2) void drawRect(int x, int y, int width, int height) void drawOval(int x, int y, int width, int height) void setColor(Color c) Example: Using Recursion: Serpinsky.java Go Through Design Process Speed of Display: Slowing it Down Machine Architecture Hardware / Software Basic Computer very primitive Architectural Features Memory CPU: INPUT, OUTPUT, BUS, Memory Low-level Machine System Levels of a Computer System Logic/Truth Tables: AND, OR Logical (Boolean) Expression Arbitrary Truth table for f(x,y,z) Binary Numbers Conversion to and from Decimal Binary Addition Truth Tables Computer Technology Some Fundamental Limitations speed of light, heat dissipations, capacitance and inductance Other Important Concerns Economics !!!, Noise, Lifetime (mean time to failure), Space CPUs in Everything Computer Security Passwords and Cracking Brief Case Combination Locks: Briefcase combination lock Analysis Password on a Computer Dictionary Attacks Encryption Polyalphabetic Substitution Cypher Reuse: Bad One Time Pads: Unbreakable The Key Exchange Problem Public Key Encryption; RSA Encryption Primes and Factoring Going Through the RSA Example Breaking the Code: Factoring Digital Signatures Virtual Environments for Computing The Problem: The Raw Machine Provides a Hostile Environment What Does an Operating System Do? Processor Management (Multiprogramming) I/O Systems Memory Management Software Environments Memory Management Memory Hierarchies, Paging, Protection I/O Systems Files Systems, Communications/Networking Graphical User Interfaces (GUI) Software Environments Client server, X-server Program Execution Time/Algorithms On the Limitations of Computer Science 1. runs too long. 2. Non-computable. 3. Don't know the algorithm Time Complexity, N Study of a Sorting Algorithm: Selection Sort: N^2 Polynomial = Tractable Linear Time Algorithms Cubic Time Algorithms Quicksort: t = A * N * log(N) Binary Search Intractable Algorithms Chess Traveling Salesperson Towers of Hanoi Exponential = Intractable More hardware not always the answer! Noncomputability Certain Problems Not Amenable to Computer Solution Existence of Noncomputable Functions Approach: Matching up Programs and Functions Have: Uncountable Infinity of Functions (cannot be put into a row) All Programs Can be Ordered Try to Draw Lines Between Functions and Programs Programs that Read Programs Artificial Intelligence The Human Brain is complex! Try to make systems that perform some tasks as well as humans Agent: something that perceives and acts Reflex agent: maps percepts directly to actions Agent with state: uses internal model of how world evolves to make better decisions Goal-oriented agent: choose actions that lead toward goal Utility-based agent: choose actions that maximize future expected happiness Computer vision: using image information to determine what is in a scene Graphics Take some internal model of a scene and depict that on screen Can be used to simulate environments that might not even exist Has greatly changed the entertainment industry