# SEE

## Lecture 20 - Car-Cdr Recursion Problem that Returns the Sum of Every Element in a List of Integers

Expand/Collapse Video
• Bookmarks
• 00:00:36

Car:Cdr Recursion Problem That Returns The Sum Of Every Element In A List Of Integers, How Scheme Checks Type During Run:Time Rather Than Compilation

• 00:07:15

Recursive Implementation Of The Fibonacci Function In Scheme

• 00:11:34

Example That Illustrates Runtime Error/Type Checking Vs. Compile:Time Error/Type Checking

• 00:14:46

Writing A Recursive Flatten Function That Removes All The Intervening Parentheses From A List

• 00:21:20

Using A Cond Structure To Branch Over The Various Recursive Cases In The Flatten Function, Using The Else Statement To Make Sure That Cond Always Returns Something

• 00:29:43

Writing The Sorted? Function For A List Of Integers, Using The Or Function To Handle The Base Case Logic And Cadr As Shorthand For The Second Element

• 00:37:53

Using < And <= With Multiple Arguments In Scheme

• 00:39:23

Function Pointers In Scheme, How Function Data Is Stored Like A Linked List In Scheme And Function Names Are Linked To Code In A Symbol Table

• 00:45:07

Generalizing The Sorted? Function By Passing In A Comparison Function As The Second Parameter

Show All

## Course Description

Advanced memory management features of C and C++; the differences between imperative and object-oriented paradigms. The functional paradigm (using LISP) and concurrent programming (using C and C++). Brief survey of other modern languages such as Python, Objective C, and C#.

Prerequisites: Programming and problem solving at the Programming Abstractions level. Prospective students should know a reasonable amount of C++. You should be comfortable with arrays, pointers, references, classes, methods, dynamic memory allocation, recursion, linked lists, binary search trees, hashing, iterators, and function pointers. You should be able to write well-decomposed, easy-to-understand code, and understand the value that comes with good variable names, short function and method implementations, and thoughtful, articulate comments.

## Instructor

Cain, Jerry

Jerry Cain is a lecturer at Stanford University in the Computer Science Department.

## Handouts

Lecture 1
 Course Information Course Syllabus
Lecture 2
 Introducing the STL Unix Basics Computer Architecture Arrays the Full Story
Lecture 3
Lecture 4
 No handouts
Lecture 5
Lecture 6
Lecture 7
 No handouts
Lecture 8
 Computer Architecture Simple Code Generation
Lecture 9
 No handouts
Lecture 10
 Function Call and Return Code Generation Examples Factorial Trace
Lecture 11
 No handouts
Lecture 12
 No handouts
Lecture 13
 No handouts
Lecture 14
 No handouts
Lecture 15
Lecture 16
 No handouts
Lecture 17
Lecture 18
 No handouts
Lecture 19
 Introduction to Scheme Scheme Functions
Lecture 20
 No handouts
Lecture 21
 Functions as Data Scheme Examples
Lecture 22
 No handouts
Lecture 23
 No handouts
Lecture 24
Lecture 25
Lecture 26
 No handouts
Lecture 27
 No handouts

## Resources

### Tutorials:

 Assorted Anecdotes and Advice - Created by course TA Aman Kumar Quick and Dirty Purify Tutorial - Created by course TA Aman Kumar Purify Errors - Most common Purify error messages

### Other Resources:

 Unix Reference Documentation xemacs Command Reference vi Command Reference gdb Command Reference Java and Eclipse C and C++ Standard Library Reference Dinkumware C++ Library Reference The Kawa Language Framework The Scheme Programming Language Online Python Tutorial Java 1.5 Documentation

## Exams

 Practice Midterm Questions Solutions Midterm Questions Solutions Practice Final Questions Solutions

Show All

## Lecture 2

 Watch Online: Download: Right Click, and Save As Duration: 51 min Topics: C/C++ Data Types - Interpretations, Sizes, Bits- How Bytes are Broken Up into Bits, Breaking Up a Character's Decimal Value into its Underlying Bit Structure, Shorts - Interpreting Data that Consists of More Than One Byte, Representations of Negative Numbers, The Sign Bit, Two's Complement Addition, Converting Between Chars and Shorts, How the Bit Representation is Transferred, Converting Between ints and shorts, Sign Extending During Conversion, Floats, Converting Between Integers and Floats

## Lecture 3

 Watch Online: Download: Right Click, and Save As Duration: 53 min Topics: Converting Between Types of Different Sizes and Bit Representations Using Pointers, Little Endian vs. Big Endian, Structs: How the Data of a Struct is Stored, Accessing the Data of a Struct, Arrays, Pointer Arithmetic on Arrays, Result of Casting Arrays to Different Types, Layout in Memory of Structs, Dynamically Allocated Strings in C vs. Arrays of Characters, Modifying Internal Data of Structs Using strcpy, Character Arrays and cout, Generic Functions in C Using Memory and Pointers

## Lecture 4

 Watch Online: Download: Right Click, and Save As Duration: 51 min Topics: Creating a Generic Swap Function for Data Types of Arbitrary Size, Void* Type for Generic Pointers, Implementation of Swap Function Using memcpy, Client Interface to Generic Swap Function, Pros and Cons of C Generics vs. C++ Generics, Errors Resulting from Improper Use of C Generic Swap Function that Compile, Swapping Pointers, Pitfalls when Swapping Pointers Using Generics, Implementing a Generic Linear Search, Implementing a Generic Linear Search, Using Casts and Pointer Arithmetic, Comparing Memory Blocks Using memcmp or a Comparison Function

## Lecture 5

 Watch Online: Download: Right Click, and Save As Duration: 52 min Topics: Generic Lsearch - Prototype, Comparison Function, Implementation, Casting Void*S to Char*S to Compute Byte Offsets, Client Use of Generic Lsearch, Example of a Comparison Function for Integers, More Complicated Data Types and Lsearch- Example Using C-Strings, Comparison Function for Two C-Strings, With Arguments that Represent Char**S, Comparison Functions Where the Key is a Different Type than the Second Argument, Using a Pointer to a Struct as a Key in Order to Access Additional Data in a Comparison Function, Functions Vs. Methods, C Data Structures - Implementing a Non-Generic Stack of Integers, C Stack Interface, Implementation, Preallocating Memory, Client Use of C Stack, State of Internal Memory of the Stack, Growth of Memory when Stack Becomes Too Large, Implementation of Stacknew, Asserts

## Lecture 6

 Watch Online: Download: Right Click, and Save As Duration: 51 min Topics: Integer Stack Implementation - Constructor and Destructor, Stackpush Implementation, Reallocation of Memory when Stack Grows Too Big Using Realloc, How Memory is Copied Using Realloc, Stackpop Implementation, Reimplementing the Stack Interface as a Generic Data Structure, Generic Implementation of StackNew, Generic Implentation of Stackpush Using Memcpy, Stackgrow Implementation, Static (Internal) Functions, Generic Stackpop Implementation Using Memcpy, Where it is the Responsibility of the Caller to Allocate the Memory Where the Popped Element is Stored.

## Lecture 7

 Watch Online: Download: Right Click, and Save As Duration: 53 min Topics: Problems with Ownership of Memory, How Default Implementation of Stackdispose Does Not Free Dynamically Allocated Data, Adding a Free Function to the Stack Implementation, Rewriting Stackdispose to Incorporate It, Writing a Free Function for a Stack of C-Strings, Pitfalls When Writing Such Functions, C Library Functions for Assignment 3 - Memmove (Memcpy That Can Copy Using Two Regions That Overlap), Example of Rotate Function, C Qsort Function, Global Layout of Memory - Stack Segment, Heap Segment, How the Heap Manager Allocates And Frees Memory on the Heap, Underlying Linked List of Free Node Information

## Lecture 8

 Watch Online: Download: Right Click, and Save As Duration: 51 min Topics: Heap Management - How Information about Allocations are Stored in the Heap, Result of Freeing Memory Improperly, Actual Sizes of Heap Allocations - Nearest Power of 2, Management of Free Blocks on the Heap by Storing Addresses in the Blocks of Free Memory, Algorithms for Choosing Which Free Block to Allocate, How the Heap's Free List Can Be Updated When Memory is Freed, How Adjacent Free Blocks Are Combined To Avoid Fragmentation, Compacting the Heap By Using Handles, Stack Segment Layout, Allocation of Local Variables on the Stack by Decrementing the Stack Pointer, Activation Records and State of the Stack Pointer During Nested Function Calls, Assembly Code and the Code Segment, RAM, Registers, and the ALU, Example That Demonstrates How an Arithmetic Expression is Translated Into Register Operations

## Lecture 9

 Watch Online: Download: Right Click, and Save As Duration: 52 min Topics: How a Code Snippet is Translated into Assembly Instructions, Store, Load, and ALU Operations, Assembly Optimizations for 4-Byte Addresses, Context-Insensitive Code Translation, Overriding the 4-Byte Default in Assembly Instructions, Translating a For Loop into Assembly, Using Branch Instructions and the PC Register, Pointer/Array Arithmetic in Assembly, Unconditional Branch Instructions (Jumps), How a 4-Byte Assembly Instruction is Encoded in Memory

## Lecture 10

 Watch Online: Download: Right Click, and Save As Duration: 49 min Topics: More Detail about Activation Records - Layout of Memory During a Function Call, How the Return Address of a Function is Stored on the Stack, Example Showing How an Activation Record is Constructed on the Stack, Setting Up Function Parameters on the Stack, Using the Call Instruction to Jump to the Function, Cleaning Up at the End of a Function and Using the RET Instruction and the Saved Return Address to Return to the Original Function, General Layout of an Activation Record, Who Sets Up Each Part of the Activation Record, Assembly Code Translation of the Factorial Function, How Recursion Translates into Assembly, Why Registers Need to be Reloaded After Other Functions Are Called, Animation Demonstrating the Assembly Execution for the Factorial Function

## Lecture 11

 Watch Online: Download: Right Click, and Save As Duration: 52 min Topics: Moving from C Code Generation to C++ Code Generation: Basic Swap Example, Code Generation for the Pointer Swap Function, Code Generation for the C++ Version Of Swap Using References, Which Are Treated as Automatically Dereferenced Pointers, Local Variables Declared as References, Difference Between References and Pointers, Effect Of Declaring a Class on Memory in the Stack, Class Methods, Which Take a "This" Pointer as An invisible First Parameter, Effect Of the "This" Pointer on the Activation Record for a Class Method, Static Class Methods (Standalone Functions), Which Don't Contain a "This" Pointer, Compilation and Linking - #Define and the Preprocessor

## Lecture 12

 Watch Online: Download: Right Click, and Save As Duration: 50 min Topics: Preprocessing Commands - #Define as a Glorified Find and Replace, Preprocessing Macros - Preprocessor Commands With Arguments, Example of Macro Usage in the Vector assignment to Calculate the Address of the Nth Element, Assert Macro Implementation, How Asserts are Stripped Out for the Final Product Using #Ifdef and #Define, C Macro Drawbacks When Given More Complex Arguments, #Include as a Search and Replace Operation, < > Vs. " ", Output to the Compiler After Preprocessing, How to View the Output of the Preprocessor Using Gcc, How to Avoid Circular #Include Loops Using #Ifndef, #Define, and #Endif, Visual Representation of the Result of Preprocessing (The Translation Unit) that Is Passed to the Compiler to Create a .O File, An Example Illustrating the Preprocessing and Compilation of a Simple Program

## Lecture 13

 Watch Online: Download: Right Click, and Save As Duration: 52 min Topics: Review of Compilation Process of a Simple Program Into a .O File, Effect of Commenting Out a C Standard Library .H File on the Resulting Translation Unit, How Gcc Infers a Prototype When None Is Found and the .O File Remains the Same, How the Gcc Linker Is Able to Link Standard Library Files Without a #Include, The (Similar) Result When the .H File with Malloc's Prototype Is Not Included, How Commenting Out Assert.H Creates Different Results, Failing In the Linker Since Assert Is a Macro, As Opposed to a Function In the Standard Libraries, Effect of Calling Strlen with the Wrong Number of Arguments on the Compilation/Linking Process, Effect of Calling Memcmp with too Few Arguments on the Compilation/Linking Process, How C++ Disambiguates Between Different Function Prototypes to Avoid the Problems Posed By the Previous Two Examples, Debugging Information - Seg Faults (Usually Dereferencing a Bad Pointer) Vs. Bus Errors (Dereferencing Data that Isn't Correctly Aligned), Debugging Example Where Overflowing an Integer Array Leads to an Infinite Loop, Similar Example with a Short Array that Works Differently on Big-Endian Systems Vs. Little-Endian Systems, Example Where an Array Overflow Overwrites the Saved PC and Leads to an Infinite Loop

## Lecture 19

 Watch Online: Download: Right Click, and Save As Duration: 52 min Topics: Imperative/Procedural Paradigms (C) and Object-Oriented Paradigm(C++), Introduction to the Functional Paradigm (Scheme), Which Is Based on Synthesizing the Return Values of Functions, Example of a Scheme Function Definition that Converts Celsius to Fahrenheit, Scheme Environment (Kawa) Details, Scheme Primitives, Scheme Lists, Expressing Functions and Function Calls as Lists, Function Examples: <, >, and, Scheme List Operations: Car and Cdr, Distinguishing Between Lists and Functions with ', Origin of the Names "Car" and "Cdr", The Cons Function, Which Constructs a New List by Prepending the First Argument to the Second Element (Which Must Be a List), The Append Function, Which Concatenates Two Or More Lists, Defining Our Own Add Function, "Define" as an Operation in Scheme with Side Effects, Run-Time Error Checking in Scheme, Writing a Recursive Function that Sums All of the Numbers in a List

## Lecture 20

 Watch Online: Download: Right Click, and Save As Duration: 52 min Topics: Car-Cdr Recursion Problem that Returns the Sum of Every Element in a List of Integers, How Scheme Checks Type During Run-Time Rather than Compilation, Recursive Implementation of the Fibonacci Function in Scheme, Example that Illustrates Runtime Error/Type Checking Vs. Compile-Time Error/Type Checking, Writing a Recursive Flatten Function that Removes All the Intervening Parentheses from a List, Using a Cond Structure to Branch Over the Various Recursive Cases in the Flatten Function, Using the Else Statement to Make Sure that Cond Always Returns Something, Writing the Sorted? Function for a List of Integers, Using the Or Function to Handle the Base Case Logic And Cadr As Shorthand for the Second Element, Using < And <= With Multiple Arguments in Scheme, Function Pointers in Scheme, How Function Data Is Stored Like a Linked List in Scheme And Function Names Are Linked to Code in a Symbol Table, Generalizing the Sorted? Function By Passing in a Comparison Function as the Second Parameter

## Lecture 21

 Watch Online: Download: Right Click, and Save As Duration: 50 min Topics: Introduction to the Kawa Development Environment: Evaluation of Expressions, Loading Function Definitions From a .Scm File, Mapping Arbitrary Unary Functions Over Lists in Scheme Using the Map Operation, Mapping List Functions (Car, Cdr) Over Lists of Lists, Using Mapping Functions with More than One Input by Passing Multiple Lists into Map, Implementing the Unary Version of Map Using Recursion, Apply, Which Allows You to Specify a Function to Be Prepended to a List of Arguments and Be Evaluated, and Eval, Which Evaluates a List as Though it Were Typed into the Commandline, Using Apply to Implement an Average Function Wihtout Recursion, How Eval Can Be Used to Apply Non-Functions Like 'And' and 'Define' to a List, or to Evaluate a Complicated Expression Created While the Program Is Running, Revisiting Flatten Using Map and Apply, Writing a Flatten Implementation That Maps Itself Over Each of its Elements and Appends Each of the Results Together Using Apply, Implementing a Translate Function, Which Shifts Each Point in a List of Points by a Certain Delta, How a Typical Mapping Function Is Not Usable Because of its Need for Client Data, Using the Lambda Function to Define a Nameless Function On the Fly, Which Can Access the Delta Value Since it Is Constructed within the Translate Function, Defining Functions within Functions as an Alternative to Using Lambda, How the Define Keyword Implicitly Uses the Lambda Keyword to Associate a Name with a Function

## Lecture 22

 Watch Online: Download: Right Click, and Save As Duration: 53 min Topics: Writing a Recursive Power Set Function in Scheme, Using a Lambda Mapping Function that Cons-Es the Car to Every Element in the Power-Set of the Cdr to Make the Recursive Step in the Power-Set Function, Using a Let Binding to Cause Power-Set to Only Make One Recursive Call Rather than Two, Structure of a Let Binding, How Expressions Within a Let Binding Cannot Depend On Each Other Unless the Let* Keyword Is Used, How a Let Binding Is Compiled to the Evaluation of a Lambda Expression, Writing a Permute Function, Which Prints Out a List of All Permutations of a Given List, Writing a Permute Function, Which Prints Out a List of All Permutations of a Given List, Writing the Overall Algorithm For the Permutation Function, Which Maps a Function Over Each Element in the List that Produces Each Permutation Starting With that Element, then Appends the Results Together, Writing the Mapping Function For the Permute Function, Which Maps Another Function (That Simply Conses the Current Element) to Each Permutation of the List of Elements when the Current Element Is Removed, Coding Without Side Effects and Immutability of Lists in Scheme, Memory Allocation in Scheme and the Read-Eval-Print Loop, How Integers, Strings, and Lists Are Laid Out in Memory when They Are Typed into the Scheme Command Line

## Lecture 23

 Watch Online: Download: Right Click, and Save As Duration: 50 min Topics: Scheme Memory Model - How Scheme Instructions Synthesize Linked Lists Behind the Scenes and Perform Operations on Them, Two Different Ways of Laying Out A List In Memory, One With Memory Aliasing and One Without, The Scheme Equivalent of "..." (Functions With Multiple Arguments), Writing A Generic Map Function, Modifying the Unary-Map Function to Handle Multiple Arguments By Adding A . to the List of Arguments, Extending Unary-Map to An N-Ary Map Implementation Using ., Sample Trace of the N-Ary Map Function, Garbage Collection In Scheme, How Care Must Be Taken When Reclaiming Global Variables to Ensure That They Won't Be Needed Later, High-Level Mechanics of Garbage Collection: Reference Counts, or Sweeping Through the Data and Marking All Reachable Data, Then Freeing the Rest, Other Functional Languages: Scheme, ML, Haskell, Erlang

## Lecture 24

 Watch Online: Download: Right Click, and Save As Duration: 49 min Topics: Overarching Features of Python: Scripting Language, Imperative, Object-Oriented, Functional, More Python Overview - Dynamic Typing, Use of Whitespace and Tabs, Python Environment, Execution of Basic Statements, Calling Methods Using Objects (And Anonymous Objects Like String Literals), Evaluating Assignments, Python Strings, String Methods, and Lists/Sublists (Including Index Wrapping), Strings as Lists of Characters in Python, Replacing Characters Within a List, Mutable Lists Vs. Immutable Lists, Writing the Gatherdivisors Function, Which Lists All the Divisors of the inputted Numbers: Function/Line Syntax (Incl. Tabs), for Loop Syntax and Iterables, Using and Importing Python Modules, Python Dictionaries, Adding and Retrieving Data from Dictionaries, How Heterogeneous Data Is Allowed inside Dictionaries, Look Ahead: Python Libraries, More About Dictionaries

## Lecture 25

 Watch Online: Download: Right Click, and Save As Duration: 49 min Topics: Rewriting RSG to Illustrate all Three Paradigms and Lambdas in Python, How Objects Are Implemented in Python, Python Dictionary Implementation, Writing an RSG Grammar in Python Using A Dictionary and Lists, Expanding the Start Terminal Using all Three Paradigms at Once, Changing the Expand Function to A Binary Function, Modifying the Map to Use A Python Lambda Function As A Result, Python Object Model From A Memory Standpoint, How Objects Are Passed By Reference and How Lists Are Copied, How to Make A Deeper Copy of an Object in Python Using Copy or Deepcopy, Objects and Classes in Python, How They Are Stored As Dictionaries, Example of A Class Constructor and How it Creates Initializes the Class's Data, Rest of the Python Lexicon Implementation, Python Object Interface, Accessing the Underlying Dictionay of an Object, Inserting New Values into an Object's Underlying Dictionary

## Lecture 26

 Watch Online: Download: Right Click, and Save As Duration: 50 min Topics: XML Processing and Python - Two Different XML Processing Models, Example XML Fragment, How an XML Parser Uses Tag Handlers to Break Up an XML Stream, How Python Can Parse XML Streams Using Urlopen, Make_Parser, and Contenthandler, Defining a Listfeedtitles Function that Takes in a URL and Parses it Using a Parser and an Rsshandler, Contenthandler Interface, Implementing The Rsshandler Class, Which Subclasses Contenthandler, to Fit The Specific Goals of The RSS Feed Reader, Implements The Rsshandler So that it Only Prints Data that Lies Within a Title Tag, Looking at an Actual RSS Feed in Firefox and Through Telnet, Looking at an XML Document with a Tree-Based XML Renderer Rather Than a Stream-Based Parser, Advantages of this Approach