Questions tagged [sicp]
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.
81
questions
3
votes
2
answers
709
views
SICP - exercise 1.7 better end test for square root approximation
Here is exercise 1.7 from SICP:
Exercise 1.7
The good-enough? test used in computing square roots will not be very
effective for finding the square roots ...
- 2,718
2
votes
0
answers
144
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,718
0
votes
2
answers
1k
views
Iterative "counting change" implementation in mit-scheme
Here is my iterative implementation of the Counting change example in SICP. Please note that I'm a beginner, which means I only know the basic syntax for the time being.
Requirement:
How many ...
- 523
1
vote
2
answers
2k
views
Pascal's triangle in mit-scheme
As suggested by the name of source file (ex1.12.scm), I just started learning mit-scheme by reading SICP. In Exercise 1.12, I'm asked to "compute elements of Pascal'...
- 523
2
votes
1
answer
990
views
Generating all unique permutations of a string
Here is a plan for generating the permutations of S: For each item x
in S, recursively generate the sequence of permutations of S - x, and
adjoin x to the front of each one. This yields, for each ...
- 2,718
1
vote
2
answers
8k
views
Reverse the order of a list in Racket
I am using the SICP book. There is an exercise in which you need to create a function that will receive a list as an argument and return a list with the same elements in a reverse order.
I know there ...
user119912
3
votes
1
answer
470
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 ...
- 2,718
3
votes
1
answer
221
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; ...
- 2,718
2
votes
1
answer
292
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,718
3
votes
1
answer
198
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 ...
- 232
3
votes
1
answer
971
views
SICP - exercise 1.12 - pascal's triangle
From SICP:
Exercise 1.12: The following pattern of numbers is called Pascal’s triangle.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
. . .
The numbers at the ...
- 2,718
2
votes
1
answer
420
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 ...
- 2,718
3
votes
1
answer
245
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 ...
- 133
2
votes
1
answer
164
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,718
4
votes
1
answer
277
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 ...
- 2,718
2
votes
1
answer
190
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-...
- 2,718
2
votes
2
answers
591
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,718
2
votes
1
answer
104
views
SICP - exercise 2.5 - representing pairs of nonnegative integers using only numbers and arithmetic operations
From SICP
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 integer that is the product 2^x*3^...
- 2,718
2
votes
1
answer
54
views
Replacing elements from a list and its sublists - part II
This is sort of a follow-up to
Replacing elements from a list and its sublists
but now there are arbitrary numbers of words that would be replaced stored in a list.
Now write substitute2 that takes ...
- 2,718
1
vote
2
answers
385
views
SICP - exercise 2.20 - same-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, a parameter ...
- 2,718
3
votes
1
answer
1k
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 ...
- 2,718
2
votes
1
answer
84
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, ...
- 2,718
5
votes
1
answer
195
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 ...
- 2,718
4
votes
2
answers
238
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 ...
- 68
3
votes
1
answer
111
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 ...
- 2,718
5
votes
4
answers
4k
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 ...
- 3,321
-1
votes
2
answers
3k
views
Filter a list with given predicate - python [closed]
For the following question, the function
• should mutate the original list
• should NOT create any new lists
• should NOT return anything
Function that do not create new lists are said to be ”in place....
- 3,321
5
votes
5
answers
62k
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 said to be ”in ...
- 3,321
0
votes
1
answer
485
views
Interval multiplication - faster version
For the below given problem from this assignment:
Q4. In passing, Ben also cryptically comments, "By testing the signs of the endpoints of the intervals, it is possible to break ...
- 3,321
1
vote
1
answer
1k
views
Is there something wrong with my remove-duplicates implementation in Scheme?
For an assignment I handed in this code to remove duplicates from a stream.
...
- 113
4
votes
1
answer
154
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
1
answer
91
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 ...
5
votes
1
answer
217
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
3
answers
543
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 ...
3
votes
1
answer
248
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 ...
- 203
4
votes
0
answers
795
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, in ...
- 3,321
4
votes
1
answer
204
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 ...
- 43
3
votes
2
answers
204
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 ...
- 183
7
votes
2
answers
539
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 ...
- 217
7
votes
2
answers
176
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 ...
- 2,243
5
votes
1
answer
223
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
...
- 2,243
5
votes
1
answer
542
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 ...
- 2,243
2
votes
1
answer
367
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,243
2
votes
0
answers
413
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,243
3
votes
1
answer
1k
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 ...
- 2,243
3
votes
2
answers
2k
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,243
4
votes
0
answers
496
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,243
2
votes
0
answers
1k
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
I ...
- 2,243
2
votes
1
answer
448
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
...
- 2,243
4
votes
1
answer
195
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
...
- 2,243