This page can be found at http://www.cs.duke.edu/courses/spring07/cps001/class/10_LastDay/final_topics.html.
The final exam will be open book, open note. That format does not mean that you do
not need to study diligently for this exam. The exam aims to test your general
understanding of the topics in this course and your ability to apply
the techniques you have learned to new problems.
The reading covered by the final will be:
- Great Ideas: Chapters 1-5, 8, 10-13, 15
- Computer Science: n Overview: Chapters 0-5, 11
- Introduction to Computing and Programming in Java: Chapters 8-10
- All course readings on Blackboard
Helpful Links
Topics since Midterm
Java Programming
- 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
- Audio
- Sound and SoundSample classes
- Amplitude vs. frequency
- Increasing and decreasing volume'
- Clipping and splicing Sound objects
- Recursion
- Factorial (N!)
- Iterative Approach for Factorial
- Towers of Hanoi
- Graphics (Lab 9)
- GDemo 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)
Debate topics
- Digital Divide: technologies for access and how to support them
- Journalism & Blogging: how the Internet enables many publishers
and a lot more "Letters to the Editor"
- Biometrics: an ID that never goes away
- Network neutrality: who wants tiered service?
- Data mining: the base rate fallacy and how technology may or may not
be affected the 4th amendment
Digital Intellectual Property
- What changes when using digital media vs. analog media
- Copyright
- Software patents, pros and cons
- Trademarks and trade secrets
- Software licenses
- EULAs
- Public domain
- Free vs. open source
- Closed software
- How licensing can affect development
Machine Architecture
- Hardware / Software
- Basic Computer very primitive
- Architectural Features
- Memory hierarchy
- CPU
- von Neumann architecture
- Fetch-Decode-Execute Cycle
- Low-level Machine System
- Levels of a Computer System
- Logic/Truth Tables: AND, OR
- Binary Numbers
- Conversion to and from Decimal
- Binary Addition & Subtraction
- Computer Technology
- Some Fundamental Limitations
- Other Important Concerns
- Economics, Noise, Lifetime (mean time to failure), Space
Computer Security
- The 5 principles
- Confidentiality
- Integrity
- Authentication
- Authorization
- Non-repudiation
- Information security services
- Confidentiality
- Integrity
- Availability
- "Analog" cryptography
- 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
- Private Key Encryption
- Public Key Encryption; RSA Encryption
- Primes and Factoring
- Breaking the Code: Factoring
- Digital Signatures
- The Strong Encryption Trap
Operating systems
- The layer between software and 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
- Software Environments
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
- Polynomial = Tractable
- Linear Time Algorithms
- Quadratic Time Algorithms
- Binary Search
- Intractable Algorithms
- 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
- What Does It All Mean?