CPS 1 - Spring, 2000 - Ramm 4/24/00 #40
- Announce
- Final: Thursday, May 4, 7:00pm, HERE
- Review on Wednesday
R E V I E W
- 4.Top-Down Programming, Subroutines, and a Database Application
- Functions using Functions
- 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
- Exponentiation (X^N)
- Church-Markov-Turing Thesis
- This part of Java lets you solve all kinds of algorithms
- Chapt 5: 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
- 5. Simulation
- Simulation: Motivation
- Optimization, Simulation: Biggest Dog Lot
- How Could We Autmoate Process?
- Other Roles For Simulations
- Economy, Policy (e.g. birth control), Marketing
- Camera Lenses, UNC CS Walkthrough, Virtual Reality
- Simulation in Microelectronics
- Logic, Layout, Circuit, Process
- Design and Manufacturing
- 6. Software Engineering
- Engineering a Program - Programming in the Large
- What is Good Software?
- Program Life Cycle, Feedback Cycles
- Understanding Problem / Specifications
- Debugging
- Correctness, Proofs?
- Documentation
- Testing
- Bottom Line: Productivity: 15 LINES OF CODE/DAY
- Many People
- The "Committee", Communication, Interaction
- Organizational Schemes
- Programming Tools (CASE)
- Chapter 8. Machine Architecture
- Hardware / Software
- Basic Computer very primitive
- Architectural Features
- Memory
- CPU: AX, IP, IR, CF
- Fetch/Execute Cycles
- Need to handle IF and WHILE situations
- Tracing (often the only way to understand)
- Loop Example
- Factorial Example (Iterative)
- Writing a Program from Scratch
- Handling Lists or Arrays (Self Modifying Code)
- Fancier Architecture
- 9. Language Translation
- Importance of language:
- Goal
- Translate Java To Assembler
- "Meaning"
- Revise Syntactic Production Rules (seen before)
- Use Rules to Modify Strings
- Add Semantic Components to our Rules
- Use Syntactic Derivation to Generate Semantic Rules; Use Semantic
rules to Generate Code
- Rules for Looping
- Cleanup Translation
- Important: Everything done by simple substitution
- Everything "adds up"
- For Maximal Learning, Do Examples by Hand
- 6. Electric Circuits
- Levels of a Computer System
- Circuits: Water Model
- Circuits: the real thing = electrons
- battery, generators, heat -> light, motors
- Circuits With Switches (e.g. knife switch)
- Logic/Truth Tables: AND, OR
- Implementing Logic with Switches
- Logical (Boolean) Expression
- Equivalence of:
- Circuit with Switches, Truth Tables, Boolean Expression
- Arbitrary Truth table for f(x,y,z)
- Relays
- Storing Information: Latch
- Binary Numbers
- Conversion to and from Decimal
- Binary Addition
- Truth Tables
- Block Diagram, Simple Adder Circuit, Decoding/Control
- How to mark Quizzes
- Computer Technology
- Some Fundamental Limitations
- speed of light, heat dissipations, capacitance and inductance
- Other Important Concerns
- Economics !!!, Noise, Lifetime (mtf), Space
- Problems with Relay Computers
- Vacuum Tube
- Problems with Vacuum Tube Computers
- Transistor
- Integrated Circuits -- VLSI
- Economics of Silicon (Micro-electronics)
- CPUs in Everything
- 11. Computer Communications
- Computer Communications is one of the Great Ideas
- Modes of Communications
- Like Most of Computing: Layers upon Layers
- Basic Communications: In binary
- Connection Mode
- Circuit Switched, Message Switched, Packet Switched
- TCP/IP
- Ethernet (Bus Example)
- Internet -- a network of LANs that are interconnected
- Packets -- the currency of the Internet
- The Layers
- The Physical Layer, The IP (Internet Protocol) Layer
- The TCP (Task Control Protocol) Layer, The Application Layer
- Packets Within Packets
- Reliability
- Addressing (Layers Again!)
- Hardware Address (Ethernet Address)
- IP Address
- Domain Name (address)
- Applications
- email, news, talk, ftp
- telnet, ssh, rlogin
- irc
- information services: WWW, Older: gopher, WAIS
- Client/Server
- Print Server, File Server, Name Server,
- WWW
- 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
- Other Attacks (Buzz Words)
- Many Leave No Trace
- Password Hacking, IP Spoofing, Replay Attack
- Man in the Middle, Denial of Service
- Whom Can You Trust?
- Viruses, Trapdoors, Trojan Horses, Common Sense
- The Strong Encryption Trap
- 10. Virtual Environments for Computing
- The Problem: The Raw Machine Provides a Hostile Environment
- Early Years Had Major Theme: CPU Time Precious
- Later Years: Cheaper and Cheaper Hardware
- 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)
- Processor Management
- True Parallel Processes vs Simulated
- Synchronization: Race condition, Deadlock
- Software Environments
- 12. Program Execution Time
- 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!
13. Parallel Computation
- Limitation on Processor Speed
- Speed of Light
- Manufacturing Problems with Small Sizes
- Ultimately Parallelism is Only Hope
- Forms of Parallelism
- Word Size, Pipe Line, Multiprocessors
- Networks of Processors, Internet
Chapter 14. 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
- Solving the Halting Problem
- Proofs by Contradiction (Indirect Proof)
- Proving non-computability
- Assume Existence of Function
halt:
- Use in way resulting in Paradox!
- Therefore
halt cannot exist!
- What Does It All Mean?