Lectures Intro to Programming 1. Elements of Programming 1.1 Your First Program 1.2 Built-in Types of Data 1.3 Conditionals and Loops 1.4 Arrays 1.5 Input and Output 1.6 Case Study: PageRank 2. Functions 2.1 Static Methods 2.2 Libraries and Clients 2.3 Recursion 2.4 Case Study: Percolation 3. OOP 3.1 Using Data Types 3.2 Creating Data Types 3.3 Designing Data Types 3.4 Case Study: N-Body 4. Data Structures 4.1 Performance 4.2 Sorting and Searching 4.3 Stacks and Queues 4.4 Symbol Tables 4.5 Case Study: Small World Computer Science 5. Theory of Computing 5.1 Formal Languages 5.2 Turing Machines 5.3 Universality 5.4 Computability 5.5 Intractability 9.9 Cryptography 6. A Computing Machine 6.1 Representing Info 6.2 TOY Machine 6.3 TOY Programming 6.4 TOY Virtual Machine 7. Building a Computer 7.1 Boolean Logic 7.2 Basic Circuit Model 7.3 Combinational Circuits 7.4 Sequential Circuits 7.5 Digital Devices Beyond 8. Systems 8.1 Library Programming 8.2 Compilers 8.3 Operating Systems 8.4 Networking 8.5 Applications Systems 9. Scientific Computation 9.1 Floating Point 9.2 Symbolic Methods 9.3 Numerical Integration 9.4 Differential Equations 9.5 Linear Algebra 9.6 Optimization 9.7 Data Analysis 9.8 Simulation Related Booksites Web Resources FAQ Data Code Errata Lectures Appendices A. Operator Precedence B. Writing Clear Code C. Glossary D. TOY Cheatsheet E. Matlab Online Course Java Cheatsheet Programming Assignments Lectures This page provides information about online lectures and lecture slides for use in teaching and learning from the book Computer Science: An Interdisciplinary Approach. These lectures are appropriate for use by instructors as the basis for a “flipped” class on the subject, or for self-study by individuals. Flipped classroom. If you are an an instructor teaching introductory computer science, an effective way for you to teach the material in a typical college class is to adhere to a weekly cadence, as follows: Each week, send an email to all students in the class that briefly describes activities for that week (lectures, reading, and programming assignments drawn from the book or from this booksite). Students watch the lecture videos at their own pace, do the readings, and work on the programming assignments. Schedule a weekly “class meeting” for discussion of the material, reviews for exams, informal interaction with students, and any enrichment material you may wish to cover. This is just one suggestion—this material can support many different teaching styles and formats. Important note: A common mistake in teaching a flipped class is to add too much enrichment material. Our experience is that time in class meetings is much better spent preparing students for success on programming assignments and exams. If an instructor makes it clear that the best way to prepare for exams is to watch the lecture videos and do the reading, most students will do so. Class meetings then can involve interacting with students and with the material in such a way as to reinforce understanding. For example, working with potential exam questions is an excellent activity. Self-study. An effective way to learn the material on your own is to watch the lecture videos on some regular schedule, do the associated reading, and attempt to solve some of the exercises in the book or on the booksite on your own. If you get stuck on a particular exercise, find some others or try to solve some of the problems given in the lectures without looking at the solutions there. Available lectures. During the spring of 2020, the lecture videos are freely available. When watching a lecture video, it is very important to choose an appropriate speed. If it is too slow, you are likely to be bored; if it is too fast, you are likely to get lost. Also be sure to make liberal use of pause and rewind. The lecture videos are available from CUvids; the lecture slides are in pdf format. Lecture 0: Prologue—A Simple Machine. This lecture introduces fundamental ideas of computation in the context of a familiar and important application from the field of cryptography. The story motivates the study of computer science, but the concepts covered are a bit advanced, so novices may wish to review it again after watching the other lectures in the course. Lecture 1: Basics. Why program? This lecture addresses that basic question. Then it describes the anatomy of your first program and the process of developing a program in Java using either virtual terminals or a program development environment, with some historical context. Most of the lecture is devoted to a thorough coverage of Java's built-in data types, with example programs for each. Lecture 2: Conditionals and Loops. The if, while, and for statements are Java's fundamental control structures. This lecture is built around short programs that use these constructs to address important computational tasks. Examples include sorting, computing the square root, factoring, and simulating a random process. The lecture concludes with a detailed example illustrating the process of debugging a program. Lecture 3: Arrays. Computing with a large sequence of values of the same type is extremely common. This lecture describes Java's built-in array data structure that supports such applications, with several examples, including shuffling a deck of cards, the coupon collector test for randomness, and random walks in a grid. Lecture 4: Input and Output. To interact with our programs, we need mechanisms for taking information from the outside world and for presenting information to the outside world. This lecture describes several such mechanisms: for text, drawings, and animation. Detailed examples covered include fractal drawings that model natural phenomena and an animation of a ball bouncing around in the display window. Lecture 5: Functions and Libraries. Modular programming is the art and science of breaking a program into pieces that can be individually developed. This lecture introduces functions (Java methods), a fundamental mechanism that enables modular programming. Motivating examples include functions for the classic Gaussian distribution and an application that creates digital music. Lecture 6: Recursion. A recursive function is one that calls itself. This lecture introduces the concept by treating in detail the ruler function and (related) classic examples, including the Towers of Hanoi puzzle, the H-tree, and simple models of the real world based on recursion. We show a common pitfall in the use of recursion, and a simple way to avoid it, which introduces a different (related) programming paradigm known as dynamic programming. Lecture 7: Performance. When you develop a program, you need to be aware of its resource requirements. In this lecture, we describe a scientific approach to understanding performance, where we develop mathematical models describing the running time our programs and then run empirical tests to validate them. Eventually we come to a simple and effective approach that you can use to predict the running time of your own programs that involve significant amounts of computation. Lecture 8: Abstract Data Types. In Java, you can create your own data types and use them in your programs. In this and the next lecture, we show how this ability allows us to view our programs as abstract representations of real-world concepts. First we show the mechanics of writing client programs that use data types. Our examples involve abstractions such as color, images, and genes. This style of programming is known as object-oriented programming because our programs manipulate objects, which hold data type values. Lecture 9: Creating Data Types. Creating your own data types is the central activity in modern Java programming. This lecture covers the mechanics (instance variables, constructors, instance methods, and test clients) and then develops several examples, culminating in a program that uses a quintessential mathematical abstraction (complex numbers) to create visual representations of the famous Mandelbrot set. Lecture 10: Programming Languages. We conclude the course with an overview of important issues surrounding programming languages. To convince you that your knowledge of Java will enable you to learn other programming languages, we show implementations of a typical program in C, C++, Python, and Matlab. We describe important differences among these languages and address fundamental issues, such as garbage collection, type checking, object oriented programming, and functional programming with some brief historical context. Lecture 11: Searching and Sorting. Building on the scientific approach developed in Lecture 7, we introduce and study classic algorithms for two fundamental problems, in the context of realistic applications. Our message is that efficient algorithms (binary search and mergesort, in this case) are a key ingredient in addressing computational problems with scalable solutions that can handle huge instances. Lecture 12: Stacks and Queues. Our introduction to data structures is a careful look at the fundamental stack and queue abstractions, including performance specifications. Then we introduce the concept of linked structures and focus on their utility in developing simple, safe, clear, and efficient implementations of stacks and queues. Lecture 13: Symbol Tables. The symbol table abstraction is one of the most important and useful programmer's tools, s we illustrate with several examples in this lecture. Extending the scientific approach of the previous two lectures, we introduce and study binary search trees, a classic data structure that supports efficient implementations of this abstraction. Lecture 14: Introduction to Theory of Computation. The theory of computation helps us address fundamental questions about the nature of computation while at the same time helping us better understand the ways in which we interact with the computer. In this lecture, we introduce formal languages and abstract machines, focusing on simple models that are actually widely useful in practical applications. Lecture 15: Turing Machines. In 1936, Alan Turing published a paper that is widely hailed as one of the most important scientific papers of the 20th century. This lecture is devoted to the two far-reaching central ideas of the paper: All computational devices have equivalent computational power, and there are limitations to that power. Lecture 16: Intractability. As computer applications expanded, computer scientists and mathematicians realized that a refinement of Turing's ideas is needed. Which computational problems can we solve with the resource limitations that are inescapable in the real world? As described in this lecture, this question, fundamentally, remains unanswered. Lecture 17: A Computing Machine. Every programmer needs understand the basic characteristics of the underlying computer processor being used. Fortunately, the fundamental design of computer processors has changed little since the 1960s. In this lecture, we provide insights into how your Java code actually gets its job done by introducing an imaginary computer that is similar to both the minicomputers of the 1960s and the microprocessor chips found in today's laptops and mobile devices. Lecture 18: von Neumann Machines. Continuing our description of processor design and low-level programming, we provide context stretching back to the 1950s and discuss future implications of the von Neumann machine, where programs and data are kept in the same memory. We examine in detail the idea that we design new computers by simulating them on old ones, something that Turing's theory guarantees will always be effective. Lecture 19: Combinational Circuits. Starting with a few simple abstractions (wires that can carry on/off values and switches that can control the values carried by wires), we address in this lecture the design of the circuits that implement computer processors. We consider gates that implement simple logical functions and components for higher-level functions, such as addition. The lecture culminates with a full circuit for an arithmetic/logic unit. Lecture 20: CPU. In this lecture we provide the last part of our answer to the question "How does a computer work?" by developing a complete circuit for a computer processor, where every switch and wire is visible. While vastly different in scale, this circuit, from a design point of view, has many of the same characteristics as the circuits found in modern computational devices. Last modified on April 29, 2020. Copyright © 2000–2019 Robert Sedgewick and Kevin Wayne. All rights reserved.
