Computer Science with Applications 1 & 2
Send us feedback!
If you like any particular exercise, or don't like it, think it's too easy, too hard, or its difficulty is mis-classified, please let us know. Even if you just attempt an exercise, you can let us know, so we can get a feel of how many people actually try them.
Exercises:
These are ungraded exercises designed to help you absorb and practice
the concepts learned in class and needed on (graded) assignments. You
are not required to turn them in, but feel free to ask course staff if
you have trouble with them.
- Exercise 0 (Week 1)
Exercises from the book:
As with the exercises above, you need not turn in the following exercises, but you can ask course staff if the exercises give you difficulty. All of these exercises will give you practice, but some will introduce you to techniques or ideas we may not have time to cover in class.
Note that many of the exercises refer to programs within the chapter. You can either copy these directly from the book into a text file, or you can download them from the booksite.
The exercises are marked as follows:
- * - Important
- C - Classic
- ! - Interesting
- !! - Cool
Exercises are also classified as either "Quick" or "In-depth". Quick ones should have very short solutions that don't require too much thought, just understanding of the material. But don't be scared by the in-depth ones -- none of them should require more than 20 lines of code.
Some extensions of the exercises are also suggested, and are numbered, for example "1.2.27X".
Section 1.2: Built-in Types of Data (Week 1)
| Quick and Easy |
| *C |
1.2.1 |
Swapping variable values |
|
1.2.2, 1.2.13 |
Imprecision of doubles |
|
1.2.6 |
Integer division |
|
1.2.7 |
Perils of String concatenation |
|
1.2.10 |
Integer overflow |
|
1.2.11 |
Casting |
| In-depth and Medium Difficulty |
| ! |
1.2.25 |
Calculating wind chill |
| ! |
1.2.27 |
Generating random numbers with a Gaussian distribution |
| ! |
1.2.27X |
Plot points using the Picture class, where the points polar coordaintes are (r, theta): r should be chosen according to a Gaussian distribution and theta should be chosen randomly between 0 and 2π |
|
1.2.29 |
Equation for the Gregorian calendar |
| ! |
1.2.31 |
Calculate Mercator projection |
| ! |
1.2.31X |
Plot the Mercator projection of an entire sphere, and draw it using the Picture class. This will require you to sample points from the sphere. |
|
1.2.35 |
Dragon Curves (pre-recursion recursion) |
Section 1.3: Conditionals and Loops (Weeks 1 & 2)
| Quick and Easy |
|
1.3.5 |
Extending 1.2.25 (wind chill) with error checking |
|
1.3.8 |
Output 5 ints per line |
| * |
1.3.11 |
Growth rates of numeric functions |
|
1.3.16 |
Sum 1/n2 |
| *C |
1.3.16X |
Use 1.3.16 to estimate the value of π. Math.PI has 15 digits of precision. Find out, for each k between 1 and 15, how many iterations of the loop are needed to get within 10-k of the value of Math.PI. |
|
1.3.21 |
Translating a while to a for |
| C |
1.3.25 |
Factoring integers, printing each prime factoring only once |
| Quick and Medium Difficulty |
|
1.3.12 |
Reversing the digits of a number |
| C |
1.3.13 |
Fibonacci numbers |
|
1.3.19 |
Numbers in base k |
| C |
1.3.28 |
Euclid's greatest common divisor algorithm |
|
1.3.31 |
Sampling a random point from a sphere |
| In-depth and Easy |
|
1.3.32 |
Find a, b, c, d, such that a3 + b3 = c3 + d3 (based on the story of Ramanujan's taxi) |
| * |
1.3.33 |
ISBN Checksum digit |
| In-depth and Medium Difficulty |
| C |
1.3.34 |
Counting primes |
| C |
1.3.40 |
Monte Hall |
|
1.3.43 |
Chaos in population growth |
|
1.3.44 |
Euler's sum-of-powers conjecture |
Section 1.4: Arrays (Week 2)
| Quick and Easy |
| * |
1.4.2 |
OutOfMemoryError |
| C |
1.4.4 |
Reverse an array in-place (i.e. without copying) |
|
1.4.9 |
Referential equality (meaning: == doesn't do equality-by-value) for arrays |
| Quick and Medium Difficulty |
| *C |
1.4.11 |
Copying 2D arrays |
|
1.4.14 |
2D array of relative primality using sieves, and printing of 2D arrays |
| *C |
1.4.15 |
Multplying boolean matrices |
| *C |
1.4.17 |
Multiplying non-square matrices |
| In-depth and Easy |
| *C |
1.4.22 |
Empirical shuffle check |
| *C |
1.4.23 |
Bad shuffling |
| * |
1.4.24 |
Minima in random permutations |
| *C |
1.4.37 |
Pascal's triangle and binomial coefficients |
| In-depth and Medium Difficulty |
| *C |
1.4.25 |
Finding the inverse of a permutation |
| *C |
1.4.26 |
Hadamard matrices (easier with recursion) |
| ! |
1.4.27 |
Rumor-spreading |
| *C |
1.4.29 |
Counting primes with a sieve; example of time-space tradeoff |
| ! |
1.4.30 |
Minesweeper |
| C |
1.4.35 |
The birthday paradox |
| C |
1.4.36 |
Coupon collector's problem (see the Wikipedia entry for details) |
Section 2.3: Recursion (Week 3)
| Quick and Easy |
| * |
2.3.1 |
Recursion blow-up |
| *C |
2.3.8 |
A classic, fast algorithm for some basic functions |
|
2.3.2 |
Easy practice: compute ln(N!) |
| In-depth and Easy |
|
2.3.15 |
Easy practice: compute the binary representation of a number recursively |
|
2.3.16 |
Easy practice: computer paper size recursively |
| In-depth and Medium Difficulty |
| *C |
2.3.29 |
Collatz 3n+1 problem |
| *! |
2.3.32 |
McCarthy's 91 function |
| !! |
2.3.30 |
Drawing realistic (Brownian) islands |
| !! |
2.3.31 |
Drawing plasma clouds |
| !! |
2.3.33 |
Drawing trees (note: mislabelled 2.3.30 in the book) |
| In-depth and Harder |
| *C |
2.3.17 |
Generating all permutations |
| *C |
2.3.20 |
Generating all combinations of size k |
|
2.3.21 |
Generating all strings at a given Hamming distance |
Practice for Midterm
Note that these exercises come with no guarantee of any kind. (For example, we don't guarantee that if you can do these then you'll do well on the midterm.) However, we think these may serve as useful practice problems that shouldn't take you too long.
- Section 1.2: 1.2.1, 1.2.7
- Section 1.3: 1.3.6, 1.3.8, 1.3.12, 1.3.21
- Section 1.4: 1.4.4, 1.4.7, 1.4.9
- Section 2.1: 2.1.4, 2.1.12
- Section 2.3: 2.3.1, 2.3.2, 2.3.8, 2.3.15, 2.3.32
- Challenge (if you can do these with ease, you're like some sort of recursion wizard): 2.3.17, 2.3.20, 2.3.21
Practice for Final
Note that these exercises come with no guarantee of any kind. (For example, we don't guarantee that if you can do these then you'll do well on the final exam.) However, we think these may serve as useful practice problems that shouldn't take you too long. All the practice exercises for the midterm will make good practice exercises for the final, in adddition to those below. The exercises below that are marked with a P are also good Python exercises. NOTE: the numbering of these exercises is as they appear on the booksite, not necessarily in the physical book. Each section below is linked to the corresponding page of the booksite (scroll down that page to get to the exercises):
- Section 3.1 Data Types: 4, 12P; Creative Exercises 11P, 25P (hint: recursion),
- Section 3.2 Creating Data Types: Creative Exercises 17+18 (don't peek @ solution), 47
- Section 4.2 Sorting and Searching: Web Exercises 5, 6, 7; Creative Exercises 2, 9, 34
- Section 4.3 Stacks and Queues: Stacks & Queues 3, 4 (don't peek @ solution), 5, 6, 13; Linked Lists 1-6; Creative Exercise 1
- Section 4.4 Symbol Tables: 8; Binary Trees 1-4, 7; Creative Exercise 17; Web Exercises