Original post by Gage64

A nice set of exercises, although thy insist more on imperative programming techniques than on actual algorithms. However, since C++ is unnecessarily verbose, I'll be using OCaml instead as an illustration of the algorithms:

// Scroll down // 1.1. Write a program that accepts the width and height of a rectangle and // returns the area and perimiter.let rectangle width height =   width * height, (width + height) * 2// 1.2. Write a program that has two variables with initial values, and add code that // causes the values in the variables to be swapped. That is, if you have the variables: // a, b, then after the code is executed, the value of a will equal the initial value of // b, and the value of b will equal to the initial value of a.let swap (a,b) =   (b,a)// 1.3. Write a program that accepts a positive two digit number and writes the two // digits of the number, separated by a space.let split num =   Printf.sprintf "%d %d" (num / 10) (num mod 10)// 1.4. Write a program that accepts two numbers, a and b, and writes a random number // in the range [a, b] (that is, the range should be inclusive).let interval a b =   Random.int (b - a + 1) + a// 2.1. Write a program that accepts two numbers as input and prints the bigger number.let bigger a b =  max a b// 2.2. Repeat 2.1 with 3 numbers.let biggest a b c =  max a (max b c)// 3.1. Write a program that reads 10 numbers and writes their average.let avg f =   let rec aux tot = function     | 10 -> tot / 10    | n -> aux (tot + f()) (n+1)  in aux 0 0// 3.2. Write a program that reads a sequence of numbers and writes their average. // the sequence ends when the number -1 is read (and -1 should not participate in the // calculation of the average).let avg f =   let rec aux tot n =    match f () with       | -1 -> tot / n      |  x -> aux (tot + x) (n + 1)   in aux 0 0     // 3.3. Write a program that reads a positive number and prints the sum of it's digits. // For example, if the number is 327, the output should be 12.let rec sum = function   | 0 -> 0  | n -> n mod 10 + sum (n/10)// 3.4. Write a program that reads a positive number and writes it with the digits // reversed. For example, if the number is 327, the output should be 723.let rec rev = function   | 0 -> ""  | n -> string_of_int (n mod 10) ^ rev (n / 10)// 3.5. Write a program that reads a sequence of numbers. The sequence ends when -1 is // read. The program should write the largest of the numbers entered.let best f =   let rec aux best =     match f () with       | -1 -> best      |  x -> aux (max best x)   in aux min_int// 3.5. Like to 3.5, but this time also write the second largest number entered. Test your // program with various inputs to make sure it's correct.let best2 f =   let rec aux (fst,snd) =     match f () with       | -1 -> (fst,snd)      |  x -> aux (max fst x, max (min fst x) snd)   in aux (min_int, min_int)// 3.6. Write a program that reads a number, and prints rows of '*'. For example, if // the number is 4, the output should be:// // *// **// ***// ****let lines n =   let rec aux lst = function     | 0 -> lst    | n -> lst ^ "\n" ^ aux (lst ^ "*") (n - 1)  in aux "" n// 3.7. Like 3.6, but this time if the number is 4, the output should be:// // *// ***// *****// *******let lines n =   let rec aux lst = function     | 0 -> lst    | n -> lst ^ "\n" ^ aux (if lst = "" then "*" else lst ^ "**") (n - 1)  in aux "" n// 3.8. Write a program that reads a number and simply prints it. However, if the number // is less than 100, the program should display an error message and request input again. // That is, the program should only end when valid input is entered.let rec read_until f =   match f () with     | bad when bad < 100 -> print_endline "bad input"; read_until f    | good -> good// 4.1. Write a program that reads 10 numbers and writes all numbers that are greater // than the average of the numbers.let bigger lst =   let avg = List.fold_left (+) 0 lst / List.length lst in  List.filter ( (>) avg ) lst  // 4.2. Write a program that reads 10 numbers and writes the numbers in reverse order.let rev lst =   let rec aux rv = function    | []   -> rv    | h::t -> aux (h::rv) t  in aux [] lst// 4.3. Write a program that reads grades between 0-100 (the program should accept // only grades in that range). The program should stop reading when -1 is entered. The // program should print a table showing how many times each grade was entered. For example, // if the input is: 60, 75, 60, 80, 75, 75, -1, the output should look something like:// // 60 - 2// 75 - 3// 80 - 1let totals f =   let data = Array.make 100 0 in   let rec read () =     match f () with       | -1                        -> ()      |  x when x < 100 && x >= 0 -> data.(x) <- data.(x) + 1; read ()      |  x                        -> read ()   in read ();    Array.iteri (fun i x -> if x > 0 then Printf.printf "%d - %d\n" i x) data// 4.4. Write a program that reads 10 numbers and puts them in an array. The program should // print all numbers whose value is exactly twice the value of it's array index. For // example, if array[3] has a value of 6, then 6 should be printed.let print_if_double arr =   Array.iteri (fun i x -> if x = i * 2 then Printf.printf "%d " x) arr

Now, a few other interesting questions on the algorithmic side:

1. Given a sequence of integers, find the median of these integers in linear time complexity.
   
   
2. Given a function f which represents an unknown equivalence relationship between the integers [1, 100], find in linear time complexity whether one of the equivalence classes contains more than half of the elements of the interval.
   
   
3. The White Wolf probability system: you throw N 10-sided dice, compute the probability that at least T dice will be higher than D, as a function of (N,T,D).
   
   
4. You are given an incomplete order relationship over [1, N], given as a list of (i,j) pairs where i < j. Sort [1, N] according to that order (if elements are not comparable, you may place them in any order).
   
   
5. You are given a flattened directory tree: a sequence of elements of the form (name, depth) where the folder itself always appears directly above its elements. Build and return the corresponding directory tree.

Quote:Original post by Alpha_ProgDes
Uhhh, ToohrVyk.... you realize this is for beginners????

Quote:Original post by ToohrVyk
A nice set of exercises, although thy insist more on imperative programming techniques than on actual algorithms.

Quote:Original post by Alpha_ProgDes
Uhhh, ToohrVyk.... you realize this is for beginners????

Quote:Original post by ToohrVyk

Quote:Original post by Alpha_ProgDes
Uhhh, ToohrVyk.... you realize this is for beginners????

The Cormen-Leiserson-Rivest-Stein "Introduction to Algorithms" book is intended for beginners

Quote:Original post by Gage64

Quote:Original post by ToohrVyk
A nice set of exercises, although thy insist more on imperative programming techniques than on actual algorithms.

You're right. They were intended to test your understanding of fundamental programming constructs, so maybe this isn't the best thread for them, but what's done is done.