We begin to consider the content and structure of the course. We also prepare ourselves to use our laboratory environment (that is, the Linux workstations and the DrRacket Programming Environment).
We consider documentation for your programs: Why to write documention, when to write documentation, how to write documentation. We also explore the 6P style of documentation that we use in this course.
We consider a new type and its use in selecting elements from lists.
We consider how and why to name values within procedures.
We consider your work on exam 1.
We consider a different form of recursion, one based on the construction of recursive helper procedures that take additional parameters. Along the way, we consider the idea of tail recursion. We also explore how careless design of recursive procedures can inadvertently lead to slow execution.
We consider a slightly different kind of recursion, numeric recursion. In this technique, we once again have procedures call themselves. However, the parameter that we “simplify” at every step is a number, rather than a list.
We consider vectors, an alternative to lists for storing collections of data.
We revisit files, considering the lower-level operations for working with files, a technique for structuring information that permits the information to persist across invocations of Scheme. Files also let our Scheme programs share information with other programs.
We revisit the topic of higher-order procedures, one of the most
important techniques in languages like Scheme. Higher-order procedures
are procedures – like
compose – that take
other procedures as parameters, return other procedures as values, or
We consider trees, structures built from pairs. Trees are somewhat like two-dimensional lists.
We explore techniques for analyzing the number of calls made in evaluating procedures, particularly recursive procedures. We consider why such analysis is useful.
We consider association lists, a simple, but useful, technique for organizing tables of information.
We introduce the project.
We provide time for groups to work on their projects.
We consider the general problem of searching. We explore binary search, one of the most efficient algorithms for searching.
We explore the problem of sorting. When you sort a list, vector, or other collection, you put the elements in order. The order of the elements usually corresponds to the type of the elements. We might sort strings alphabetically, grades numerically, colors by brightness, and so on and so forth.
We provide additional time for groups to work on their projects.
We move from our general exploration of sorting to the implementation of a particular sorting algorithm, insertion sort. We also explore how the running time for that algorithm varies based on the number of values we are sorting.
We will have some additional time to work on projects before the project deadline.
We continue our exploration of sorting by considering the applicability of the divide-and-conquer approach to the problem of sorting. We look at one particular divide-and-conquer algorithm, merge sort. We explore how the running time for that algorithm varies based on the number of values we are sorting.
We explore your projects.
We conclude the course by considering the topics we’ve covered, and discuss the concepts you will see in future CS courses.