start to capture notes and look at ass 1

1 files changed, 34 insertions, 1 deletions

diff --git a/0x01/README.md b/0x01/README.md
index 724085f..1c29d5b 100644
--- a/0x01/README.md
+++ b/0x01/README.md
@@ -8,11 +8,44 @@ When you complete all the exercises of an assignment, zip them into a single fil
 
 Submit your solutions to the following exercises and problems:
 
-1. Exercise 1.1-4 from the textbook (5 marks)
+1. Exercise 1.1-4
+  * How are the shortest path and traveling-salesman problems given above similar?
+  * How are they different?
 1. Exercise 1.2-2 from the textbook (5 marks)
+  * Suppose we are comparing implementations of insertion sort and merge sort on
+    the same machine. For inputs of size n, insertion sort runs in 8n^2 steps,
+    while merge sort runs in 64nlg(n) steps. For which values of n does
+    insertion sort beat merge sort?
 1. Exercise 2.1-3 from the textbook. (10 marks)
+
+    Consider the searching problem:
+
+    Input: A sequence of n numbers A = {a1, a2, ...., an} and a value v.
+    Output: An index i such that v = A[i] or the special value NIL if v does not
+    appear in A.
+
+    Write pseudocode for linear search, which scans through the sequence,
+    looking for v. Using a loop invariant, prove that your algorithm is correct.
+    Make sure that your loop invariant fulfills the three necessary properties.
+
 1. Exercise 2.2-3 from the textbook (10 marks)
+
+    Consider linear search again (see Exercise 2.1-3). How many elements of the
+    input sequence need to be checked on the average assuming that the element
+    being searched for is equally likely to be any element in the array? How
+    about in the worst case? What are the average-case and worst-case running
+    times of linear search in O-notation? Justify your answers.
+
 1. Exercise 2.3-5 from the textbook (10 marks)
+
+    Referring back to the searching problem (see Exercise 2.1-3), observe that
+    if the sequence A is sorted, we can check the midpoint of the sequence
+    against v and eliminate half of the sequence from further consideration. The
+    binary search algorithm repeats this procedure, halving the size of the
+    remaining portion of the sequence each time. Write pseudocode, either
+    iterative or recursive, for binary search. Argue that the worst case running
+    time of binary search is O(lg(n)).
+
 1. Exercise 3.1-1 from the textbook (5 marks)
 1. Problem 3-1 from the textbook (10 marks)
 1. Exercise 4.1-2 from the textbook (10 marks)