Complexity

Lecture Description

Complexity; log, linear, quadratic, exponential algorithms

Course Description

This subject is aimed at students with little or no programming experience. It aims to provide students with an understanding of the role computation can play in solving problems. It also aims to help students, regardless of their major, to feel justifiably confident of their ability to write small programs that allow them to accomplish useful goals. The class will use the Python™ programming language.

Related Resources

Binary search: Wikipedia article on binary search (focus on the recursive implementation in Section 4)

Course Index

1. Introduction and Goals of the Course
2. Operators and operands
3. Common code patterns
4. Decomposition and abstraction through functions
5. Floating point numbers
6. Bisection methods
7. Lists and mutability
8. Complexity
9. Binary search
10. Divide and conquer methods
11. Testing and debugging
12. Knapsack problem
13. Dynamic programming
14. Introduction to object-oriented programming
15. Abstract data types
16. Encapsulation
17. Computational models
18. Presenting simulation results
19. Biased random walks
20. Monte Carlo simulations
21. Validating simulation results
22. Normal, uniform, and exponential distributions
23. Stock market simulation
24. Course overview: What do computer scientists do?