Start Programming Using HTML, CSS, and JavaScript

Quiz, Additional Problems, and Source Code

Quiz
Programming Challenges
Download Examples from the Book

Challenge 1

Write a program that computes the factorial of n. The factorial of n is the product of all positive integers less than or equal to n and is denoted by n!.

For example: 4! = 1×2×3×4 = 24

By definition, zero factorial is equal to one: 0! = 1.

Get solution

Challenge 2

Write a program that counts from 1 to 100 but replaces any number divisible by three with the word "Fizz" and any number divisible by five with the word "Buzz". If a number is divisible by both, three and five, the program should replace it with "FizzBuzz".

The program output should look like this: 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, ...

An interesting fact about the Fizz Buzz problem is that it is commonly used as a job interview question that helps ruling out more than 95% of programmer candidates. Allegedly, the problem is so hard for many people because its solution doesn't follow any of the standard patterns taught in schools.

Get solution

Challenge 3

Implement a base-n counter for any n between 2 and 10.

Base-n counting is like usual counting except that you use a different number of digits. Basically, each counting step starts by incrementing the rightmost digit by one. If the digit cannot be incremented any further, the digit is set back to zero, and its left nearest neighbor is incremented by one. This continues until either a digit can be incremented or all the digits are set back to zero and the digit 1 is added to the left of the counter.

For example, a base-2 (binary) counter counts like: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, ...

A base-4 counter would go as: 0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33, 100, 101, 102, 103, 110, ...

In everyday counting we use a base-10 (decimal) counting: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...

Hint: You can convert any base-10 number to its base-n representation by simply collecting all the remainders of consecutive divisions of that number by n.

Get solution

Challenge 1

Write a program that, given a number of elapsed milliseconds, writes the elapsed time in hh:mm:ss.f format.

For example, for 129619 milliseconds the program should display 00:02:09.6.

Get solution

Challenge 2

Write a program that computes the value of π = 3.14159... using the Leibniz formula π = 4 - 4/3 + 4/5 - 4/7 + 4/9 - ...

Notice that the Leibniz formula is an infinite series, so you will have to decide to stop it at some point to get an approximation of π.

Get solution

Challenge 3

Write a program that finds an approximate solution to the following problem: A jar contains two green and five red marbles. You take a random marble from the jar and then you take a second random marble without replacing the first one. What is the probability that none of the two chosen marbles is green ? (The exact answer is 10/21)

Hint: You can simulate the action of taking two random marbles from the jar for, say, 100,000 times, counting the number of times when no green marble is chosen. Finally, you compute the probability by simply dividing the number of times when no green marble is chosen by the total number of trials (i.e., 100,000).

Get solution

Challenge 1

Write a program that computes and outputs the first 20 Fibonacci numbers. The first two Fibonacci numbers are zero and one, and each following number is the sum of the previous two.

For example, the first 10 Fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

Get solution

Challenge 2

Write a program that makes a copy of an array of integers with all the duplicates removed.

Get solution

Challenge 3

The following code selects six different random numbers from one to 54 inclusive and stores them into an array numbers:

  var numbers = [];
  var i, n;
  for (n = 0; n < 6; n++) {
    do {
      numbers[n] = Math.floor(Math.random() * 54) + 1;
    } while(numbers.indexOf(numbers[n]) < n);
  }
  console.log(numbers);

The solution uses an array (numbers), two numerical variables (i and n), and two loops. Rewrite the program so that you only use an array, a single numerical variable, a single loop, and an if statement.

Hint: Look for additional properties and methods of the Array object.

Get solution

Challenge 4

Write a program that corrects two initial capitals in a string. For example, a string "TWo INitial CApitals" should be corrected to "Two Initial Capitals".

Get solution

Challenge 5

Write a program that evaluates expressions using Reverse Polish Notation (RPN). Assume that only decimal digits (from 0 to 9) are used as operands and only addition, subtraction, multiplication, and division are used as operations.

RPN is a way of writing mathematical expressions where each operator follows all of its operands. For example, the algebraic expression 5 + 8 is written as 5 8 + in RPN.

When evaluating an RPN expression, you often use a stack, which is an abstract data type used for storing a collection of elements. You store an element to a stack by simply putting that element on top of the stack, and you retrieve an element from a stack by taking the element that is currently on the top of the stack. The two operations on a stack are called push and pop, respectively. In JavaScript, you can use an Array object to implement a stack, using the object's push() and pop() methods to store and retrieve elements.

To evaluate an RPN expression, you only need to carry out two activities:

If there is a value in the expression, push that value onto the stack.
If an operator appears in the expression, first pop two values off the top of the stack (assuming the operator is binary) and push the result of the operation back onto the stack.

When the end of the expression is reached, there should be a single value left on the stack, which is the final value of the expression.

Note that—if you only use binary operators—there should be exactly one operand more than there are operators in a valid RPN expression. It is also true that on the left side of any point within an RPN expression there should be at least one operand more than there are operators.

For example, the expression 5 9 4 + 2 - * is evaluated as follows:

5 (push 5 onto the stack), stack contents: 5
9 (push 9 onto the stack), stack contents: 5 9
4 (push 4 onto the stack), stack contents: 5 9 4
+ (pop the values 4 and 9 off the stack, add the values, and push the result back onto the stack), stack contents: 5 13
2 (push 2 onto the stack), stack contents: 5 13 2
- (pop the values 2 and 13 off the stack, subtract the values, and push the result back onto the stack), stack contents: 5 -11
* (pop the values -11 and 5 off the stack, multiply the values, and push the result back onto the stack), stack contents: -55 (this is now the value of the above RPN expression)

Get solution

Challenge 1

The following JavaScript code produces a histogram displaying a distribution of the sums obtained by rolling two dice for 100 times:

  var sums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; 
  var i;
  for (i = 0; i < 100; i++) {
    sums[sumOfNDice(2) - 2]++;
  }
  for (i = 0; i < sums.length; i++) {
    console.log(histogram(i + 2, sums[i]));
  }

Write the missing definitions of the functions sumOfNDice() and histogram().

The function sumOfNDice() takes as a parameter a positive integer n. The function rolls n dice and returns their sum.

The function histogram() takes two parameters, legend and value. The function returns a string containing legend, a colon, and value hash symbols (#).

Finally, a completed program should produce a histogram like this one:

 2: #
 3: ##
 4: ###########
 5: #############
 6: ############
 7: ##################
 8: ####################
 9: ##############
10: #######
11: 
12: ##

Get solution

Challenge 2

Write a program that finds the solution to the following problem. Using the digits 3, 3, 8, and 8 each once and only once, and using (some or all of the operations of) addition, subtraction, multiplication, division, and parentheses, build an expression that evaluates to 24.

Hint: With the help of a base-n counter (see Meeting 7, Challenge 3) build all the possible strings of length 7 using some or all of the symbols "3", "8", "+", "-", "*", and "/" (you will use a base-6 counter). Then, using a RPN calculator (see Meeting 9, Challenge 5), evaluate each one of the before obtained strings as RPN expressions. An expression that evaluates to 24 and has exactly two 3's and two 8's is the solution to the problem.

Get solution

Challenge 1

Define a class named Box that will allow you to construct a box (i.e., rectangular cuboid) with sides a, b, and c. The class should implement two methods, one that will return the volume of the box and one that will test whether or not the box fits into another box (passed as a parameter).

This is an example of using the Box class:

  var boxOne = new Box(1, 4, 9);
  var boxTwo = new Box(2, 8, 0.6);
  console.log(boxOne.getVolume()); //Writes 36
  console.log(boxTwo.fitsInto(boxOne)); //Writes true

Get solution

Challenge 2

Extend the String class with a method correctTwoInitialCapitals() that corrects two initial capitals in a string (see Meeting 9, Challenge 4).

This is an example of using the method:

  var testString = "THis is an (EXample).";
  console.log(testString.correctTwoInitialCapitals()); //Writes This is an (Example).

Get solution

Challenge 3

Write a program that solves a classic knapsack problem: Assume that you have a knapsack that can hold a certain maximum weight. Given a number of items, each having a mass and value, determine which items to pack into the knapsack so that their total value is as large as possible while their total weight does not exceed the knapsack capacity.

To solve the problem, define a class Knapsack, whose usage is shown in the following code:

  var i;
  var myKnapsack = new Knapsack(99); //The maximum weight (the knapsack capacity) is 99
	
  myKnapsack.insertItem(new Item(23, 34));
  myKnapsack.insertItem(new Item(77, 65));
  myKnapsack.insertItem(new Item(22, 12));
  myKnapsack.insertItem(new Item(55, 56));
  myKnapsack.insertItem(new Item(12, 3));
  myKnapsack.insertItem(new Item(55, 6));
  myKnapsack.insertItem(new Item(15, 10));
	
  myKnapsack.findSolution();
  console.log(myKnapsack.reportSolution()); //Writes item0:(wt:23, val:34) item3:(wt:55, val:56) 
                                            //       item6:(wt:15, val:10) total:(wt:93, val:100)

Get solution

Challenge 1

Assume that you have the following HTML:

  <div class="stopwatch">
    <form>
      <div id="stopwatch1">00:00:00.0</div>
      <input type="button" value="Start" id="start-stopwatch1">
    </form>
  </div>

Write a program that does the following:

When a visitor clicks the start button, the stopwatch starts running. The writing on the button changes to Stop.
When a visitor clicks the stop button, the stopwatch stops. The writing on the button changes to Reset.
When a visitor clicks the reset button, the stopwatch resets to zero. The writing on the button changes back to Start.

Hint: To format the time, you can use the solution of Challenge 1, Meeting 8.

Get solution

Challenge 1

Write a program that will allow you to play a classic memory board game like the one below.

Icons made by Freepik from www.flaticon.com licensed by CC BY 3.0

Get solution

Challenge 1

Write a recursive function that returns the nth Fibonacci number (see Meeting 9, Challenge 1).

Explanation: Certain types of problems can be broken down into smaller subproblems of the same type, which can be further broken down into even smaller subproblems. Eventually, you arrive at a subproblem simple enough to be solved directly. This process of breaking down a problem into smaller and smaller subproblems of the same type is called recursion. Recursive problems can be represented by a tree and implemented as a function calling itself.

For example, a process of recursively computing the fifth Fibonacci number can be summarized in the following tree.

Notice how the main problem of computing the fifth Fibonacci number is decomposed into the subproblems of computing the fourth and third Fibonacci numbers. The subproblem of computing the fourth Fibonacci number is further decomposed into the subproblems of computing the third and second Fibonacci numbers. Finally, the subproblem of computing the third Fibonacci number is the most basic one and can be solved directly by summing the first and second numbers which are specified by definition.

Get solution

Challenge 2

Recursion is not very efficient since it consumes memory and time resources, and the problem of finding Fibonacci numbers is much more efficient when it is implemented iteratively as, for example, is the solution presented in Meeting 9, Challenge 1. That said, you will be sometimes prepared to sacrifice some efficiency for a more elegant and understandable solution, especially when you encounter a complex problem that is recursive by nature, like, for example, the following programming challenge.

Using the Box class from Meeting 11, Challenge 1, write a program that, given an array of boxes, finds the longest series of boxes that can be put one into the other so that the largest box of the found series contains all the other boxes, the second largest contains all but the largest box, and so forth.

The problem can be solved by trying out all the possible combinations of given boxes. Since a larger box cannot be placed into a smaller one, you can first sort the boxes by volume. Then, starting with the smallest box, you try to put the box into the second smallest box. If it doesn't fit, you try the next one, and so forth, until you either find a box that the first box fits into or you repeat the whole process with the second smallest box. Every time you get to the largest box, you count the number of boxes that you succeeded to put one into the other.

Hint: Before you start to write a program, draw a tree that depicts the process of trying to put boxes into the other boxes.

Get solution

Furter Reading

If you have been intrigued by recursion, I suggest that you read the chapter on recursion from the Design and Implementation of Computer Applications Course Notes by Mathieu Couture. Note that the examples are written in Java (which is not JavaScript) but I think that you shouldn't have any troubles with understanding the code.

Challenge 1

Extend the Sudoku application from the book (finished in Appendix A) so that it will remember a partial solution entered by a player even when he/she leaves the page and returns back later. Use the Web Storage to implement the needed data storage. Also, add a "new" button that will clear the grid and generate a new Sudoku puzzle.

Hint: You can store the puzzle state to local memory just before the page unloads, which triggers the unload event on the window object. You might also want to rewrite certain parts of the existing code in order to easier implement the required additions. In practice, it is sometimes necessary to do so at certain stages of a project, when you discover that you overlooked certain details or—even more likely—not all the knowledge needed was available at the planning stage.

Note: The Web Storage is not available locally in IE, so you will have to upload your code to a web server if you want to test it in IE.

Get solution

You can download a zip file containing the source code of the examples from the book. Each file is named by a page number where the example starts and a short title of the example. There is a separate folder for each meeting containing all the necessary files.

Notes:

You can run the examples locally, except for the Ajax example from Appendix B, which you need to upload to a web server in order to be able to run it.
If you are using IE, you will have to upload to a web server the Memo example as well, as the Web Storage is not available locally in IE.
Some examples write text to the JavaScript Console and you will see nothing when you load them unless you open the Console.