Knapsack Problem

More about debugging, knapsack problem, introduction to dynamic programming

Course Lectures

• Introduction and Goals of the Course

  Eric Grimsom

  Play

  Goals of the course; what is computation; introduction to data types, operators, and variables

• Operators and Operands

  Eric Grimsom

  Play

  Operators and operands; statements; branching, conditionals, and iteration

• Common Code Patterns

  Eric Grimsom

  Play

  Common code patterns: iterative programs

• Decomposition and Abstraction Through Functions

  Eric Grimsom

  Play

  Decomposition and abstraction through functions; introduction to recursion

• Floating Point Numbers

  Eric Grimsom

  Play

  Floating point numbers, successive refinement, finding roots

• Bisection Methods

  Eric Grimsom

  Play

  Bisection methods, Newton/Raphson, introduction to lists

• Lists and Mutability

  Eric Grimsom

  Play

  Lists and mutability, dictionaries, pseudocode, introduction to efficiency

• Complexity

  Eric Grimsom

  Play

  Complexity; log, linear, quadratic, exponential algorithms

• Binary Search

  Eric Grimsom

  Play

  Binary search, bubble and selection sorts

• Divide and Conquer Methods

  Eric Grimsom

  Play

  Divide and conquer methods, merge sort, exceptions

• Testing and Debugging

  Eric Grimsom

  Play

  Testing and debugging

• Knapsack Problem

  Eric Grimsom

  Playing

  More about debugging, knapsack problem, introduction to dynamic programming

• Dynamic Programming

  Eric Grimsom

  Play

  Dynamic programming: overlapping subproblems, optimal substructure

• Introduction to Object-Oriented Programming

  Eric Grimsom

  Play

  Analysis of knapsack problem, introduction to object-oriented programming

• Abstract Data Types Classes and Methods

  Eric Grimsom

  Play

  Abstract data types, classes and methods

• Encapsulation

  Eric Grimsom

  Play

  Encapsulation, inheritance, shadowing

• Computational Models

  Eric Grimsom

  Play

  Computational models: random walk simulation

• Presenting Simulation Results

  Eric Grimsom

  Play

  Presenting simulation results, Pylab, plotting

• Introduction to Digital Communication

  Eric Grimsom

  Play

  Course overview; what do computer scientists do?

• Biased Random Walks

  Eric Grimsom

  Play

  Biased random walks, distributions

• Monte Carlo Simulations

  Eric Grimsom

  Play

  Monte Carlo simulations, estimating pi

• Validating Simulation Results

  Eric Grimsom

  Play

  Validating simulation results, curve fitting, linear regression

• Normal, Uniform, and Exponential Distributions

  Eric Grimsom

  Play

  Normal, uniform, and exponential distributions; misuse of statistics

• Stock Market Simulation

  Eric Grimsom

  Play

  Stock market simulation