CS 10051-003/004 Introduction to Computer Science - Spring 2008

Exam 2 Study Guide - Exam is on Wednesday, March 12, 2008

Chapter 3:

• Algorithm attributes
  • correctness
  • ease of understanding
  • elegance
  • efficiency
• Benchmarking

Measuring efficiency

• Sequential search algorithm
• Order of magnitude O(n)
• Selection Sort algorithm
• Order of magnitude O(n²)

Data Cleanup Algorithms*

• Shuffle-Left
• Copy-Over
• Converging Pointers
• Figure 3.17 - Algorithm analysis of data cleanup algorithms

Binary Search

•  Binary tree
• Order of magnitude O(log n)

When things get out of hand

• Polynomially bounded vs. exponential algorithm
• approximation algorithms (heuristics)

Chapter 4:

• Binary numbers / base 2 representation
• Sign / magnitude notation
• Fractional numbers (sign, mantissa, exponent)
• ASCII / Unicode
• Multimedia storage (pixels)
• Boolean logic
  • Truth tables
  • Gates (AND, OR, NOT)
  • Combinational circuits
  • Sum-of-products algorithm (building circuits)
  • Control circuits (decoder, multiplexor)

Chapter 5:

• Abstraction
• Memory and Cache
  • memory size compared to address space
  • address space (n bits of address, 2ⁿ memory locations)
  • MAR / MDR
  • Fetch / Store processes
  • memory organization (2-D with decoders)
  • Principle of Locality
• I/O and Mass Storage
  • direct vs. sequential access
  • volatile, non-volatile  storage
  • I/O controller (buffer, control logic)
• ALU (Arithmetic / Logic Unit)
  • register designators (names)
  • path and bus
  • Multiplexor
  • Machine language instructions --> Op code and address field(s)
  • Types of machine language instructions (data transfer, arithmetic, comparison, branch)
  • PC, IR, Instruction decoder
  • Fetch / decode /execute cycles on Von Neumann computers
• Parallel Computing
  • SIMD
  • Associative Computing
  • MIMD
  • Quantum computing

Last Updated: Friday, March 7, 2008