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.
1
vote
0answers
116 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".
(define ...
5
votes
1answer
125 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
128 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
123 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
...
2
votes
0answers
94 views
[SICP ex. 3.22] represent 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
...
3
votes
1answer
144 views
SICP ex. 3.18 - Write a program to 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
157 views
[SICP ex. 3.17] 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.
It's easy,'' he reasons.The
...
1
vote
1answer
149 views
[SICP ex. 3.8] 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
99 views
[SICP ex. 2.84] 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 successive
...
1
vote
0answers
236 views
(scheme [SICP ex. 2.82] 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 the
...
1
vote
1answer
363 views
Huffman encoding successive-merge function [SICP ex. 2.69]
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
322 views
(Encode-symbol …) for Huffman tree [SICP ex. 2.68]
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.
(define (encode message tree)
...
2
votes
1answer
202 views
Lookup (search) on a binary tree [SICP ex. 2.66]
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
622 views
Union-set intersection-set for a binary-tree implementation of sets [SICP ex. 2.65]
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
I ...
1
vote
1answer
220 views
(scheme) [SICP ex. 2.62] 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:
(define (union-set set1 set2)
(cond ((null? set1) set2)
...
1
vote
1answer
132 views
(scheme) [SICP ex. 2.61] 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
...
2
votes
1answer
138 views
(scheme) [SICP ex. 2.60] 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
1answer
328 views
(Scheme) [SICP ex. 2.59] union-set
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
213 views
Standard Algebraic Derivative Calculator [SICP ex. 2.58 part b]
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 ...
1
vote
1answer
147 views
(Scheme) [SICP ex. 2.57] Extend sums and products functions without changing deriv function
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
(deriv '(* ...
0
votes
1answer
78 views
(Scheme) [SICP ex. 2.56] Extend Differentiator
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
283 views
(Scheme) [SICP ex. 2.54] Define equal?
Exercise 2.54. Two lists are said to
be equal? if they contain equal
elements arranged in the same order.
For example,
(equal? '(this is a list) '(this is a list))
is true, but
...
1
vote
2answers
101 views
(scheme) [SICP ex. 2.46] add-vect, sub-vect, scale-vect
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
110 views
(Scheme ) [SICP ex. 2.45] Write 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:
(define (right-split painter n)
(if (= n 0)
painter
(let ((smaller (right-split painter (- n ...
3
votes
4answers
421 views
(Scheme) [SICP ex. 2.42] eight-queens puzzle - help me fix my popsicle-stick-bridge solution!
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 ...
5
votes
4answers
636 views
(Scheme) [SICP ex. 2.41] 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.
(define ...
0
votes
1answer
110 views
(Scheme) [SICP ex. 2.40] unique-pairs
From the section called Nested Mappings
Exercise 2.40. Define a procedure
unique-pairs that, given an integer n,
generates the sequence of pairs (i,j)
with 1< j< i< n. Use ...
3
votes
2answers
413 views
(scheme) [sicp ex. 2.39] 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:
(define (reverse sequence)
(fold-right (lambda (x ...
1
vote
2answers
1k views
(Scheme) [SICP ex. 2.37 Matrix Multiplication
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 ...
0
votes
1answer
216 views
(Scheme) [SICP ex. 2.35] Redefine count-leaves as an accumulation
Exercise 2.35. Redefine count-leaves
from section 2.2.2 as an accumulation:
(define (count-leaves t) (accumulate
<??> <??> (map <??> <??>)))
I wrote the ...
1
vote
2answers
606 views
(Scheme) [SICP ex. 2.31] 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
(define (square-tree tree) (tree-map
square ...
0
votes
1answer
136 views
(Scheme) [SICP ex. 2.30 square-tree
Exercise 2.30. Define a procedure
square-tree analogous to the
square-list procedure of exercise
2.21. That is, square-list should behave as follows:
(square-tree (list 1
(list 2 ...
0
votes
1answer
310 views
(scheme) [SICP ex. 2.27] deep-reverse
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
...
0
votes
1answer
446 views
(Scheme) [SICP ex. 2.23] 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
...
0
votes
3answers
545 views
(Scheme) [SICP ex. 2.20] 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
definition, ...
0
votes
2answers
450 views
(scheme) [SICP ex. 2.18] 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:
(reverse (list 1 4 ...
1
vote
1answer
127 views
[SICP ex. 2.11] 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 ...
0
votes
1answer
152 views
(Scheme) [SICP ex. 2.8] 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
...
0
votes
1answer
342 views
(Scheme) [SICP ex. 2.6] 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 get ...
0
votes
1answer
178 views
(Scheme) [SICP ex. 2.5] 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 the ...
1
vote
1answer
218 views
(Scheme) [SICP ex. 2.2] 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
128 views
(Scheme) [SICP ex. 2.1] 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
the ...
1
vote
1answer
123 views
(Scheme) [SICP ex. 1.38] Compute e usine 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
341 views
(scheme) [SICP ex. 1.37] 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 expansion
...
0
votes
3answers
610 views
(Scheme) [SICP ex. 1.33] 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. That ...
0
votes
1answer
415 views
(Scheme) [SICP ex. 1.32] Show that Sum and Product are both examples of Accumulation
Given this task:
Exercise 1.32. a. Show that sum and
product (exercise 1.31) are both
special cases of a still more general
notion called accumulate that combines
a collection of terms, ...
0
votes
1answer
482 views
(Scheme) [SICP ex. 1.29] Integral using Simpson's Rule
As an answer to this problem:
Exercise 1.29. Simpson's Rule is a
more accurate method of numerical
integration than the method
illustrated above. Using Simpson's
Rule, the integral of a ...
0
votes
1answer
382 views
[SICP ex. 1.30] Iterative Sum
Given the following recursive definition of sum:
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
And the task:
Exercise 1.30. The ...
