Rosuav

//Utility function to display a binary tree to the console
//More helpful than console.log(tree) due to circular parent refs
//Usage: print_tree(some_tree)
function print_tree(tree, depth) {
	if (!depth) {
		console.log("" + tree.key);
		depth = 0;
	}
	depth += 1;
	if (tree.left) {

Rosuav

//The share price for a company over a week's trading is as follows:
//[128, 97, 121, 123, 98, 97, 105]. If you had to buy shares in the company
//on one day, and sell the shares on one of the following days, write an
//algorithm to work out what the maximum profit you could make would be.
function best_profit(prices) {
	if (!prices.length) return 0;
	//Algorithm: Step through potential selling days. If the price
	//is lower than our current buying day, switch to a new buying
	//day. If the price diff between buying and selling days is
	//greater than our current best, it's our new best.

Rosuav

//Write an O(n) algorithm to sort an array of integers, where you know in
//advance what the lowest and highest values are.
function bucket_sort(arr, min, max) {
	var buckets = Array(max - min + 1);
	for (var i = 0; i < arr.length; ++i)
		buckets[arr[i] - min] = (buckets[arr[i] - min]|0) + 1;
	var ret = [];
	for (var i = min; i <= max; ++i)
		for (var j = 0; j < buckets[i - min]; ++j)
			ret.push(i);

Rosuav

//Write an algorithm which will sum two numbers stored in linked lists, where
//each node contains a single digit of the number.

//Assuming that the head of the list is the least significant digit, and that
//each list contains a minimum of one node (which may be zero).
var BASE = 10; //Each digit in the linked list is smaller than this.
function add_numbers(list1, list2) {
	var carry = 0;
	var ret, tail = null;
	while (list1 || list2 || carry) {

Rosuav

function triangle(x)
{
	if (x <= 1)
	{
		if (x == 1) return 1;
		else throw "Can't get triangle number of " + x;
	}
	return triangle(x - 1) + x;
}

Rosuav

"use strict";

function g(n) {
	if (n) {
		const me_cry = "stand here";
		var break_of_dawn = "perfect";
	} else {
		//Some variables rise to the top of the function.
		//Do their values?
		console.log(break_of_dawn);

Rosuav

Solutions to these problems

Note that there are other ways to solve these problems, different algorithms to achieve the same goals, which may have different algorithmic complexities.

Exercise 1:

Write a program that determines if an input is even or odd. Explain its average and worst run time

function is_odd(n) {
    return (n % 2) != 0;
}

Rosuav

Two of the most commonly used data structures in web development are stacks and queues. The history of pages visited in a web browser and the undo operation in a text editor are examples of operations made possible using stacks. The handling of events in web browsers often uses a queue data structure.

Stack

A stack is a data structure that stores elements in a LIFO (Last In First Out) order. It's like a stack of plates in your kitchen. When a plate is added, it is pushed towards the bottom of a stack. The last plate that you stack becomes the one on the top of the stack and it is the first one that you get to use.

A stack has two basic functions:

• push(): places data onto the top of a stack
• pop(): removes data from the top of the stack

Rosuav

Palindromes

A palindrome is a word, phrase, or number that is spelled the same forward and backward. For example, “dad” is a palindrome; “A man, a plan, a canal: Panama” is a palindrome if you take out the spaces and ignore the punctuation; and 1,001 is a numeric palindrome. We can use a stack to determine whether or not a given string is a palindrome.

Write a function that takes a string of letters and returns true or false to determine whether it is palindromic. For example:

function is_palindrome(s) {
    s = s.toLowerCase().replace(/[^a-z]/g, "");
    // your code goes here
}

Rosuav

//Basic string padding functions
function lpad(str, wid) {
	return (" ".repeat(wid) + str).slice(-wid);
}

function rpad(str, wid) {
	return (str + " ".repeat(wid)).slice(0, wid);
}

function cpad(str, wid) {