▢ edge
▢ weighted
▢ axes
▢ directed
▢ node
▢ vertex
Muḥammad ibn Mūsā al-Khwārizmī (محمد بن موسی خوارزمی), from whom the word Algorithm derives, was from:
▢ Greece
▢ India
▢ Persia
▢ Pisa
▢ Italy
▢ North Africa
# this is not a question
bio_data = { "Leo Fibonacci": (1170, 1250),
"Al Khwarizmi": (780, 850),
"Al Gore": (1948,)}
Who wrote the multivolume The Art of Computer Programming?
▢ Djikstra
▢ Fibonacci
▢ Knuth
▢ Prim
▢ Ada
▢ Babbage
A caching technique often used to make recursive programs more efficient:
▢ dynamic programming
▢ memoization
▢ vectorization
▢ parallelization
▢ list comprehension
▢ depth first search
Which of the following are considered data structures? Check all that apply.
▢ queue
▢ stack
▢ terminal
▢ array
▢ vector
▢ Julia
Which one of the following is not considered an essential property of any group $G$ with operation $\bigotimes$?
▢ Closure: $a \bigotimes b \in G$
▢ Neutral: $G$ must have neutral element $e$ such that $e \bigotimes p = p \bigotimes e = p$
▢ Associativity: $(p \bigotimes q) \bigotimes r == p \bigotimes (q \bigotimes r)$
▢ Commutativity: $p \bigotimes q = q \bigotimes p$ for all $p, q \in G$
▢ Inverse: every $p \in G$ has an inverse $\neg p \in G$ such that $p \bigotimes \neg p = e$
True or False? Circle your answer.
In Group Theory, the elements of a group must have a well-defined "greater than" and "less than" relationship.
True | False
Napoleon was tricked into thinking he had lost a game of chess to an automaton.
True | False
A polyhedron made of vertices (nodes) and edges is a type of graph.
True | False
Totatives of N are positive integers < N with no factors in common with N.
True | False
The totient of N is the number of totatives it has.
True | False
A tree made of nodes and edges is a type of graph.
True | False
The Radix Sort is grossly inefficient at sorting large arrays.
True | False
Any graph must have a spanning tree, by definition.
True | False
Replit runs code in many languages, including Python and C++.
True | False
In a group, an element e always has an inverse ~e such that e op ~e = 1
where op is the binary operation for the group, and 1 is the identity element such that 1 op e = e op 1 = e
for any e.
True | False
Prim's Algorithm is used to find the maximum increasing (or decreasing) sub-sequence inside a give sequence of numbers.
True | False
$V + F = E + 2$ is known as Avogadro's Law.
True | False
A sphere may be tiled completely with hexagons.
True | False
A graph's spanning tree may contain one or more cycles.
True | False
The "weight" of a graph's edge always stands for "distance".
True | False
The totatives of N multiplied modulo N form a group.
True | False
The totatives of N added modulo N form a group.
True | False
import numpy as np
import pandas as pd
# setting up two graphs
G1 = pd.DataFrame({'A':[0, 3, 0, 4, 0],
'B':[2, 0, 0, 0, 0],
'C':[0, 1, 0, 0, 1],
'D':[4, 0, 3, 0, 1],
'E':[0, 0, 0, 1, 0]},
index = ['A', 'B', 'C', 'D', 'E'])
G2 = pd.DataFrame({'A':[0, 2, 3, 0, 1],
'B':[2, 0, 0, 1, 0],
'C':[3, 1, 0, 0, 0],
'D':[0, 1, 0, 0, 0],
'E':[0, 0, 1, 0, 0]},
index = ['A', 'B', 'C', 'D', 'E'])
Based on G1 and G2 below, complete the weighted, directed graphs using one- and two-way arrows. Show weights. Avoid crossing edges. Nodes provided.
G1
A | B | C | D | E | |
---|---|---|---|---|---|
A | 0 | 2 | 0 | 4 | 0 |
B | 3 | 0 | 1 | 0 | 0 |
C | 0 | 0 | 0 | 3 | 0 |
D | 4 | 0 | 0 | 0 | 1 |
E | 0 | 0 | 1 | 1 | 0 |
G2
A | B | C | D | E | |
---|---|---|---|---|---|
A | 0 | 2 | 3 | 0 | 0 |
B | 2 | 0 | 1 | 1 | 0 |
C | 3 | 0 | 0 | 0 | 1 |
D | 0 | 1 | 0 | 0 | 0 |
E | 1 | 0 | 0 | 0 | 0 |
Which of the following are well-known algorithms related to Graph Theory? Could be more than one.
▢ Prim's
▢ Djikstra's
▢ Pascal's
▢ Mandelbrot's
▢ Kadane's
▢ Julia's
USACO story problems tend to almost always involve (one best answer):
▢ recursion
▢ graphs
▢ random numbers
▢ cows
▢ dynamic programming
▢ pigs
# setting up an array
arr = [-1, 3, -2, 6, 4, 5, 10, -12]
arr
[-1, 3, -2, 6, 4, 5, 10, -12]
What is a maximum increasing subsequence of array arr
?
List its elements: _________________
What subarray of array arr
has the maximum sum?
List its elements: _________________
Which of the following is not a JVM language (one only):
▢ Java
▢ Scala
▢ Kotlin
▢ Rust
▢ Jython
▢ Clojure
Hint: JVM = Java Virtual Machine
Pair each item with a single corresponding number that connects topically (not all numbers will be needed).
Example:
[3] Animal
▢ Indian Mathematician
▢ 1, 1, 2, 3, 5...
▢ beat Napoleon at chess
▢ Graham's Scan
▢ Art of Computer Programming
▢ 5757
▢ 1, 12, 42, 92, 162...
def some_sort(seq):
if len(seq) <= 1:
return seq
else:
pivot = seq[-1]
left = [elem for elem in seq if elem < pivot]
right = [elem for elem in seq if elem > pivot]
return some_sort(left) + [pivot] + some_sort(right)
arr
[-1, 3, -2, 6, 4, 5, 10, -12]
some_sort(arr) # it works!
[-12, -2, -1, 3, 4, 5, 6, 10]
The above sorting algorithm is known as:
▢ Bubble Sort
▢ Insertion Sort
▢ Heap Sort
▢ Quick Sort
▢ Merge Sort
▢ Radix Sort
How would you define "dynamic programming" in your own words?
Fill in the non-directed, not weighted graph for this Tetrahedron.
Fill in the non-directed, not weighted graph for this Cube.