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(n²), O(n³), O(2ⁿ), 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 T_EX by T_TH, version 3.74.
On 29 Apr 2008, 09:33.