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.
8
votes
3answers
886 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.
...
7
votes
2answers
423 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 ...
7
votes
2answers
4k views
Sum of squares of two largest of three numbers
Given the following problem (SICP Exercise 1.3):
Define a procedure that takes three
numbers as arguments and returns the
sum of squares of the two largest
numbers.
I wrote the following (...
7
votes
2answers
167 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 ...
6
votes
3answers
1k 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
1answer
411 views
Redefine count-leaves as an accumulation
Exercise 2.35. Redefine count-leaves
from section 2.2.2 as an accumulation:
...
5
votes
3answers
355 views
SICP Exercise 1.3: Sum of squares of two largest numbers out of three
The exercise 1.3 of the book Structure and Interpretation of Computer Programs asks the following:
Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the ...
5
votes
3answers
964 views
Recursive and iterative approach for mergesort
Problem:
Question 8: *
Mergesort is a type of sorting algorithm. It follows a naturally
recursive procedure:
Break the input list into equally-sized halves Recursively sort both ...
5
votes
1answer
138 views
SICP Exercise 1.3: Sum of squares of two largest numbers out of three, Haskell Version
The exercise 1.3 of the book Structure and Interpretation of Computer Programs asks the following:
Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the ...
5
votes
1answer
89 views
Finding next perfect number - brute force
A “perfect number” is defined as a number equal to the sum of all its factors less than itself. For example, the first perfect number is 6, because its factors are 1, 2, 3, and 6, and 1+2+3=6. The ...
5
votes
1answer
340 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 ...
5
votes
2answers
1k 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:
...
5
votes
1answer
3k 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 ...
5
votes
0answers
414 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 ...
4
votes
1answer
189 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
...
4
votes
1answer
291 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
...
4
votes
1answer
105 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 ...
4
votes
1answer
368 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 ...
4
votes
1answer
83 views
SICP - exercise 2.69 - generate a huffman tree from a set of ordered leaves
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 tree ...
4
votes
2answers
97 views
Squaring a tree in Clojure
I am working on Problem 2.30 from Structure and Interpretation of Computer Programs. I book is in scheme, but I am doing the exercises in Clojure.
The problem is to write code that takes a tree of ...
4
votes
1answer
1k 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
...
4
votes
0answers
124 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). Then,...
4
votes
0answers
162 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
...
3
votes
2answers
105 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 ...
3
votes
1answer
90 views
Reversing a list without (append)
I would like to reverse a list using cdr, car and cons. Since lists in lisp are asymmetrical (can only insert at the beginning), I am interested on how one would write a procedure to do that without ...
3
votes
1answer
75 views
Church Numerals
Here is exercise 2.6 from SICP:
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 by ...
3
votes
1answer
58 views
Replacing words from a sentence
I am extremely new at scheme and I am doing this problem from here:
Write a procedure switch that takes a sentence as its argument and
returns a sentence in which every instance of the words I or ...
3
votes
1answer
71 views
SICP Exercise 1.3: Sum of squares of two largest numbers out of three, Prolog Version
The exercise 1.3 of the book Structure and Interpretation of Computer Programs asks the following:
Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the ...
3
votes
1answer
58 views
SICP Exercise 1.3: Sum of squares of two largest numbers out of three, Rust Version
The exercise 1.3 of the book Structure and Interpretation of Computer Programs asks the following:
Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the ...
3
votes
1answer
95 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 ...
3
votes
1answer
802 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 ...
3
votes
1answer
795 views
equal? predicate for lists
Exercise 2.54
Two lists are said to
be equal? if they contain equal
elements arranged in the same order.
For example,
...
3
votes
1answer
193 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:
...
3
votes
1answer
60 views
SICP - exercise 1.11 - tree recursion
From SICP
Exercise 1.11: A function \$f\$ is defined by the rule that:
\$f(n) = n\$ if \$n < 3\$, and
\$f(n) = f(n-1)+2f(n-2)+3f(n-3)\$ if \$n >= 3\$.
Write a procedure ...
3
votes
1answer
57 views
Square root calculation in Scheme (SICP Exercise 1.7)
I have done exercise 1.7 in SICP (calculate square root precision when change in guesses is under a certain value), but I am calling the change-in-precision function twice in each iteration, which ...
3
votes
1answer
59 views
SICP exercise 2.28 - counting leaves in a tree (recursive process)
From SICP
Exercise 2.28: Write a procedure fringe that takes as argument a tree
(represented as a list) and returns a list whose elements are all the
leaves of the tree arranged in left-to-...
3
votes
1answer
60 views
Replacing elements from a list and its sublists
Write a procedure substitute that takes three arguments: a list, an old word, and a new word. It should return a copy of the list, but with every occurrence of the old word replaced by the new word, ...
3
votes
1answer
97 views
SICP exercise 1.28 - miller-rabin primality test part II
This is a follow-up to SICP exercise 1.28 - miller-rabin primality test.
Exercise 1.28:
One variant of the Fermat test that cannot be fooled is
called the Miller-Rabin test (Miller 1976; ...
3
votes
0answers
41 views
Computing nth roots of a number - SICP exercise 1.45
From SICP
Exercise 1.45:
We saw in 1.3.3 that attempting to compute square roots
by naively finding a fixed point of x/y does not converge, and that
this can be fixed by average damping.
...
2
votes
5answers
7k views
Shift elements left by n indices in a list
For the following question, the function
• should mutate the original list
• should NOT create any new lists
• should NOT return anything
Functions that do not create new lists are ...
2
votes
1answer
287 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 the ...
2
votes
1answer
115 views
SICP exercise 1.28 - miller-rabin primality test
From SICP
Exercise 1.28:
One variant of the Fermat test that cannot be fooled is
called the Miller-Rabin test (Miller 1976; Rabin 1980). This starts
from an alternate form of Fermat’s ...
2
votes
1answer
965 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
29 views
SICP 1.3 Sum of Squares of two largest numbers
Define a procedure that takes three numbers as arguments and returns the sum of squares of the two largest numbers.
I'm using just the machinery that was developed so far in SICP to be true to the ...
2
votes
1answer
54 views
SICP exercise 1.3 - sum of squares of two largest of three numbers
From SICP
Exercise 1.3: Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
Square is:
...
2
votes
2answers
79 views
SICP - exercise 2.27 - reversing elements of a list and sublists
From SICP
Exercise 2.27: Modify your deep-reverse procedure of Exercise 2.18 to produce a deep-deep-reverse procedure that takes a list as argument and returns as its value the list with its ...
2
votes
1answer
296 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 ...
2
votes
1answer
361 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 ...
2
votes
1answer
1k 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 get ...
2
votes
1answer
421 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 ...
