CSCI 170 (GOLDWEBER)
Spring 08: 4/29/08
Study Guide #2
All web pages associated with the course.
All readings distributed in class.
- Definitions (Know them and know why they are important):
- Abstraction
- Computer and computing agent
- Computer Science (Algorithmics)
- Algorithm
- Natural language, formal language, pseudocode
- Big-Oh
- Preconditions and Postconditions
- Dissecting and Creating Algorithms:
- Attributes of Algorithms: Correctness, Ease of understanding, Elegance, Efficiency
- Algorithm Building Blocks: Assignment (and variables), Selection, Iteration, Input/Output, Arithmetic, Relational Expressions
(Turing Completeness)
- Finding flaws in poorly written algorithms.
- Creating algorithms (in Python, for Karel, or for the Simple Computer)
- Algorithms We Have Met (and Love):
- Examine-All algorithms: e.g. finding the largest, smallest, median, and selection sort
- All-pairs algorithms: e.g. Sums to x
- Divide-and-Conquer: e.g. Binary Search
- Sorting: Selection Sort and Insertion Sort
- Searching: Sequential Search, Short Sequential Search, and Binary Search
- Σi (Summing the numbers from 1 to n.)
- Finding perfect numbers
- Traveling Salesperson Route (The "Spring break Tour")
- The Simple Computer
- Circuits and Hardware:
- Positional number systems: e.g. binary
- Data representations: unsigned integers, sign-magnitude, two's complement, characters, colors, etc.
- Boolean logic and Truth Tables
- Bi-stable electrical devices and Transistors
- Basic gates, circuits, and the Sum of Products circuit construction algorithm.
- The Von Neumann model of a computer: the basic components (CPU, RAM, Bus, etc.)
- The fetch-decode-execute cycle
- Non-volatile storage: disk, CD, etc.
- The "Big Picture"
- Understanding the layers of abstraction: bi-stable electrical devices (transistors) - gates (AND, OR, NOT) - circuits (adders, multiplexors, decoders, storage bits) - components (CPU, memory, etc) - a complete though simple computer architecture (Simple Computer).
- Programming these abstractions: Programming the architecture directly with assembly language (Simple computer programming) - high-level programming languages (Python) - abstract graphical programming environments (Karel)
- Analysis of Algorithms:
- "Orders of Magnitude" (Big-Oh)
- Big-Oh values we have seen: O(1), O(lgn), O(n), O(nlgn), O(n2), O(n3), O(2n), O(n!)
- Algorithm comparison: Given two algorithms for the same problem, compare their respective execution times.
- Feasible (tractable) problems vs intractable problems vs. unsolvable problems.
- Known intractable problems and NP-Complete problems.
- Monty Karel the Robot
- Understand Karel's (rurple) basic operation.
- Inheritance: creating a new class based on an existing class.
- "Top-down" program design and "Bottom-up" implementation strategies.
File translated from
TEX
by
TTH,
version 3.74.
On 29 Apr 2008, 09:33.