Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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.

Filter by
Sorted by
Tagged with
3 votes
2 answers
749 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 ...
lightning_missile's user avatar
2 votes
0 answers
148 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. ...
lightning_missile's user avatar
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 ...
nalzok's user avatar
  • 513
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'...
nalzok's user avatar
  • 513
2 votes
1 answer
995 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 ...
lightning_missile's user avatar
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 ...
user avatar
3 votes
1 answer
474 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 ...
lightning_missile's user avatar
3 votes
1 answer
222 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; ...
lightning_missile's user avatar
2 votes
1 answer
301 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 ...
lightning_missile's user avatar
3 votes
1 answer
200 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 ...
Hugo's user avatar
  • 232
3 votes
1 answer
1k 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 ...
lightning_missile's user avatar
2 votes
1 answer
446 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 ...
lightning_missile's user avatar
3 votes
1 answer
255 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 ...
leancz's user avatar
  • 133
2 votes
1 answer
169 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: ...
lightning_missile's user avatar
4 votes
1 answer
286 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 ...
lightning_missile's user avatar
2 votes
1 answer
197 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-...
lightning_missile's user avatar
2 votes
2 answers
611 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 ...
lightning_missile's user avatar
2 votes
1 answer
109 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^...
lightning_missile's user avatar
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 ...
lightning_missile's user avatar
1 vote
2 answers
400 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 ...
lightning_missile's user avatar
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 ...
lightning_missile's user avatar
2 votes
1 answer
85 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, ...
lightning_missile's user avatar
5 votes
1 answer
199 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 ...
lightning_missile's user avatar
4 votes
2 answers
243 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 ...
jimypbr's user avatar
  • 68
3 votes
1 answer
112 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 ...
lightning_missile's user avatar
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 ...
overexchange's user avatar
  • 3,331
-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....
overexchange's user avatar
  • 3,331
5 votes
5 answers
63k 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 ...
overexchange's user avatar
  • 3,331
0 votes
1 answer
495 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 ...
overexchange's user avatar
  • 3,331
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. ...
user16655's user avatar
  • 113
4 votes
1 answer
156 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 ...
Marcus Vinícius Monteiro's user avatar
3 votes
1 answer
92 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 ...
Marcus Vinícius Monteiro's user avatar
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 ...
Marcus Vinícius Monteiro's user avatar
5 votes
3 answers
550 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 ...
Marcus Vinícius Monteiro's user avatar
3 votes
1 answer
255 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 ...
fearless_fool's user avatar
4 votes
0 answers
805 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 ...
overexchange's user avatar
  • 3,331
4 votes
1 answer
210 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 ...
user2944397's user avatar
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 ...
stantona's user avatar
  • 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 ...
Racheet's user avatar
  • 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 ...
jaresty's user avatar
  • 2,243
5 votes
1 answer
224 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 ...
jaresty's user avatar
  • 2,243
5 votes
1 answer
547 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 ...
jaresty's user avatar
  • 2,243
2 votes
1 answer
369 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 ...
jaresty's user avatar
  • 2,243
2 votes
0 answers
415 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 ...
jaresty's user avatar
  • 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 ...
jaresty's user avatar
  • 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. ...
jaresty's user avatar
  • 2,243
4 votes
0 answers
499 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 ...
jaresty's user avatar
  • 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 ...
jaresty's user avatar
  • 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 ...
jaresty's user avatar
  • 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 ...
jaresty's user avatar
  • 2,243