Computer Science

Hi everyone! This month I have a tasty collection of free computer science courses. All the courses have videos included.

The topics include: Introduction to computer science. Computational complexity and quantum computing. Introduction to computing systems. The C programming language. Multicore programming. Statistics and data mining. Combinatorics. Software testing. Evolutionary computation. Deep learning. Data structures and algorithms. Bonus lecture: Computational origami.


Introduction to Computer Science and Programming (MIT 6.00)


Course Website
Programming Video Lectures
Exams and Solutions

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.

Course topics:
What is computation; introduction to data types, operators, and variables. Operators and operands; statements; branching, conditionals, and iteration. Common code patterns: iterative programs. Decomposition and abstraction through functions; introduction to recursion. Floating point numbers, successive refinement, finding roots. Bisection methods, Newton/Raphson, introduction to lists. Lists and mutability, dictionaries, pseudocode, introduction to efficiency. Complexity; log, linear, quadratic, exponential algorithms. Binary search, bubble and selection sorts. Divide and conquer methods, merge sort, exceptions. Testing and debugging. More about debugging, knapsack problem, introduction to dynamic programming. Dynamic programming: overlapping subproblems, optimal substructure. Analysis of knapsack problem, introduction to object-oriented programming. Abstract data types, classes and methods. Encapsulation, inheritance, shadowing. Computational models: random walk simulation. Presenting simulation results, Pylab, plotting. Biased random walks, distributions. Monte Carlo simulations, estimating pi. Validating simulation results, curve fitting, linear regression. Normal, uniform, and exponential distributions; misuse of statistics. Stock market simulation. Course overview; what do computer scientists do?


Computational Complexity and Quantum Computation (Tim Gowers)


Comp. Complexity and Quantum Computation Video Lectures


Course description:
Computational complexity is the study of what resources, such as time and memory, are needed to carry out given computational tasks, with a particular focus on lower bounds for the amount needed of these resources. Proving any result of this kind is notoriously difficult, and includes the famous problem of whether P=NP. This course will be focused on two major results in the area. The first is a lower bound, due to Razborov, for the number of steps needed to determine whether a graph contains a large clique, if only "monotone" computations are allowed. This is perhaps the strongest result in the direction of showing that P and N P are distinct (though there is unfortunately a very precise sense in which the proof cannot be developed to a proof of the whole conjecture). The second is Peter Shor's remarkable result that a quantum computer can factorize large integers in polynomial time.

Course topics:
Equivalence between Turing machines and the circuit model of compuation. Final details needed for the quantum Fourier transform, such as how to "uncompute". Solving the descrete logirithm problem. Definition of P, NP and NP-complete and some examples. A demonstration that clique is NP-complete, and some lower bound complexity proofs which don't work. Razborov's proof that no monotone circuit can solve Clique in polynomial time. No "natural proof" exists for proving a separation between P and NP if one-way functions exist. We then move into a mathematician's description of quantum computation starting from probabilistic computation. Description of quantum computation continued. We start describing Shor's factoring algorithm.


Introduction to Computing Systems


Course Website
Computing Systems Video Lectures
Exams


Course topics:
Computer systems organized as a systematic set of transformations; representation using bits. Bits and Operations on Bits: unsigned and signed integers; arithmetic and logical operations; ASCII; floating point; hexadecimal notation. Digital Logic Structures: gates; combinational logic; storage elements. Digital Logic Structures: memory; sequential logic; clock. The von Neumann Model: basic concepts; instruction processing; sequencing. The LC-3: Instruction Set Architecture. The LC-3: Example program in LC-3 machine language; LC-3 datapath. Programming: problem solving using systematic decomposition, more examples, debugging. LC-3 Assembly Language; examples; assembly process. I/O abstractions: input from the keyboard, output to the monitor. Repeated Code: TRAPs and subroutines; Examples. Stacks; Executing subroutines with stacks. Introduction to C; Variables and Operators: basic data types, simple operators, examples. Operators: simple operators, memory allocation of variables, examples. Control Structures: conditional constructs. Control Structures: iterative constructs, comprehensive examples, problem solving. Functions: introduction, syntax, run-time stack. Functions: activation records, examples. Pointers and Arrays: introduction, problem solving, examples. Arrays: 2D arrays, examples. Testing and Debugging: introduction, error taxonomy, using a debugger. Recursion: introduction, basic example, example showing run-time stack. Input and Output in C: standard library, basic I/O calls, file I/O, example. Basic Data Structures: introduction. Basic Data Structures: structures, defining new types, enumerations, dynamic memory allocation. Basic Data Structures: linked lists. Basic Data Structures: linked lists, linked structure traversal. Comprehensive Case Study: sorting. Simple Guide to C++: Design, abstractions, and implementation. Course Wrap-up and Advice for Sophomore System Builders.


Multicore Programming (MIT 6.189)


Course Website
Multicore Programming Video Lectures


Course description:
The course serves as an introductory course in parallel programming. It offers a series of lectures on parallel programming concepts as well as a group project providing hands-on experience with parallel programming. The students will have the unique opportunity to use the cutting-edge PLAYSTATION 3 development platform as they learn how to design and implement exciting applications for multicore architectures.

Course topics:
Introduction to Cell processor. Introduction to parallel architectures. Introduction to concurrent programming. Parallel programming concepts. Design patterns for parallel programming I. Design patterns for parallel programming II. StreamIt language. Debugging parallel programs. Performance monitoring and optimizations. Parallelizing compilers. StreamIt parallelizing compiler. Star-P. Synthesizing parallel programs. Cilk. Introduction to game development. The Raw experience. The future.


Statistical Aspects of Data Mining (Data Mining at Google)


Data Mining Video Lecture 1
Data Mining Video Lecture 2

Data Mining Video Lecture 3

Data Mining Video Lecture 4

Data Mining Video Lecture 5

Data Mining Video Lecture 6

Data Mining Video Lecture 7

Data Mining Video Lecture 8
Data Mining Video Lecture 9

Data Mining Video Lecture 10

Data Mining Video Lecture 11
Data Mining Video Lecture 12
Data Mining Video Lecture 13
Course Website


This is a talk series being given at Google by David Mease based on a Master's level stats course he is teaching this summer at Stanford.

Course topics:
1. Discussion of locations of potentially useful data (grocery checkout, apartment door card, elevator card, laptop login, traffic sensors, cell phone, google badge, etc). Note mild obsession with consent. Overview of predicting future vs describing patterns, and other broad areas of data mining. Intro to R. 2. Data. Reading datasets into excel and R. Observational (data mining) vs Experimental data. Qualitative analysis vs quantitative analysis. Nominal vs ordinal. 3. Sampling. 4. Empirical distribution function. Histograms. Plots. 5. Overlaying multiple plots. Statistical significance. Labels in plots. 6. Box plots. Color in plots. Installing R packages. ACCENT principles and Tufte. 7. Association Rules. Measures of location. Measures of spread. Measures of association. Frequent itemsets. Similar to conditional probabilities. 8. More association rule mining. Support and confidence calculations. Personalization using rules. Beyond support and confidence. 9. Review. 10. Data Classification. A negative view of decision trees. Decision trees in R. Algorithms for generating decision trees. 11. More decision trees. Gini index. Entropy. Pruning. Precision, recall, f-measure, and ROC curve. 12. Nearest Neighbor. KNN. Support Vector Machines. Adding 'slack' variables, using basis functions to make the space linearly separable. Some comments on Stats vs ML. Intro to ensemble (uncorrelated) classifiers. Random Forests. AdaBoost - Adaptive Boosting. Some discussion of limits of classifiers (nondeterministic observational datasets). Clustering. K-Means.


Data Structures and Algorithms (COMP1927, UNSW)


Data Structures and Algorithms Video Lectures


Lectures by Richard Buckland from The University of New South Wales.

Course topics:
Abstract data types. Stacks. Queues. Recursion. Time and Space Complexity. Big Oh Notation. Complexity Analysis. BFS (Breadth First Search). DFS (Depth First Search). Trees. Tree Algorithms. Self Balancing Trees. Graphs and Graph Algorithms. C99 Extensions. Unit Testing. Debugging. Pair Programming.


Peter Gibbons Memorial Lecture Series


Peter Gibbsons Memorial Video Lectures


The Combinatorics at the Heart of the Problem


Making Software Testing Easier


Developing Darwin's Computer


Technologies for Deep Learning



Computational Origami


Erik Demaine on Computational Origami


Lecture description:
As a glassblower, Tetris master, magician, and mathematician, the MIT professor has spent his life exploring the mysterious and fascinating relationships between art and geometry. Here, he discusses the potential of lasers, leopard spots, and computer science to breathe new life into everything from architecture to origami. Demaine has a "hard time distinguishing art from mathematics." His approach to art has a strong emphasis on collaboration, which as he says, is a rare thing in art. Demaine is a professor in computer science and mathematics. He realized that "mathematics (itself) is an art form." During the talk, he also mentions Escher's study of mathematics.


Have fun with these lectures!


Related Posts

Free Computer Science Video Lecture Courses
(Courses include web application development, lisp/scheme programming, data structures, algorithms, machine structures, programming languages, principles of software engineering, object oriented programming in java, systems, computer system engineering, computer architecture, operating systems, database management systems, performance analysis, cryptography, artificial intelligence)


Programming Lectures and Tutorials
(Lectures include topics such as software engineering, javascript programming, overview of firefox's firebug extension, document object model, python programming, design patterns in python, java programming, delphi programming, vim editor and sqlite database design)


Programming, Networking Free Video Lectures and Other Interesting Ones
(Includes lectures on Python programming language, Common Lisp, Debugging, HTML and Web, BGP networking, Building scalable systems, and as a bonus lecture History of Google)


More Mathematics and Theoretical Computer Science Video Lectures
(Includes algebra, elementary statistics, applied probability, finite mathematics, trigonometry with calculus, mathematical computation, pre-calculus, analytic geometry, first year calculus, business calculus, mathematical writing (by Knuth), computer science problem seminar (by Knuth), dynamic systems and chaos, computer musings (by Knuth) and other Donald E. Knuth lectures)


More Mathematics and Theoretical Computer Science Video Lectures
(Includes algebra, elementary statistics, applied probability, finite mathematics, trigonometry with calculus, mathematical computation, pre-calculus, analytic geometry, first year calculus, business calculus, mathematical writing (by Knuth), computer science problem seminar (by Knuth), dynamic systems and chaos, computer musings (by Knuth) and other Donald E. Knuth lectures)


Pure Computer Science
(Includes basics of computation theory, intro to computer science, data structures, compiler optimization, intro to computers and internet, intro to clojure, and some videos from EECS colloquium at Case Western Reserve University.)