6.

• Tree of domain names (C Scientists love trees),, how many top level domains?, true, false and meaningless statements, what is an algorithm.
• Base Ten Logarithms. Plotting on Log-Log graph paper: Printed on the back of the homework assignment paper.
• Homework Assignment 1 (DUE Jan 27)
  • SortableArray class Java file      Stopwatch class Java File
  • Linear grid to print
  • 8x10 Portrait Log-Log grid to print--is better!
  • Log-Log grid to print
• Reading summary assignment: Write 2 sentences for EACH SECTION (specifically, 1.1, 1.2, 1.3, 2.1, 2.2 and 2.3) of the text to summarize what is covered in that section. (Only a few of the textbook's details will be required in the course.) Do or submit electronically on Blackboard.

• A good free web service that generates .pdf grids for printing of graph paper.
• Wikipedia article on Domain Name System
• Wikipedia article on ICANN
• Wikipedia article on Domain Name Root

1. 2. 6.

• Quiz on the reading
• Describe the sorting problem, before learning how CLRS do it.
• Introduction to algorithms via two algorithms and programs for the sorting problem.
• Lecfure notes (.pdf)

1. 3. 6.

• Quiz: (1-2) best outer and inner loop limits for selection sort pseudo code, write pseudo code for the merge procedure.
• The merge problem distinguished from the sorting problem
• Details of the MERGE procedure (ideas on chalkboard)
• Generalities about recursion: Why it's good to know. MERGESORT as an example of divide and conqure. Why MERGESORT is so fast. We got up to the recursion history tree. Please think about how much baby food was purchased by each of George Washington's decendents..
• Homework Assignment 2 (DUE Feb 3)

• Vi Hart's Binary Tree Doodling Video

• UA-CCI ACM Student Chapter meeting THURSDAY 6:00PM LI-84
• Quiz-exercise on binary search in an array and drawing a binary search tree.
• Trees, Binary Trees, Binary Ordered Trees, Binary Search Trees.
• Vi Hart's Binary Tree Doodling Video
• Analysis of the Binary Search Algorithm
• Why MERGE-SORT is so fast. Chalkboard sketch reproduced.
• Reading assignment DUE TUES (1 week) Chapter 4 (just skim and omit writing about the Strassen section) and reading on HEAP-SORT: Sections 6.4, 6.1, 6.2, 6.3

• Don't get "snowed" Write for each subsection (that is subsection under a boldface heading) write one sentence that says what is done in that subsection. After you are finished writing one sentence for each subsection, go back and write another sentence for each subsection that sanswers "How?"

• Suprise quiz: Draw an example of a heap with 7 keys.
• New views on "What is the sorting problem" from class members.
• Homework Assignment 3: T1: (Paper) Demonstrate HEAP-SORT on paper. P1: (Blackboard) Program HEAP-SORT as described in the text into your sorting code benchmarking program. E1: (Paper) Plot, on linear and log-log grids and compare the actual running times for the entire range of practical problem sizes for (1) your best MERGE-SORT implementation with (2) your HEAP-SORT implementation.
• HEAP-SORT: An application of trees. How to read a CS book. Our order: 6.4, 6.1, 6.2, 6.3 Mostly class discussion using the chalkboard. Everything covered except the run time analysis. "Clever ideas" pointed out.

• Homework idea: Scribble on a recursion history tree the time-on-the-clock when each activation started and each activation finished.

• Review clever ideas behind HEAP-SORT (notes from chalkboard talk partially complete).
• Some theoretical and practical issues particular to HEAP-SORT and general about exploring algorithms were discussed, see scribbled notes above.
• Why is "booting" a computer called "booting"?

  Yes, it comes from "bootstrapping", a word attributed by unnamed Web sources to date to the early 19th century, to "pull onself up by one's own bootstraps" It does mean getting the Operating System kernel into the computer memory. The BIOS code is run and plays an important role.

  But still, why is it called "bootstrapping"?

• Homework Assignment 3.5: E1 (Due on paper Thu, Feb. 17) Compile with javac nameOfClass.java and disassassemble with javap -c nameOfClass a class that contains the method int access(int i) { return (i-1); }. Count (approximately) how many bytes of byte-code comprises the byte-codes for the access() method. Compare that number to 4, which is the number of bytes wasted when the [0] entry of a Java int array is ignored.

• ---

2., 6., 7.

• In class quiz: Make your own decision tree for sorting (a1,a2,a3).

  The decision tree model for sorting is defined so each question is only of the form "Is ai < aj ?" for just two keys. This question has only a yes-no answer. A decision tree for sorting (a1,a2,a3) MUST (1) Be only one tree and (2) have 6 leaves, one for each of the 6 answers which are the orders of distinct keys.

• Tree-lore: Number of nodes, total, internal and leaves, in a complete binary tree of a given height.
• Homework 1 returned and graphs of merge versus selection sort times viewed and compared.
• Homework Assignment 4 (slipped DUE Mar. 3 after break, but extra credit if in by Thursday, Feb 17, 9 days, everything on PAPER)

  In Chapter 8, the decision tree model for comparison sorting is explained and used, and then sorting based on NUMERIC properties of keys, over and above their ordering, is discussed. We showed that the computer can figure out exactly where key

  532,231 should be placed when all the keys are in the 1-1,000,000 range of integers.

  T1:(a) In your own words, explain the conclusion of 8.1.(b) Draw your one decision tree for sorting (a1,a2,a3,a4): Make sure it has 24 leaves. Hint: Write out the 24=4! leaves first.

  T2: (a) In your own words, explain the conclusion of section 8.2. (b) Exercise 8.2-1

  T3: (a) In your own words, explain the conclusion of 8.3. (b) Exercise 8.3-1.

  T4: (a) In your own words, explain the conclusion of 8.4. (b) Exercise 8.4-1.

  T5: Exercise 8.4-2. Hint: An algorithm can be a combination of algorithms.

• Notes of last week and this week.
• HW 4 (see above) due Thurs, Mar. 3 (Extra credit if in before the break.)
• Half rounded up of the nodes are at the bottom level!
• Figuring out formulas for things like the number of nodes in a complete 3-ary tree when you don't know the answer already. (meta-education)
• Runtime analysis of HEAP-SORT and its supporting sub-algorithms: Why BUILD-HEAP takes O(N) time instead of O(N log N) (applies Calculus).

• Comparison idea and decision tree model for distinguishing among 9 "Jewels": Discussion and application to the sorting problem log(N!) comparison lower bound.
• The ratio test of calculus applied to help know that the BUILD-HEAP step (Phase 1 of Heap-sort) takes O(N) time and not O(N log N).
• Cleverness of counting sort (just began)

• Cleverness of counting sort.
• Assorted radix type sorting ideas

• QUICK-SORT
• Divide and conquer applied to multiplication
• Homework 5 (DUE Thursday, Mar 10)

• • T0: Begin to review the chapters on Data Structures in CLRS. Write an assessment of how much understand of each section. That will guide how much we cover of it in class.
  • T1: CLRS Exercise 5.1-2 Only do it when b-a+1 (number of possible return values for RANDOM(a,b)) is a power of 2, so it is easy to use binary search.
  • T2: CLRS Exercise 7.1-1.
  • P1: Add QUICKSORT to your sorting laboratory program.
  • E1: (a) Add to your laboratory program the ability to initiallize the array to be sorted with random values. (b) Benchmark and plot one running time for the usual sequence of sizes of arrays to be sorted with QUICKSORT. Use the same environment that you used for other experiments.
  • T3: Demonstrate the faster divide and conquer multiplication algorithm from class for multiplying 12345678 (base ten) by 87654321.

• MIDTERM SURVEY
• Derive the correct tricky divide and conquer algorithm for multiplying integers and discover its O(N^(log 2 (3)) running time.

• Remarks on midterm survey.
• Link to Shannon's paper on Prof. Knuth's course web site. Quantity of information from knowing an answer is measured by the logarithm of the number of (equally likely) possible answers. The Order(N Log N) lower bound for number of pairwise comparisons needed to sort N things is called the "Information Theory Lower Bound".
• Today's notes added. We discussed linked lists versus arrays and formulated the amortized time analysis for adding elements to an extendable array when the size is doubled each time expanding is required.
• Quiz warning: See today's notes!
• Java Library Documention pages read:
  • Vector
  • ArrayList

• Quiz on calculating that expanding takes O(N) amortized time.
• Notes for Midterm Review
• The max sum of subarray problem: 3 algorithms compared.

Midterm Exam in class

• Notes on data structures and dynamic sets operations: up to hashing.
• Mini Homework 6(DUE Mar 24): CLRS Exercise 4.1-5 (The "good" O(N) algorithm for the max sum subarray problem).

• HW 7 (Due Mar 31 as usual)
  • T1: Exercise 10.1-2 Write pseudo-code AND demonstrate on a small example.
  • T2: Exercise 10.3-1 MUST demostrate the array-representation idea: Learn it by reading.
  • T3: Exercises 10.4-2 AND 10.4-3 Demonstrate on the SAME SMALL GENERIC binary tree.
  • T4: Exercise 10.4-6 Draw a picture. Hint: Use the same pointer fields(s) for different purposes.
  • P1: Demonstrate Exercise 11.1-2 with a BitVector Java class. Find out about Java bit operations. The constructor must accept ints m. Hints: The constructor constructs an array of Java ints. Access involves dividing by 32 and getting the remainder mod 32..
  • T5: Exercise 11.4-1
  • Reading: The chapter on B-trees. (Ch. 18).
• Discussion of
  • balanced trees
  • hashing including the fact about the same address sequence for open addressing
  • intro to B-trees.

• Element tree traversing interface to DOMused in JavaScript (w3c STANDARD)

• Search trees, balanced trees, intro. to B-trees, annotated algorithm to search a B-tree

Midterm-Makeup Problem: Problems versus Algorithms

Write on 5 separate pages the following for each of the 5 problems below.

What to write:

• The problem statement, informatively, terms of input and output (NOTHING MUST BE MENTIONED ABOUT ALGORITHMS or the problem's difficulty)
• Brief descriptions of two different algorithms that solve the described problem, where the two algorithms MUST have different asymptotic worst case running times. For example, for the MERGE problem, one algorithm is the simple merge procedure which takes O(N) time and another is MERGE-SORT (applied to the two subarrays together) which takes O(N log N) time.

The Problems:

1. Sorting (p. 16)
2. Searching (p. 22)
3. Merging (class notes only-not written out explicitly in CLRS)
4. Maximum subarray (p.69: You write your own input/output formal statement).
5. Selection problem (p.213)

Students who answered the midterm question to state and compare PROBLEMS without reference to ALGORITHMS got 14 points on the midterm for this. Everyone else will get those 14 midterm exam points from doing this homework. DUE (like taxes) Thu, April 14.).

• Finish (almost?) B-tree topic. Use the notes to help use the textbook explanations for inserting and deleting.
• Homework 8:
  • T1 18.2-1
  • T2 18.2-3
  • T3 18.2-6
  • T4 18.3-1 (subtle! study my notes plus the text)

• Completion of B-trees topic. Glimpse at Red-Black Trees. Intro. to the augmenting of data structures with additional useful stuff and the combination of ordered dictionary operations with rank calculation and rank based retrieval.

(2)

• In class quiz: Write the recursive pseudo-code for the in-order traversal of a binary tree with a rank field in each node that causes the rank field to become set to the rank of the node in binary search order. Hint: Use a global counter variable G to keep track of the last rank value assigned.

• Continuation of the idea of how to augment data structures. See these notes for Homework 9. Get copies of Figure 14.4 from class or make them yourself because the homework includes scribbling on Figure 14.4 several times!

• Finish augmenting data strs: Details of rank retrieval and determination; interval overlapping problem
• Begin Dynamic Programming (rod cutting problem intro): Reading 15.1, 15.2, 25.2

• Finish Rod Cutting problem solved by dynamic programming and start with optimal matrix multiplication ordering.
  • 3 Rod Cutting algorithms inplemented in Java, to demonstrate using a base class for common data and methods, an interface to specify how the 3 classes can be used the same way, and 3 derived classes for the algorithms. Benchmarking main class included too.

• hw 10 Due Thurs, Apr 28
  • T1 15.1-5
  • T2 15.2-1
  • T3 15.3-2
  • T3 25.2-1

• Scribbled notes for optimal matrix multiplication.
• Notes for shortest paths dynamic programming algorithms inluding the Warshall-Floyd algorithm; Min-Plus arithmetic.

• CLRS Lect 19 Original

  MIT OCW page for all resources

• CLRS Lect 15 Original

  MIT OCW page for all resources

• Warshall-Floyd algorithm; Min-Plus arithmetic. power finding by repeated squaring.
• Application for Min-Plus operations.
• Longest common subsequences found with dynamic programming; Dynamic programming hallmarks.

• Post-midterm topic summary.
• Shortest paths with Dijkstra's algorithm
  1. Learning from theorems stated in books or papers: (a) What the theorem says. (b) Why it is true, if it is, is explained with a proof.
  2. The power of an invariant to understand why a subtle algorithm like Dijkstra's solves its problem correctly.

• Dijkstra's famous paper "Go-to statement considered harmful"
• Dijkstra's archive web site.
• Barbara Liskov's Lecture on her work on object oriented programming leading to her Turing Award.