Introduction to Computer Science and Programming using Python (Repost)
Introduction to Computer Science and Programming using Python (Repost)
English | MP4 | 640x480 | AVC 768 Kbps 29.970 fps | AAC 80 Kbps 44.1 khz | 32h 34mn | 7.8 GB
Sample Files: present
Genre: Video Training
English | MP4 | 640x480 | AVC 768 Kbps 29.970 fps | AAC 80 Kbps 44.1 khz | 32h 34mn | 7.8 GB
Sample Files: present
Genre: Video Training
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.
About This Course
Let's start with the strategic goals of this course:
Help students (who may or may not intend to major in computer science) to feel justifiably confident of their ability to write small programs.
Map scientific problems into computational frameworks.
Position students so that they can compete for jobs by providing competence and confidence in computational problem solving.
Prepare college freshman and sophomores who have no prior programming experience or knowledge of computer science for an easier entry into computer science or electrical engineering majors.
Prepare students from other majors to make profitable use of computational methods in their chosen field.
6.00SC can be summarized with these six major topics or objectives:
Learning a language for expressing computations—Python
Learning about the process of writing and debugging a program
Learning about the process of moving from a problem statement to a computational formulation of a method for solving the problem
Learning a basic set of "recipes"—algorithms
Learning how to use simulations to shed light on problems that don't easily succumb to closed form solutions
Learning about how to use computational tools to help model and understand data
6.00 is designed to help you become skillful at making the computer do what you want it to do. Once you acquire this skill, your first instinct when confronted with many tasks will be to write a program to do the task for you. Said another way, we want to help you learn to apply computational modes of thought to frame problems, and to guide the process of deducing information in a computational manner.
This means that the primary knowledge you will take away from this course is the art of computational problem solving. Unlike many introductory level courses, having an ability to memorize facts will be of little help in 6.00. This course is about learning to solve problems, not learning facts. This, by the way, is exactly why all exams are open book.
Prerequisites and Preparation
This course is aimed at students with little or no prior programming experience but a desire to understand computational approaches to problem solving. Now, by definition, none of you are under-qualified for this course. In terms of being over-qualified — if you have a lot of prior programming experience, we really don't want you wasting your time, and in this case we would suggest that you talk to me about how well this class suits your needs, and to discuss other options. In addition, we want to maintain a productive educational environment, and thus we don't want over-qualified students making other students feel inadequate, when in fact they are only inexperienced.
Since computer programming involves computational modes of thinking, it will help to have some mathematical and logical aptitude. You should be confident with your math skills up to pre-calculus.
Unit 1
We will start the semester by discussing the difference between imperative knowledge and definitional knowledge, as well as between fixed program and stored program computers, and finally the definitions of syntax, static semantics, and semantics. We cover straight line, branching, and looping programs. Other topics are binary representation of numbers, orders of growth, and debugging programs.
Python concepts covered in this unit include values, types, int, float, Boolean, strings (str), tuples, dictionaries (dict), and lists. We will also learn about expressions and statements—especially how to effectively use print statements in your programs. Other topics include assignment, conditionals, loops, assert, functions, scope, object models, mutation, and mutability.
By the end of Unit 1 you should be familiar with the following algorithmic techniques: guess and check, linear search, bisection search, successive approximation, and Newton-Raphson (Newton's method). You will also learn recursive definitions, problem solving techniques, and how to structure programs using decomposition and abstraction, including specifications and parameters.
Unit 1 ends with a quiz covering all material (lectures, recitations, and problem sets) through Efficiency and Order of Growth.
Session 1
This lecture covers course expectations, introduces computer programming and its uses, and begins to familiarize the student with concepts related to how programs work.
Lecture 1: Introduction to 6.00
Topics covered: Purposes of the course, declarative and imperative knowledge, flow of control, algorithms, fixed program and stored program computers, termination conditions, interpretation, compilation, syntax, static semantics, semantics, and types of errors.
Session 2
This lecture covers the building blocks of straight line and branching programs: Objects, types, operators, variables, execution, and conditional statements. It also discusses common errors related to the topics covered.
Lecture 2: Core Elements of a Program
Topics covered: IDLE, types of objects, operators, overloading, commands, variables, assignment, input, straight line and branching programs, looping constructs, turing completeness, conditionals, nesting.
Recitation 1: Introduction to Coding Concepts
Topics covered: Syntax, semantics, object types, comparison, loops, coding.
Session 3
This lecture covers the use of iteration to build programs whose execution time depends upon the size of inputs. It also introduces search problems and brute force and bisection for solving them.
Lecture 3: Problem Solving
Topics covered: Termination, decrementing functions, exhaustive enumeration, brute force, while loop, for loop, approximation, specifications, bisection search.
Session 4
This lecture introduces the notion of decomposition and abstraction by specification. It also covers Python modules, functions, parameters, and scoping. Finally, it uses the Python assert statement and type 'str'.
Lecture 4: Machine Interpretation of a Program
Topics covered: Decomposition, module, function, abstraction, formal parameter, actual parameter, argument, assert, scope, mapping, stack, last in first out, LIFO, strings, slicing.
Recitation 2: Loops, Tuples, Strings and Functions
Topics covered: Loops, tuples, concatenating tuples and strings, string operations, immutability, range function, slicing, types of data structures, decrementing function, global and local variables, global keepers.
Session 5
This lecture introduces Python tuples, lists, and dictionaries, as well as the concept of mutability and how to avoid problems relating to it.
Lecture 5: Objects in Python
Topics covered: Tuples, lists, dictionaries, methods, identifiers, modifying objects, aliasing, mutability.
Session 6
This lecture finishes the discussion of dictionaries, then introduces inductive reasoning and recursion. Examples include generating the Fibonacci sequence and solving the Towers of Hanoi problem.
Lecture 6: Recursion
Topics covered: Dictionaries, modular abstraction, divide and conquer, recursion, tower of Hanoi, base case, Fibonacci sequence.
Recitation 3: Lists and their Elements, Sorting, and Recursion
Topics covered: Tuples, lists, iteration, list elements, sorting lists, mutability, keys, dictionaries, chain method, recursion, base case, Tower of Hanoi.
Session 7
This lecture starts with a brief explanation of why floating point numbers are only an approximation of the real numbers. Most of the lecture is about a systematic approach to debugging.
Lecture 7: Debugging
Topics covered: Binary, float, floating point, approximations, debugging, runtime error.
Recitation 4: Recursion, Pseudo code and Debugging
Topics covered: Recursion, divide and conquer, base cases, iterative vs. recursive algorithms, Fibonacci numbers example, recursive bisection search, optional and default parameters, pseudo code, introduction to debugging, test cases and edge cases, and floating points.
Session 8
This lecture revolves around the topic of algorithmic efficiency. It introduces the random access model (RAM) of computation and "big O notation" as a way to talk about order of growth. It concludes with binary search.
Lecture 8: Efficiency and Order of Growth
Topics covered: Efficiency, problem reduction, RAM, best case, worst case, expected case, growth, exponential growth, polynomial growth, logarithmic growth, global variables.
Session 9
This lecture discusses how indirection is used to provide an efficient implementation of Python lists and other data structures. It also presents and analyzes the efficiency of selection and merge sort.
Lecture 9: Memory and Search Methods
Topics covered: Memory, storage, indirection, sorting.
Quiz I
Unit 2
Unit 2 begins with hash functions, which are useful for mapping large data sets. We will continue with a broad introduction to object-oriented programming languages (Python is an example), covering objects, classes, subclasses, abstract data types, exceptions, and inheritance. Other algorithmic concepts covered are "Big O notation," divide and conquer, merge sort, orders of growth, and amortized analysis.
The next several lectures introduce effective problem-solving methods which rely on probability, statistical thinking, and simulations to solve both random and non-random problems. A background in probability is not assumed, and we will briefly cover basic concepts such as probability distributions, standard deviation, coefficient of variation, confidence intervals, linear regression, standard error, and plotting techniques. This will include an introduction to curve fitting, and we introduce the Python libraries numpy and pylab to add tools to create simulations, graphs, and predictive models.
We will spend some time on random walks and Monte Carlo simulations, a very powerful class of algorithms which invoke random sampling to model and compute mathematical or physical systems. The Monty Hall problem is used as an example of how to use simulations, and the knapsack problem introduces our discussion of optimization. Finally, we will begin looking at supervised and unsupervised machine learning, and then turn to data clustering.
At the end of Unit 2 there will be an exam covering all material (lectures, recitations, and problem sets) from the beginning of the course through More Optimization and Clustering.
Session 10
This lecture starts by showing how hashing can be used to achieve near constant time lookups and the concept of classes as understood by a computer. It then introduces exceptions.
Lecture 10: Hashing and Classes
Topics covered: Hashing, bucket, collision, linear rehash, exceptions, classes, modules, built-in classes.
Session 11
In this lecture, we learn about object-oriented programming (OOP) and how classes are used to implement new types of objects in Python. As part of that discussion we introduce inheritance.
Lecture 11: OOP and Inheritance
Topics covered: Object-oriented programming (OOP), abstract data types, specifications, subclasses, inheritance.
Recitation 5: Quiz 1 Answers and Object-Oriented Programming
Topics covered: Double recursion, big O notation, binary function, run times, object-oriented programming, classes, encapsulation, methods, class hierarchy, subclasses, inheritance, polymorphism, accessor and mutator functions, Person example, underbar methods, self parameter.
Session 12
This lecture completes the introduction of classes by showing a way to implement user-defined iterators. It then starts a new unit with a discussion of simulation models, and illustrates some of the ideas underlying simulations modeling by simulating a random walk.
Lecture 12: Introduction to Simulation and Random Walks
Topics covered: Subclasses, inheritance, generator, analytic methods, simulation methods, simulations, models, random walk.
Optional Recitation: Algorithm Complexity and Class Review
Topics covered: Big O notation, algorithm complexity, algorithm comparison example, object-oriented programming, Person class example, defensive programming, private attributes, mutability, aliasing.
Session 13
This lecture returns briefly to random walks, and moves on to discuss different views of non-determinism and an introduction to probability. It concludes with examples of using pylab to plot data.
Lecture 13: Some Basic Probability and Plotting Data
This lecture begins a deeper look at simulations with an introduction to randomness, probability, and plotting through programming.
Session 14
This lecture starts with some examples of how to use pylab's plotting mechanisms. It then returns to the topic of using probability and statistics to derive information from samples.
Lecture 14: Sampling and Monte Carlo Simulation
Topics covered: Plotting, randomness, probability, Pascal's algorithm, Monte Carlo simulation, inferential statistics, gambler's fallacy, law of large numbers.
Session 15
This lecture presents ways of ascertaining how dependable information extracted from samples is likely to be. It covers standard deviation, coefficient of variation, and standard error. It also shows how to use pylab to produce histograms.
Lecture 15: Statistical Thinking
Topics covered: Variance, standard deviation, standard error.
Recitation 6: Probability and Statistics
Topics covered: Probability, statistics, Venn diagrams, distributions, standard deviation, Monte Carlo simulation, plotting graphs.
Session 16
This lecture starts by defining normal (Gaussian), uniform, and exponential distributions. It then shows how Monte Carlo simulations can be used to analyze the classic Monty Hall problem and to find an approximate value of pi.
Lecture 16: Using Randomness to Solve Non-random Problems
Topics covered: Gaussian distributions, analytical models, simulations, exponential growth, probability, distributions, Monty Hall problem.
Session 17
This lecture is about how to use computation to help understand experimental data. It talks about using linear regression to fit a curve to data, and introduces the coefficient of determination as a measure of the tightness of a fit.
Lecture 17: Curve Fitting
Topics covered: Arrays, curve fitting, numpy, pylab, least squares fit, prediction.
Recitation 7: Distributions, Monte Carlo, and Regressions
Topics covered: Data distributions, mean, standard deviation, Monte Carlo simulations, Monty Hall problem, Riemann sum method, data regressions, r^2 (r-squared), coefficient of termination, scientific applications of programming.
Session 18
This lecture returns to material covered in Lecture 17 Curve Fitting, emphasizing the interplay among theory, experimentation, and computation and addressing the problem of over-fitting. It then moves on to introduce the notion of an optimization problem, and illustrates it using the 0/1 knapsack problem.
Lecture 18: Optimization Problems and Algorithms
Topics covered: Modeling, optimization, greedy algorithms, 0-1 knapsack problem.
Session 19
This lecture continues to discuss optimization in the context of the knapsack problem, and talks about the difference between greedy approaches and optimal approaches. It then moves on to discuss supervised and unsupervised machine learning optimization problems. Most of the time is spent on clustering.
Lecture 19: More Optimization and Clustering
Topics covered: Knapsack problem, local and global optima, supervised and unsupervised machine learning, training error, clustering, linkage, feature vectors.
Quiz II
Unit 3
In Unit 3 we pick up our discussion of data clustering from the end of Unit 2. We introduce graphs as a set of nodes and edges, and learn how these can help solve degrees-of-separation problems and to find a shortest path. We will practice using pseudocode as preparation for writing code, and learn about dynamic programming as we attempt to write optimally efficient programs.
In order to become better statistical thinkers we will learn to spot and avoid several common logical and statistical fallacies like bias, data enhancement, causal fallacies, and the Texas sharpshooter fallacy. In the penultimate lecture we introduce queuing network simulations and important factors like the arrival process, service mechanism, and queue characteristics. We will compare the most common queue disciplines such as first-in-first-out, last-in-first-out, or shortest-remaining-processing-time. The last class presents different possible careers in computer science, and its application across diverse fields and industries.
Unit 3 concludes with a Final Exam covering all material (lectures, recitations, and problem sets) from the beginning of the course through Queuing Network Models.
Session 20
This lecture covers hierarchical clustering and introduces k-means clustering.
Lecture 20: More Clustering
Topics covered: Feature vectors, scaling, k-means clustering.
Recitation 8: Hierarchical and k-means Clustering
Topics covered: Unsupervised learning, k-means clustering, distance metric, cluster merging, centroid, k-mean error, hold out set, k value significance, features of k-means clustering, merits and disadvantages of types of clustering.
Session 21
This lecture begins by finishing up k-means clustering. It then moves on to introduce the notion of modeling things using graphs (sets of nodes and edges that link them).
Lecture 21: Using Graphs to Model Problems, Part 1
Topics covered: Pseudocode, graphs, nodes, edges, adjacency matrix, adjacency list.
Session 22
This lecture returns to graph theory. It defines and gives examples of some classic graph problems: shortest path, shortest weighted path, cliques, and min-cut. It then shows how memoization can be used to speed up some algorithms.
Lecture 22: Using Graphs to Model Problems, Part 2
Topics covered: Dynamic programming, optimal path, overlapping subproblems, weighted edges, specifications, restrictions, efficiency, pseudo-polynomials.
Recitation 9: Directed and Undirected Node Graphs
Topics covered: Node graphs, nodes, edges, directed and undirected graphs, weighted edges, depth-first search, breadth-first search, graph cycles, children of nodes, shortest path, lambda functions.
Session 23
This lecture introduces dynamic programming, and discusses the notions of optimal substructure and overlapping sub-problems.
Lecture 23: Dynamic Programming
Topics covered: Dynamic programming, optimal path, overlapping subproblems, weighted edges, specifications, restrictions, efficiency, pseudo-polynomials.
Session 24
This lecture discusses some common ways that people use statistics to draw invalid or misleading conclusions.
Lecture 24: Avoiding Statistical Fallacies
Topics covered: Statistics, plotting, correlation, causation, bias, logical fallacies, data enhancement, Texas sharpshooter fallacy.
Recitation 10: Introduction to Dynamic Programming
Topics covered: Dynamic programming, memoization, overlapping subproblems, optional substructure, Fibonacci memoization example.
Session 25
This lecture introduces queuing network models and simulations. The lecture is designed to prepare students to read the code they are asked to study in preparation for the final exam.
Lecture 25: Queuing Network Models
Topics covered: Queuing network simulations, Poisson distributions, wait time, queue length, server utilization, FIFO, LIFO, SRPT.
Session 26
This lecture provides some perspective on the material covered in the course. In addition to giving a high level view of the topics covered, it provides a glimpse of what one might do with an education in computer science.
Lecture 26: What Do Computer Scientists Do?
Topics covered: Careers in computer science, computational thinking, abstraction, automation.
Final Exam
We will start the semester by discussing the difference between imperative knowledge and definitional knowledge, as well as between fixed program and stored program computers, and finally the definitions of syntax, static semantics, and semantics. We cover straight line, branching, and looping programs. Other topics are binary representation of numbers, orders of growth, and debugging programs.
Python concepts covered in this unit include values, types, int, float, Boolean, strings (str), tuples, dictionaries (dict), and lists. We will also learn about expressions and statements—especially how to effectively use print statements in your programs. Other topics include assignment, conditionals, loops, assert, functions, scope, object models, mutation, and mutability.
By the end of Unit 1 you should be familiar with the following algorithmic techniques: guess and check, linear search, bisection search, successive approximation, and Newton-Raphson (Newton's method). You will also learn recursive definitions, problem solving techniques, and how to structure programs using decomposition and abstraction, including specifications and parameters.
Unit 1 ends with a quiz covering all material (lectures, recitations, and problem sets) through Efficiency and Order of Growth.
Session 1
This lecture covers course expectations, introduces computer programming and its uses, and begins to familiarize the student with concepts related to how programs work.
Lecture 1: Introduction to 6.00
Topics covered: Purposes of the course, declarative and imperative knowledge, flow of control, algorithms, fixed program and stored program computers, termination conditions, interpretation, compilation, syntax, static semantics, semantics, and types of errors.
Session 2
This lecture covers the building blocks of straight line and branching programs: Objects, types, operators, variables, execution, and conditional statements. It also discusses common errors related to the topics covered.
Lecture 2: Core Elements of a Program
Topics covered: IDLE, types of objects, operators, overloading, commands, variables, assignment, input, straight line and branching programs, looping constructs, turing completeness, conditionals, nesting.
Recitation 1: Introduction to Coding Concepts
Topics covered: Syntax, semantics, object types, comparison, loops, coding.
Session 3
This lecture covers the use of iteration to build programs whose execution time depends upon the size of inputs. It also introduces search problems and brute force and bisection for solving them.
Lecture 3: Problem Solving
Topics covered: Termination, decrementing functions, exhaustive enumeration, brute force, while loop, for loop, approximation, specifications, bisection search.
Session 4
This lecture introduces the notion of decomposition and abstraction by specification. It also covers Python modules, functions, parameters, and scoping. Finally, it uses the Python assert statement and type 'str'.
Lecture 4: Machine Interpretation of a Program
Topics covered: Decomposition, module, function, abstraction, formal parameter, actual parameter, argument, assert, scope, mapping, stack, last in first out, LIFO, strings, slicing.
Recitation 2: Loops, Tuples, Strings and Functions
Topics covered: Loops, tuples, concatenating tuples and strings, string operations, immutability, range function, slicing, types of data structures, decrementing function, global and local variables, global keepers.
Session 5
This lecture introduces Python tuples, lists, and dictionaries, as well as the concept of mutability and how to avoid problems relating to it.
Lecture 5: Objects in Python
Topics covered: Tuples, lists, dictionaries, methods, identifiers, modifying objects, aliasing, mutability.
Session 6
This lecture finishes the discussion of dictionaries, then introduces inductive reasoning and recursion. Examples include generating the Fibonacci sequence and solving the Towers of Hanoi problem.
Lecture 6: Recursion
Topics covered: Dictionaries, modular abstraction, divide and conquer, recursion, tower of Hanoi, base case, Fibonacci sequence.
Recitation 3: Lists and their Elements, Sorting, and Recursion
Topics covered: Tuples, lists, iteration, list elements, sorting lists, mutability, keys, dictionaries, chain method, recursion, base case, Tower of Hanoi.
Session 7
This lecture starts with a brief explanation of why floating point numbers are only an approximation of the real numbers. Most of the lecture is about a systematic approach to debugging.
Lecture 7: Debugging
Topics covered: Binary, float, floating point, approximations, debugging, runtime error.
Recitation 4: Recursion, Pseudo code and Debugging
Topics covered: Recursion, divide and conquer, base cases, iterative vs. recursive algorithms, Fibonacci numbers example, recursive bisection search, optional and default parameters, pseudo code, introduction to debugging, test cases and edge cases, and floating points.
Session 8
This lecture revolves around the topic of algorithmic efficiency. It introduces the random access model (RAM) of computation and "big O notation" as a way to talk about order of growth. It concludes with binary search.
Lecture 8: Efficiency and Order of Growth
Topics covered: Efficiency, problem reduction, RAM, best case, worst case, expected case, growth, exponential growth, polynomial growth, logarithmic growth, global variables.
Session 9
This lecture discusses how indirection is used to provide an efficient implementation of Python lists and other data structures. It also presents and analyzes the efficiency of selection and merge sort.
Lecture 9: Memory and Search Methods
Topics covered: Memory, storage, indirection, sorting.
Quiz I
Unit 2
Unit 2 begins with hash functions, which are useful for mapping large data sets. We will continue with a broad introduction to object-oriented programming languages (Python is an example), covering objects, classes, subclasses, abstract data types, exceptions, and inheritance. Other algorithmic concepts covered are "Big O notation," divide and conquer, merge sort, orders of growth, and amortized analysis.
The next several lectures introduce effective problem-solving methods which rely on probability, statistical thinking, and simulations to solve both random and non-random problems. A background in probability is not assumed, and we will briefly cover basic concepts such as probability distributions, standard deviation, coefficient of variation, confidence intervals, linear regression, standard error, and plotting techniques. This will include an introduction to curve fitting, and we introduce the Python libraries numpy and pylab to add tools to create simulations, graphs, and predictive models.
We will spend some time on random walks and Monte Carlo simulations, a very powerful class of algorithms which invoke random sampling to model and compute mathematical or physical systems. The Monty Hall problem is used as an example of how to use simulations, and the knapsack problem introduces our discussion of optimization. Finally, we will begin looking at supervised and unsupervised machine learning, and then turn to data clustering.
At the end of Unit 2 there will be an exam covering all material (lectures, recitations, and problem sets) from the beginning of the course through More Optimization and Clustering.
Session 10
This lecture starts by showing how hashing can be used to achieve near constant time lookups and the concept of classes as understood by a computer. It then introduces exceptions.
Lecture 10: Hashing and Classes
Topics covered: Hashing, bucket, collision, linear rehash, exceptions, classes, modules, built-in classes.
Session 11
In this lecture, we learn about object-oriented programming (OOP) and how classes are used to implement new types of objects in Python. As part of that discussion we introduce inheritance.
Lecture 11: OOP and Inheritance
Topics covered: Object-oriented programming (OOP), abstract data types, specifications, subclasses, inheritance.
Recitation 5: Quiz 1 Answers and Object-Oriented Programming
Topics covered: Double recursion, big O notation, binary function, run times, object-oriented programming, classes, encapsulation, methods, class hierarchy, subclasses, inheritance, polymorphism, accessor and mutator functions, Person example, underbar methods, self parameter.
Session 12
This lecture completes the introduction of classes by showing a way to implement user-defined iterators. It then starts a new unit with a discussion of simulation models, and illustrates some of the ideas underlying simulations modeling by simulating a random walk.
Lecture 12: Introduction to Simulation and Random Walks
Topics covered: Subclasses, inheritance, generator, analytic methods, simulation methods, simulations, models, random walk.
Optional Recitation: Algorithm Complexity and Class Review
Topics covered: Big O notation, algorithm complexity, algorithm comparison example, object-oriented programming, Person class example, defensive programming, private attributes, mutability, aliasing.
Session 13
This lecture returns briefly to random walks, and moves on to discuss different views of non-determinism and an introduction to probability. It concludes with examples of using pylab to plot data.
Lecture 13: Some Basic Probability and Plotting Data
This lecture begins a deeper look at simulations with an introduction to randomness, probability, and plotting through programming.
Session 14
This lecture starts with some examples of how to use pylab's plotting mechanisms. It then returns to the topic of using probability and statistics to derive information from samples.
Lecture 14: Sampling and Monte Carlo Simulation
Topics covered: Plotting, randomness, probability, Pascal's algorithm, Monte Carlo simulation, inferential statistics, gambler's fallacy, law of large numbers.
Session 15
This lecture presents ways of ascertaining how dependable information extracted from samples is likely to be. It covers standard deviation, coefficient of variation, and standard error. It also shows how to use pylab to produce histograms.
Lecture 15: Statistical Thinking
Topics covered: Variance, standard deviation, standard error.
Recitation 6: Probability and Statistics
Topics covered: Probability, statistics, Venn diagrams, distributions, standard deviation, Monte Carlo simulation, plotting graphs.
Session 16
This lecture starts by defining normal (Gaussian), uniform, and exponential distributions. It then shows how Monte Carlo simulations can be used to analyze the classic Monty Hall problem and to find an approximate value of pi.
Lecture 16: Using Randomness to Solve Non-random Problems
Topics covered: Gaussian distributions, analytical models, simulations, exponential growth, probability, distributions, Monty Hall problem.
Session 17
This lecture is about how to use computation to help understand experimental data. It talks about using linear regression to fit a curve to data, and introduces the coefficient of determination as a measure of the tightness of a fit.
Lecture 17: Curve Fitting
Topics covered: Arrays, curve fitting, numpy, pylab, least squares fit, prediction.
Recitation 7: Distributions, Monte Carlo, and Regressions
Topics covered: Data distributions, mean, standard deviation, Monte Carlo simulations, Monty Hall problem, Riemann sum method, data regressions, r^2 (r-squared), coefficient of termination, scientific applications of programming.
Session 18
This lecture returns to material covered in Lecture 17 Curve Fitting, emphasizing the interplay among theory, experimentation, and computation and addressing the problem of over-fitting. It then moves on to introduce the notion of an optimization problem, and illustrates it using the 0/1 knapsack problem.
Lecture 18: Optimization Problems and Algorithms
Topics covered: Modeling, optimization, greedy algorithms, 0-1 knapsack problem.
Session 19
This lecture continues to discuss optimization in the context of the knapsack problem, and talks about the difference between greedy approaches and optimal approaches. It then moves on to discuss supervised and unsupervised machine learning optimization problems. Most of the time is spent on clustering.
Lecture 19: More Optimization and Clustering
Topics covered: Knapsack problem, local and global optima, supervised and unsupervised machine learning, training error, clustering, linkage, feature vectors.
Quiz II
Unit 3
In Unit 3 we pick up our discussion of data clustering from the end of Unit 2. We introduce graphs as a set of nodes and edges, and learn how these can help solve degrees-of-separation problems and to find a shortest path. We will practice using pseudocode as preparation for writing code, and learn about dynamic programming as we attempt to write optimally efficient programs.
In order to become better statistical thinkers we will learn to spot and avoid several common logical and statistical fallacies like bias, data enhancement, causal fallacies, and the Texas sharpshooter fallacy. In the penultimate lecture we introduce queuing network simulations and important factors like the arrival process, service mechanism, and queue characteristics. We will compare the most common queue disciplines such as first-in-first-out, last-in-first-out, or shortest-remaining-processing-time. The last class presents different possible careers in computer science, and its application across diverse fields and industries.
Unit 3 concludes with a Final Exam covering all material (lectures, recitations, and problem sets) from the beginning of the course through Queuing Network Models.
Session 20
This lecture covers hierarchical clustering and introduces k-means clustering.
Lecture 20: More Clustering
Topics covered: Feature vectors, scaling, k-means clustering.
Recitation 8: Hierarchical and k-means Clustering
Topics covered: Unsupervised learning, k-means clustering, distance metric, cluster merging, centroid, k-mean error, hold out set, k value significance, features of k-means clustering, merits and disadvantages of types of clustering.
Session 21
This lecture begins by finishing up k-means clustering. It then moves on to introduce the notion of modeling things using graphs (sets of nodes and edges that link them).
Lecture 21: Using Graphs to Model Problems, Part 1
Topics covered: Pseudocode, graphs, nodes, edges, adjacency matrix, adjacency list.
Session 22
This lecture returns to graph theory. It defines and gives examples of some classic graph problems: shortest path, shortest weighted path, cliques, and min-cut. It then shows how memoization can be used to speed up some algorithms.
Lecture 22: Using Graphs to Model Problems, Part 2
Topics covered: Dynamic programming, optimal path, overlapping subproblems, weighted edges, specifications, restrictions, efficiency, pseudo-polynomials.
Recitation 9: Directed and Undirected Node Graphs
Topics covered: Node graphs, nodes, edges, directed and undirected graphs, weighted edges, depth-first search, breadth-first search, graph cycles, children of nodes, shortest path, lambda functions.
Session 23
This lecture introduces dynamic programming, and discusses the notions of optimal substructure and overlapping sub-problems.
Lecture 23: Dynamic Programming
Topics covered: Dynamic programming, optimal path, overlapping subproblems, weighted edges, specifications, restrictions, efficiency, pseudo-polynomials.
Session 24
This lecture discusses some common ways that people use statistics to draw invalid or misleading conclusions.
Lecture 24: Avoiding Statistical Fallacies
Topics covered: Statistics, plotting, correlation, causation, bias, logical fallacies, data enhancement, Texas sharpshooter fallacy.
Recitation 10: Introduction to Dynamic Programming
Topics covered: Dynamic programming, memoization, overlapping subproblems, optional substructure, Fibonacci memoization example.
Session 25
This lecture introduces queuing network models and simulations. The lecture is designed to prepare students to read the code they are asked to study in preparation for the final exam.
Lecture 25: Queuing Network Models
Topics covered: Queuing network simulations, Poisson distributions, wait time, queue length, server utilization, FIFO, LIFO, SRPT.
Session 26
This lecture provides some perspective on the material covered in the course. In addition to giving a high level view of the topics covered, it provides a glimpse of what one might do with an education in computer science.
Lecture 26: What Do Computer Scientists Do?
Topics covered: Careers in computer science, computational thinking, abstraction, automation.
Final Exam
General
Complete name : 01-Lecture 01_ Introduction to 6.00.mkv
Format : Matroska
Format version : Version 2
File size : 228 MiB
Duration : 41mn 27s
Overall bit rate : 768 Kbps
Encoded date : UTC 2012-05-13 10:25:23
Writing application : mkvmerge v5.2.1 ('A Far Off Place') built on Jan 2 2012 23:21:10
Writing library : libebml v1.2.3 + libmatroska v1.3.0
Video
ID : 1
Format : AVC
Format/Info : Advanced Video Codec
Format profile : Main@L3.0
Format settings, CABAC : Yes
Format settings, ReFrames : 3 frames
Format settings, GOP : M=1, N=30
Muxing mode : Header stripping
Codec ID : V_MPEG4/ISO/AVC
Duration : 41mn 27s
Width : 640 pixels
Height : 480 pixels
Display aspect ratio : 4:3
Frame rate mode : Constant
Frame rate : 29.970 fps
Color space : YUV
Chroma subsampling : 4:2:0
Bit depth : 8 bits
Scan type : Progressive
Default : Yes
Forced : No
Audio
ID : 2
Format : AAC
Format/Info : Advanced Audio Codec
Format profile : LC
Codec ID : A_AAC
Duration : 41mn 27s
Channel(s) : 2 channels
Channel positions : Front: L R
Sampling rate : 44.1 KHz
Compression mode : Lossy
Default : Yes
Forced : No
Complete name : 01-Lecture 01_ Introduction to 6.00.mkv
Format : Matroska
Format version : Version 2
File size : 228 MiB
Duration : 41mn 27s
Overall bit rate : 768 Kbps
Encoded date : UTC 2012-05-13 10:25:23
Writing application : mkvmerge v5.2.1 ('A Far Off Place') built on Jan 2 2012 23:21:10
Writing library : libebml v1.2.3 + libmatroska v1.3.0
Video
ID : 1
Format : AVC
Format/Info : Advanced Video Codec
Format profile : Main@L3.0
Format settings, CABAC : Yes
Format settings, ReFrames : 3 frames
Format settings, GOP : M=1, N=30
Muxing mode : Header stripping
Codec ID : V_MPEG4/ISO/AVC
Duration : 41mn 27s
Width : 640 pixels
Height : 480 pixels
Display aspect ratio : 4:3
Frame rate mode : Constant
Frame rate : 29.970 fps
Color space : YUV
Chroma subsampling : 4:2:0
Bit depth : 8 bits
Scan type : Progressive
Default : Yes
Forced : No
Audio
ID : 2
Format : AAC
Format/Info : Advanced Audio Codec
Format profile : LC
Codec ID : A_AAC
Duration : 41mn 27s
Channel(s) : 2 channels
Channel positions : Front: L R
Sampling rate : 44.1 KHz
Compression mode : Lossy
Default : Yes
Forced : No
Screenshots
Introduction to Computer Science and Programming using Python (Repost)
Introduction to Computer Science and Programming using Python (Repost)
Introduction to Computer Science and Programming using Python (Repost)
