Repository files navigation

🐍 Exercise solutions for chapter 1.1 written in Python

1. is_between_zero_and_one()
2. to_binary_string()
3. print_two_dm_boolean_array()
4. print_two_dm_int_array()
5. print_int_array()
6. matrix_transposition()
7. lg()
8. Fibonacci.fib()
9. Fibonacci.fast_fib()
10. fact()
11. binary_search()
12. brute_force_search()

One interesting implementation is this algorithm to compute fibonacci sequences (exercise 1.1.19). It runs in O(1) time provided that the cache contains the previous two sequences. Generating the previous sequences is usually done using loops.

@staticmethoddeffast_fib(n:int,cache: {int:int})->int:"""Fibonacci sequence algorithm utilizing dynamic programing and memoization"""ifn==0:cache[n]=0return0ifn==1:cache[n]=1return1cache[n]=cache[n-2]+cache[n-1]returncache[n]

It's also worth noting that I've implemented brute force search recursively here as opposed to the iterative approach in the Javasource

defbrute_force_search(key:int,the_array: [int],index:int)->int:"""Returns the index of the key if present, otherwise -1 using brute force search"""ifindex==len(the_array):return-1ifthe_array[index]==key:returnindexreturnbrute_force_search(key,the_array,index+1)

These were originally implemented in Java. You can find the sourcehere