Structure and Interpretation of Computer Programs (SICP) is a classic textbook for learning how to program. The language used in the book is Scheme, a dialect of Lisp.
3
votes
1answer
51 views
SICP streams in C++
To brush up on my C++ chops, I've implemented a toy version of "SICP Streams", which behave like lists with one twist: the first element of the list is always available, the rest of the list is stored ...
4
votes
0answers
52 views
Building Data abstraction and ADT for rectangle using “objects”
For the below given exercise:
Exercise 7: Abstracting Rectangles
Implement a representation for rectangles in a plane. (Hint: You may want to make use of your procedures from exercise 5). ...
4
votes
1answer
42 views
Encapsulated state in clojure
While going through SICP and trying to implement the code in clojure, I've found that while I can get the code in chapter 3 to work, it seems to go against Clojure idioms, but I can't quite imagine ...
3
votes
2answers
88 views
This snippet of scheme calculates a value in pascal's triangle
I'm working through SICP and have implemented exercise 1.11 (Pascal's Triangle). What I'm curious about here is performance considerations by defining functions within the main function. I would ...
7
votes
2answers
370 views
My first accumulators
Notes
I'm working my way through SICP, and as I got very confused by the section on folds, I decided to try to implement foldr in scheme and javascript to understand how it works differently with ...
1
vote
0answers
143 views
SICP ex. 2.42 “eight queens puzzle”
The problem can be found online here.
In short, we're given the following function definition, that will recursively generate all the possible solutions for the "eight-queen-problem".
...
7
votes
2answers
162 views
Write a procedure stream-limit that finds
From SICP:
Exercise 3.64. Write a procedure
stream-limit that takes as arguments a
stream and a number (the tolerance).
It should examine the stream until it
finds two successive elements ...
1
vote
0answers
147 views
Write a definition of a semaphore in terms of test-and-set! operations
From SICP:
Exercise 3.47. A semaphore (of size
n) is a generalization of a mutex.
Like a mutex, a semaphore supports
acquire and release operations, but it
is more general in that up to n
...
1
vote
0answers
148 views
Write a definition of a semaphore in terms of mutexes
From SICP:
Exercise 3.47. A semaphore (of size
n) is a generalization of a mutex.
Like a mutex, a semaphore supports
acquire and release operations, but it
is more general in that up to n
...
3
votes
0answers
123 views
Representing a queue as a procedure with local state
From SICP:
Exercise 3.22. Instead of
representing a queue as a pair of
pointers, we can build a queue as a
procedure with local state. The local
state will consist of pointers to the
...
4
votes
1answer
213 views
Examine a list for cycles
From SICP:
Exercise 3.18. Write a procedure that
examines a list and determines whether
it contains a cycle, that is, whether
a program that tried to find the end
of the list by taking ...
1
vote
0answers
345 views
Correctly count the number of pairs in an irregular list structure
From SICP:
For background, here is exercise 3.16:
Exercise 3.16
Ben Bitdiddle decides
to write a procedure to count the
number of pairs in any list structure.
...
1
vote
1answer
241 views
Order of evaluation of function arguments
From SICP:
Exercise 3.8
When we defined the
evaluation model in section 1.1.3, we
said that the first step in evaluating
an expression is to evaluate its
subexpressions. But we never ...
1
vote
0answers
149 views
Coercion of arguments using successive raising
From SICP:
Exercise 2.84
Using the raise
operation of exercise 2.83, modify the
apply-generic procedure so that it
coerces its arguments to have the same
type by the method of ...
1
vote
0answers
313 views
Coercion with multiple arguments
From SICP:
Exercise 2.82
Show how to generalize
apply-generic to handle coercion in
the general case of multiple
arguments. One strategy is to attempt
to coerce all the arguments to ...
2
votes
1answer
645 views
Huffman encoding successive-merge function
From SICP:
Exercise 2.69. The following
procedure takes as its argument a list
of symbol-frequency pairs (where no
symbol appears in more than one pair)
and generates a Huffman encoding ...
1
vote
1answer
684 views
Encode-symbol for Huffman tree
From the text:
Exercise 2.68. The encode procedure
takes as arguments a message and a
tree and produces the list of bits
that gives the encoded message.
...
2
votes
1answer
311 views
Search on a binary tree
From SICP:
Exercise 2.66. Implement the lookup
procedure for the case where the set
of records is structured as a binary
tree, ordered by the numerical values
of the keys.
I wrote the ...
2
votes
0answers
819 views
Union-set intersection-set for a binary-tree implementation of sets
From SICP:
Exercise 2.65
Use the results of
exercises 2.63 and 2.64 to give (n)
implementations of union-set and
intersection-set for sets implemented
as (balanced) binary trees.41
...
1
vote
0answers
312 views
Union-set for ordered representation
From SICP:
Exercise 2.62. Give a (n)
implementation of union-set for sets
represented as ordered lists.
I wrote this answer:
...
1
vote
1answer
231 views
Adjoin-set for an ordered set representation
From SICP:
Exercise 2.61
Give an implementation
of adjoin-set using the ordered
representation. By analogy with
element-of-set? show how to take
advantage of the ordering to produce a
...
4
votes
1answer
172 views
Set representation allowing duplicates
From SICP:
Exercise 2.60. We specified that a
set would be represented as a list
with no duplicates. Now suppose we
allow duplicates. For instance, the
set {1,2,3} could be represented as
...
1
vote
0answers
1k views
Union-set operation for unordered-list representation of sets
One way to represent a set is as a
list of its elements in which no
element appears more than once. The
empty set is represented by the empty
list. In this representation,
element-of-set? ...
1
vote
0answers
343 views
Standard Algebraic Derivative Calculator
I had some difficulty with this problem, so I'm sure there is a better way. Here is the question from SICP:
Exercise 2.58
Suppose we want to
modify the differentiation program so
that it ...
3
votes
1answer
227 views
Extend sums and products functions
Exercise 2.57. Extend the
differentiation program to handle sums
and products of arbitrary numbers of
(two or more) terms. Then the last
example above could be expressed as
...
0
votes
1answer
108 views
Extending basic differentiator to handle more kinds of expressions
Exercise 2.56. Show how to extend the
basic differentiator to handle more
kinds of expressions. For instance,
implement the differentiation rule
by adding a new clause to the deriv
...
0
votes
1answer
590 views
Define the equal? predicate
Exercise 2.54
Two lists are said to
be equal? if they contain equal
elements arranged in the same order.
For example,
...
1
vote
1answer
181 views
Adding, subtracting, and multiplying a vector by a scalar
Exercise 2.46. A two-dimensional
vector v running from the origin to a
point can be represented as a pair
consisting of an x-coordinate and a
y-coordinate. Implement a data
abstraction ...
1
vote
1answer
159 views
Writing a general purpose “split” function (for SICP's imaginary language)
From SICP 2.2.4:
The textbook has already defined a function (right-split ...) as follows:
...
4
votes
3answers
864 views
Eight-queens puzzle
Figure 2.8: A solution to the
eight-queens puzzle. The
``eight-queens puzzle'' asks how to
place eight queens on a chessboard so
that no queen is in check from any
other (i.e., no two ...
6
votes
3answers
803 views
Find all distinct triples less than N that sum to S
Exercise 2.41. Write a procedure to
find all ordered triples of distinct
positive integers i, j, and k less
than or equal to a given integer n
that sum to a given integer s.
...
0
votes
1answer
219 views
Defining a unique-pairs procedure
From the section called Nested Mappings
Exercise 2.40
Define a procedure
unique-pairs that, given an integer n,
generates the sequence of pairs (...
4
votes
2answers
874 views
Reverse in terms of fold-right and fold-left
Exercise 2.39
Complete the following definitions of reverse
(exercise 2.18) in terms of fold-right
and fold-left from exercise 2.38:
...
4
votes
1answer
2k views
Matrix multiplication and dot-product
Exercise 2.37. Suppose we represent
vectors v = (vi) as sequences of
numbers, and matrices m = (mij) as
sequences of vectors (the rows of the
matrix). For example, the matrix
is ...
4
votes
1answer
350 views
Redefine count-leaves as an accumulation
Exercise 2.35. Redefine count-leaves
from section 2.2.2 as an accumulation:
...
4
votes
1answer
840 views
Abstract tree-map function
Exercise 2.31. Abstract your answer
to exercise 2.30 to produce a
procedure tree-map with the property
that square-tree could be defined as
...
1
vote
1answer
223 views
Square-tree using maps and recursion
Define a procedure square-tree analogous to the
square-list procedure of exercise
2.21. That is, square-list should behave as follows:
...
0
votes
1answer
454 views
Producing a deep-reverse procedure
Exercise 2.27
Modify your reverse
procedure of exercise 2.18 to produce
a deep-reverse procedure that takes a
list as argument and returns as its
value the list with its elements
...
1
vote
2answers
1k views
A definition of for-each
Exercise 2.23
The procedure for-each
is similar to map. It takes as
arguments a procedure and a list of
elements. However, rather than forming
a list of the results, for-each just
...
1
vote
2answers
740 views
Filter a list of integers by parity
Exercise 2.20
The procedures +, *,
and list take arbitrary numbers of
arguments. One way to define such
procedures is to use define with
dotted-tail notation. In a procedure
...
1
vote
2answers
2k views
Design a procedure to reverse a list
SICP exercise 2.18 asks the following:
Exercise 2.18. Define a procedure
reverse that takes a list as argument
and returns a list of the same
elements in reverse order:
...
1
vote
1answer
165 views
A more efficient mul-interval
From 2.11
Exercise 2.11. In passing, Ben also
cryptically comments: ``By testing the
signs of the endpoints of the
intervals, it is possible to break
mul-interval into nine cases, only ...
1
vote
1answer
220 views
Interval Subtraction
From the Extended Exercise beginning in section 2.1.4, you can find exercise 2.8:
Exercise 2.8. Using reasoning
analogous to Alyssa's, describe how
the difference of two intervals may be
...
1
vote
1answer
731 views
Church Numerals - implement one, two, and addition
Given the following exercise:
Exercise 2.6
In case representing
pairs as procedures wasn't
mind-boggling enough, consider that,
in a language that can manipulate
procedures, we can ...
0
votes
1answer
273 views
Represent pairs of nonnegative integers using 2^a * 3^b
Given the following exercise:
Exercise 2.5
Show that we can
represent pairs of nonnegative
integers using only numbers and
arithmetic operations if we represent
the pair a and b as ...
1
vote
1answer
356 views
Midpoint of a segment
From SICP:
Exercise 2.2
Consider the problem of
representing line segments in a plane.
Each segment is represented as a pair
of points: a starting point and an
ending point. Define a ...
1
vote
1answer
294 views
Make a version of make-rat that handles positive and negative arguments
Given the following task from SICP
Exercise 2.1
Define a better version
of make-rat that handles both positive
and negative arguments. Make-rat
should normalize the sign so that if
...
1
vote
1answer
188 views
Compute e using Euler's expansion
Given the following task:
Exercise 1.38. In 1737, the Swiss
mathematician Leonhard Euler published
a memoir De Fractionibus Continuis,
which included a continued fraction
expansion for e ...
0
votes
2answers
759 views
Infinite Continued Fraction - iterative and recursive
Given the following exercise:
Exercise 1.37. a. An infinite
continued fraction is an expression of
the form
As an example, one can show that the
infinite continued fraction ...
1
vote
3answers
874 views
Filtered-Accumulate
Given the following task:
Exercise 1.33
You can obtain an even
more general version of accumulate
(exercise 1.32) by introducing the
notion of a filter on the terms to be
combined. ...
