Description
Plan
Introduce yourself to those of your classmates sitting closest to you and tell them a bit about yourself. We are guaranteed to be a population with very different backgrounds, different languages, different hometowns, different career plans, and so on. If you already know your neighbours, mingle with some of the other students.
The exercises
1. Consider the usual (unsigned) binary representation of integers. For example, 10110010 represents 178, and 000011 represents 3.
(a) If we call the bits in an n-bit word xn−1,xn−2,…,x2,x1,x0 (so x0 is the least significant bit), which natural number is denoted by xn−1xn−2 ···x2x1x0?
(b) Describe, in English, an algorithm for converting from binary to decimal notation.
(c) Write the algorithm in (pseudo-) code.
(d) Describe, in English, how to convert the decimal representation to binary.
2. Below are three (correct) formulas for calculating the area of a triangle with sides A, B, and C, of length a, b, and c, respectively.
(a) S = √p(p − a)(p − b)(p − c), where p = (a + b + c)/2
, where θ is the angle between sides A and B
, where hA is the height to base A
Which of these would you accept as an algorithm?
3. Consider the following problem: You are to design an algorithm to determine the best route for a subway passenger to take from one station to another in a city such as Kolkata or Tokyo.
(a) Discuss ways of making the problem statement less vague. In particular, what is “best” supposed to mean?
(b) How would you model this problem by a graph?
4. Consider the following map:
a b
c d
e
f
g
(a) A cartographer wants to colour the map so that no two neighbouring countries have the same colour. How few colours can she get away with?
(b) Show how to reduce the problem to a graph-colouring problem.
5. You have to search for a given number n in a sorted list of numbers.
(a) How can you take advantage of knowing that the list is represented as a linked (and sorted) list?
(b) How can you take advantage of knowing the list is represented as an array?
gcd(x,y) = max{z | ∃u,v : x = uz ∧ y = vz}
