SIT111-Algorithms and Computing Systems 1
Think questions 8
1. What is the smallest computer you have seen?
1. What is an “algorithm”?
1. What is the difference between Computer Science and computer programming?
1. Four aspects of computational thinking are:
You have been asked to prepare three types of sushi rolls (tuna roll, cucumber roll and salmon roll). How do you apply the above to making three types of sushi rolls?
Week 2. Think.
1. What do you understand by the word “digital”?
1. “Computer Science: the science (systematic study and body of knowledge) that deals with the theory and methods of processing information in digital computers, the design of computer hardware and software, and the applications of computers.”
A key principle underlying computer hardware is that they mainly process digital signals – why are modern computers fundamentally digital signal processing machines rather than analog?
1. Where is the CPU, memory and hard drive in this picture of a desktop PC?
1. The following describes the three steps the Central Processing Unit (CPU) of a computer repeatedly cycles through when executing a sequence of instructions. Which step would be the starting step?
1. The algorithm below takes two inputs: a decimal number and a base, and does something. What answer does this algorithm compute?X is assigned the input decimal number, B is the input base
While (X is not zero)
Divide X by B to get a quotient and a remainde
Make the remainder the next digit to the left in the answe
X is assigned the quotient
1. Name as many Operating Systems as you can. Why does a computer need an Operating System?
2. What does it mean to say that a computer can multitask, and why does a computer need to multitask?
3. What is a file system on a computer?
4. What does this Python program do? Describe the output of the program (i.e., what would be seen when the program runs to completion and terminates?)
print(‘count is 3’)
And what about this?
count = 0
for i in ['a','b','c']:
count = count + 1
print(‘count is ‘+str(count))
print("hello \a world!")
print("blackslash \\ is me")
Week 4. Think.
1. Why do we need programming languages for programming computers?
1. Why does a program in Python need to be interpreted or compiled in order to run/execute?
1. What is the syntax of a programming language and the semantics of a programming language?
1. What is the difference between interpretation and compilation?
1. What are examples of basic types in Python?
1. What is dynamic typing?
Week 5. Think.
1. Convert these into Python code:
1. Einstein’s field equation (from Physics - relates gravitation with the speed of light, and the curvature of space-time):
1. Rossmo’s formula (from Criminology - gives the probability of pi,j of the position of the serial criminal residing at a point (Xi,Yj) based on a history of crimes):
[Src: Wikipedia for some references. Or if interested, see https:
jeremykun.com/2011/07/20/serial-killers/ (hunting for serial killers), and see https:
1. Which list operation to do the following?
1. Find the length of (number of items in) the list [1,5,7,3,9]
1. Join two lists [1,2,3] and [4,5,6] into [1,2,3,4,5,6]
1. Generate [‘hi’, ‘hi’, ‘hi’, ‘hi’, ‘hi’] from [‘hi’]
1. Test if 3 is in [1,2,3]
1. Count how many times an object (e.g., ‘a’) appears in
a list (e.g., in the list [‘a’, ‘b,’, ‘f’, ‘a’, ‘e’, ‘a’, ‘a’])
1. Remove an object ‘a’ from the list [‘a’, ‘b,’, ‘f’, ‘a’, ‘e’, ‘a’, ‘a’] to form [‘b,’, ‘f’, ‘e’]
1. Insert an object ‘a’ into the list [‘b,’, ‘f’, ‘e’] at the 2nd position to form [‘b,’, ‘a’, ‘f’, ‘e’]
1. Reverses objects in a list, e.g., [1,2,3,4,5,6] to [6,5,4,3,2,1]
1. Sorts objects in a list, e.g., from [1,5,7,3,9] to [1,3,5,7,9]
1. Find the maximum value in a list, e.g., 9 from [1,3,5,7,9]
[Check out https:
ary/stdtypes.html?highlight=list%20operations#sequence-types-list-tuple-range and https:
3. Devise an algorithm to compute the following: given a list of numbers, find the average of the even numbers in the list, e.g., in [1,2,4,1,2,9,4], the even numbers are 2,4,2 and 4, and the average of them is XXXXXXXXXX)/4=3.
Week 6. Think.
1. Often programs need to manipulate collections of information, e.g., a list of student names, a list of numbers or a collection of records. For example, you have a list of names you want to sort – what is the first thing required before you can manipulate the data? How does Python support the representation of collections?
1. Write an iterative algorithm and a recursive algorithm to sum the numbers in a list.
1. Write a recursive algorithm to sort the numbers in a list.
1. Consider the following problem. Write pseudocode for an algorithm (that uses recursion) to solve it.
Problem how to draw a Sierpinski triangle: “The procedure for drawing a Sierpinski triangle by hand is simple. Start with a single large triangle. Divide this large triangle into four new triangles by connecting the midpoint of each side. Ignoring the middle triangle that you just created, apply the same procedure to each of the three corner triangles. Each time you create a new set of triangles, you recursively apply this procedure to the three smaller corner triangles. You can continue to apply this procedure indefinitely if you have a sharp enough pencil.”
[A recursive algorithm to do this using the turtle package is at http:
Week 7. Think.
1. Compare mergesort and insertion sort of this list [2,9,1,6,3,2]: how many comparisons are needed in each?
1. What does it mean to say that a function T(n) = O(n log n) ?
1. If the time complexity of mergesort is O(n log n) and insertion sort is O(n2), where n is the input size, how much faster is mergesort?
1. What does a polynomial time algorithm mean, i.e. a problem in class P?
1. What does non-deterministic polynomial time algorithm mean, i.e. a problem in class NP?
1. Give an example of a problem that is in NP?
1. Is P=NP?
1. Consider the following directed graph represented by adjacency lists:
Do a BFT and a DFT of the graph.
1. What is the advantage of BFT over DFT when searching over an infinite sized graph?
Week 8. Think.
1. What is dynamic programming? Why does it usually work faster?
2. Using the dynamic programming solution for the knapsack problem, compute a solution to this knapsack problem:
total number of items = 4
capacity of the knapsack = 7
3. Suppose that the similarity between an object O and 6 other objects in the database A,B,C,D,E and F are as follows:
sim(A,O) = 0.1
sim(B,O) = 0.3
sim(C,O) = 0.85
sim(D,O) = 0.8
sim(E,O) = 0.9
sim(F,O) = 0.6
Also, suppose objects A, B and C are in class 1 and
D,E and F are in class 2.
With k=4, what class should O be in, using the kNN algorithm?
With k=2, what class should O be in, using the kNN algorithm?
Week 9. Think.
1. Why does the Internet need standards?
1. Build an index for these documents:
D1: “I love Algorithms and Computing systems”
D2: “Algorithms are my love, and so is Computing”
D3: “I am confused by Algorithms”
How do you use the index to answer the query “Computing” and the query “Algorithms” and “love”?
1. What does the random surfer notion have to do with the PageRank algorithm?
1. Compute the page rank of the three pages below, at time step 2:
1. using prob 0.15 that the user simply randomly selects a page from the whole Web and with prob 0.85, the user follows a link from the cu
(b)using prob 0.5 that the user simply randomly selects a page from the whole Web and with prob 0.5, the user follows a link from the cu
Cryptography and Crytocu
1. What is a cipher? How does it secure a message?
1. What operations are used in the DES?
1. What operations are used in the AES?
1. How is a public key cryptographic system different from a private key cryptographic system?
1. What is a cryptocu
1. How is cryptography used in cryptocu