Contents

 
• Course Information
  • Course Guidelines
    • Grading
    • Lateness Policy
  • Homework Guidelines
    • How To Approach the Assignments
    • Written Exercises
    • Coding Guidelines
• Weiss Chapter 2 Notes
  • Definitions
    • Big-O Conventions
    • Why Not Use All The Time?
  • Finding the Big-O of a Function
    • The Dominance of Functions
    • Properties of Orders
  • Big-O Notation and Algorithm Analysis
    • The Size of a Problem
    • What Does It All Mean?
• Sparse Arrays
  • A Troublesome Property of C Arrays
  • Linked List Representation
    • Extremely Sparse Arrays
  • An Implementation
    • An Optimization: Taking Advantage of Order
    • Cursors
  • How Space-Efficient Are Sparse Arrays?
  • A Note About Software Engineering
  • Exercises
• Matrix Operations
  • Terms and Definitions
  • Matrix Addition and Multiplication
    • Addition
    • Multiplication
  • Faster Matrix Multiplication Algorithms
  • Operations on Sparse Matrices
    • Multiplying Sparse Matrices
    • Another Note About Software Engineering
    • Other Sparse Matrices
  • Exercises
• Tries
  • Tries as an Abstract Data Type
  • Tries as a Data Structure
  • Implementing Tries
  • Reducing Memory Requirements: Eliminating Nodes
    • Special Case: Leaf Nodes
    • Patricia Tries
  • Reducing Memory Requirements: Smaller Nodes
  • More Trie Operations
  • Exercises
• I/O of Data Structures
  • An Introduction
    • A Word of Advice
  • Arrays
    • Arrays of Fixed Size
    • Arrays of Unknown Extent
    • Arrays of Unknown Dimension
    • Arrays of Unknown Type
    • Data Definition Languages
  • Strings and String Fields
    • Delimited Strings
    • Escaped Strings
    • Annotated Strings
  • Binary Trees
    • Binary Search Trees
      • Choosing a Traversal
    • Unordered Binary Trees
      • An Explicit Reconstruction
      • An Implicit Representation
      • Adding Inorder Keys
  • Exercises
• The Monte Carlo Method
  • Randomized Algorithms and Probability
  • Monte Carlo Simulation
    • Accuracy of a Monte Carlo Simulation
      • Computing the Margin of Error
      • Computing the Number of Trials
  • Monte Carlo Integration
  • Exercises
• String Searching
  • The General Problem
    • Terms and Definitions
  • The Rabin-Karp Algorithm
    • String Searching via Hashing
      • Properties of Modulo
      • An Example
    • The Trick That Makes Rabin-Karp Fast
    • Implementing the Rabin-Karp String Search
    • Speeding Up Rabin-Karp
      • Avoiding the Modulo Operation
      • Avoiding False Matches Through Randomness
  • The Knuth-Morris-Pratt Algorithm
    • Implementation of Knuth-Morris-Pratt
    • Analysis of Knuth-Morris-Pratt
    • A Knuth-Morris-Pratt Example
  • The Boyer-Moore Algorithm
    • Implementation of Boyer-Moore
    • A Boyer-Moore Example
  • Exercises
• Sparse Arrays Revisited
  • Hash Tables
  • Binary Search Trees
  • Exercises
• Pointers and Malloc
  • Memory and Pointers
    • Memory and Addresses
    • C Syntax for Pointers
    • Call by Reference versus Call by Value
  • Arrays and Pointers in C
  • Dynamic Memory Allocation
    • Malloc, Sizeof and Free
      • Malloc
      • Sizeof
      • Free
  • Dynamically Allocating Arrays
    • One-Dimensional Arrays
    • Two-Dimensional Arrays
      • A Digression Into Engineering
• Data Representation
  • Representing Integers
    • Unsigned Binary Numbers
      • Conversion of Binary to Decimal
      • Conversion of Decimal to Binary
      • Addition of Unsigned Binary Numbers
    • Signed Binary Numbers
      • Addition and Subtraction of Signed Binary Numbers
      • Shifting Signed Binary Numbers
      • Hexadecimal Notation
  • Representing Characters
  • Representing Programs
  • Memory Organization
    • Units of Memory
      • Historical Perspective
    • Addresses and Pointers
    • Summary
  • Exercises
• About this document ...