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
