<commit_before>---
layout: post
title: "Algorithms Course I With Prof Sidgewick on Coursera"
category: posts
tags: []
categories: []
published: false
tweetfb: true
disqus: true
---

### General

1. Why study Algorithms and Data Structures? Why are they important?
Computers, no matter how powerful, have space and time constraints. Poorly thought through implementations for computing problems can take years to compute even when computing resources are massive. For example -

![image](http://bharathwrites.in/images/algorithms/timecompare.png)

2. Why learn, re-learn algorithms?

* The primary reason to do so is that we are faced, all too often, with completely new computing environments (hardware and software) with new features that old implementations may not use to best advantage
* As a professional, it is a crime to use tools without their thorough understanding. So as Java programmers, to use HashMap and TreeSet without the knowledge of the underlying resource utilisation and performance impact is…
* Intellectually satisfying

3. How do you measure how long will your program take to run?
* Repeated runs in thousands to find the mean and standard-deviation
* Run it for different quantum's of input data 'N' - find mean and std-dev for different N after thousands of runs
* Find a relationship between N and time-taken by plotting on a graph - is the graph linear? hyperbolic? logarithmic? 

4. Why measure how long programs take to run?
Knowing the order of growth of the running time of an algorithm provides precisely the information that you need to understand limita- tions on the size of the problems that you can solve. Developing such understanding is the most important reason to study performance.

4. What are big-O and big-Omega notations? Why are they needed?
big-O is for the upper bound. big-Omega is for the lower bound. (there is also a big-Theta that is a little more involved idea). The running times of a great many programs depend only on a small subset of their instructions - so when running time of algorithms are proportional to squares(N<sup>2</sup>) or cubes(N<sup>3</sup>) or exponentials(2<sup>N</sup>) of input data counts (N), we know that these algorithms will not scale for large inputs (N). Only when running times of algorithms are proportional to linear(N), linearithmic(NlogN) or logarithmic(logN) or constant can they be expected to scale for large inputs.

4. Then why is big-O not useful for predicting performance or for comparing algorithms?
The primary reason is that it describes only an upper bound on the running time. Actual performance might be much better. The running time of an algorithm might be both O(N2) and ~ a N log N. As a result, it cannot be used to justify tests like our doubling ratio test (see Proposition C on page 193). 

5. What is the base of log when we are talking about complexities of algorithms? Why?
Base-2. In terms of Big-O, the base doesn't matter because the change of base formula implies that it's only a constant factor difference. That is logarithms from base 10 or base 2 or base e can be exchanged (transformed) to any other base with the addition of a constant. The critical thing to understand is that logarithms (of any base) increase slowly with the increase of N. However, observe this table of log values… (with respect to complexity of algorithms, the value of N can never be fractional or negative anyway...)

![image](http://bharathwrites.in/images/algorithms/log.png)

6. What does Java Arrays.sort() implement?
Mergesort till Java6. TimSort from Java7 onwards...

7. Order of growth graph?
Here is the log-log plot (both size(N) x-axis and time(T) y-axis are in logarithms)
![image](http://bharathwrites.in/images/algorithms/orderofgrowth.png)

8. Example of each -

constant time - assignment statement
logarithmic - binary search
linear - find the maximum value
linearithmic - merge sort
quadratic - double for/while loop
cubic - triple for/while loop
exponential - brute force search

9. Why develop faster algorithms?
Faster algorithms help us to address larger problems

10. Why study memory utilisation of Java programs?
if you have 1GB of memory on your computer (1 billion bytes), you cannot fit more than about 32 mil- lion int values or 16 million double values in memory at any one time.

11. How many bytes in memory are required to store a reference to a Java Object?
4 bytes on a 32 bit system. 8 bytes on a 64 bit system

### Sorting

1. In Java what do you have to do to be able to sort an array of a custom object type?
The class of the object should implement Comparable

2. Performance of selection sort
N<sup>2</sup>/2 compares and N exchanges

3. About selection sort
* it takes about as long to run selection sort for an array that is already in order or for an array with all keys equal as it does for a randomly-ordered array! 
* Data movement is minimal

4. Performance of insertion sort
Insertion sort uses N<sup>2</sup>/4 compares and N<sup>2</sup>/4 exchanges to sort a randomly ordered array of length N with distinct keys, on the average. The worst case is N<sup>2</sup>/2 compares and N<sup>2</sup>/2 exchanges and the best case is N-1 compares and 0 exchanges.

5. Performance of merge sort
Top-down and bottom-up mergesort uses between 1⁄2NlogN and NlogN compares to sort any array of length N. Top-down mergesort uses at most 6NlogN array accesses to sort an array of length N. The primary drawback of mergesort is that it requires extra space proportional to N

6. Upper limits to compare based sorting algorithms
Compare-based algorithms that make their decisions about items only on the basis of comparing keys. A compare-based algorithm can do an ar- bitrary amount of computation between compares, but cannot get any information about a key except by comparing it with another one. No compare-based sorting algorithm can guarantee to sort N items with fewer than log(N!) ~ NlogN compares.

7. 
<commit_msg>till priority queues<commit_after>---
layout: post
title: "Algorithms Course I With Prof Sidgewick on Coursera"
category: posts
tags: []
categories: []
published: false
tweetfb: true
disqus: true
---

### General

1. Why study Algorithms and Data Structures? Why are they important?
Computers, no matter how powerful, have space and time constraints. Poorly thought through implementations for computing problems can take years to compute even when computing resources are massive. For example -

![image](http://bharathwrites.in/images/algorithms/timecompare.png)

2. Why learn, re-learn algorithms?

* The primary reason to do so is that we are faced, all too often, with completely new computing environments (hardware and software) with new features that old implementations may not use to best advantage
* As a professional, it is a crime to use tools without their thorough understanding. So as Java programmers, to use HashMap and TreeSet without the knowledge of the underlying resource utilisation and performance impact is…
* Intellectually satisfying

3. How do you measure how long will your program take to run?
* Repeated runs in thousands to find the mean and standard-deviation
* Run it for different quantum's of input data 'N' - find mean and std-dev for different N after thousands of runs
* Find a relationship between N and time-taken by plotting on a graph - is the graph linear? hyperbolic? logarithmic? 

4. Why measure how long programs take to run?
Knowing the order of growth of the running time of an algorithm provides precisely the information that you need to understand limita- tions on the size of the problems that you can solve. Developing such understanding is the most important reason to study performance.

4. What are big-O and big-Omega notations? Why are they needed?
big-O is for the upper bound. big-Omega is for the lower bound. (there is also a big-Theta that is a little more involved idea). The running times of a great many programs depend only on a small subset of their instructions - so when running time of algorithms are proportional to squares(N<sup>2</sup>) or cubes(N<sup>3</sup>) or exponentials(2<sup>N</sup>) of input data counts (N), we know that these algorithms will not scale for large inputs (N). Only when running times of algorithms are proportional to linear(N), linearithmic(NlogN) or logarithmic(logN) or constant can they be expected to scale for large inputs.

4. Then why is big-O not useful for predicting performance or for comparing algorithms?
The primary reason is that it describes only an upper bound on the running time. Actual performance might be much better. The running time of an algorithm might be both O(N2) and ~ a N log N. As a result, it cannot be used to justify tests like our doubling ratio test (see Proposition C on page 193). 

5. What is the base of log when we are talking about complexities of algorithms? Why?
Base-2. In terms of Big-O, the base doesn't matter because the change of base formula implies that it's only a constant factor difference. That is logarithms from base 10 or base 2 or base e can be exchanged (transformed) to any other base with the addition of a constant. The critical thing to understand is that logarithms (of any base) increase slowly with the increase of N. However, observe this table of log values… (with respect to complexity of algorithms, the value of N can never be fractional or negative anyway...)

![image](http://bharathwrites.in/images/algorithms/log.png)

6. What does Java Arrays.sort() implement?
Mergesort till Java6. TimSort from Java7 onwards...

7. Order of growth graph?
Here is the log-log plot (both size(N) x-axis and time(T) y-axis are in logarithms)
![image](http://bharathwrites.in/images/algorithms/orderofgrowth.png)

8. Example of each -

constant time - assignment statement
logarithmic - binary search
linear - find the maximum value
linearithmic - merge sort
quadratic - double for/while loop
cubic - triple for/while loop
exponential - brute force search

9. Why develop faster algorithms?
Faster algorithms help us to address larger problems

10. Why study memory utilisation of Java programs?
if you have 1GB of memory on your computer (1 billion bytes), you cannot fit more than about 32 mil- lion int values or 16 million double values in memory at any one time.

11. How many bytes in memory are required to store a reference to a Java Object?
4 bytes on a 32 bit system. 8 bytes on a 64 bit system

### Sorting

1. In Java what do you have to do to be able to sort an array of a custom object type?
The class of the object should implement Comparable

2. Performance of selection sort
N<sup>2</sup>/2 compares and N exchanges

3. About selection sort
* it takes about as long to run selection sort for an array that is already in order or for an array with all keys equal as it does for a randomly-ordered array! 
* Data movement is minimal

4. Performance of insertion sort
Insertion sort uses N<sup>2</sup>/4 compares and N<sup>2</sup>/4 exchanges to sort a randomly ordered array of length N with distinct keys, on the average. The worst case is N<sup>2</sup>/2 compares and N<sup>2</sup>/2 exchanges and the best case is N-1 compares and 0 exchanges.

5. Performance of merge sort
Top-down and bottom-up mergesort uses between 1⁄2NlogN and NlogN compares to sort any array of length N. Top-down mergesort uses at most 6NlogN array accesses to sort an array of length N. The primary drawback of mergesort is that it requires extra space proportional to N

6. Upper limits to compare based sorting algorithms
Compare-based algorithms that make their decisions about items only on the basis of comparing keys. A compare-based algorithm can do an arbitrary amount of computation between compares, but cannot get any information about a key except by comparing it with another one. No compare-based sorting algorithm can guarantee to sort N items with fewer than log(N!) ~ NlogN compares.

7. Performance of quick sort
The quicksort algorithm’s desirable features are that it is in-place (uses only a small auxiliary stack) and uses ~ 2NlogN compares and one-sixth that many ex- changes on the average to sort an array of length N with distinct keys.

8. Whats the problem statement for priority queues?
*insert* and *remove the maximum* have to be fast. Provide fast insert and access to a subset of data points among potentially infinite number of data points. Binary heaps provide the data structure to implement logarithmic time insert and remove-max. (Java natively provides a [PriorityQueue](http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue) implementation as part of collections)

9. What is a binary heap?
In a binary heap, the keys are stored in an *array* such that each key is guaranteed to be larger than (or equal to) the keys at two other specific positions. In turn, each of those keys must be larger than (or equal to) two additional keys, and so forth. The largest key in a heap-ordered binary tree is found at the root. Generally binary heaps are stored sequentially within an array by putting the nodes in level order, with the root at position 1, its children at positions 2 and 3, their children in positions 4, 5, 6, and 7, and so on.

10. Performance of Priorty queues with binary heaps?
In an N-key priority queue, the heap algorithms require no more than 1 + log N compares for insert and no more than 2logN compares for remove the maximum.

11. Performance of heap sort
Heapsort is significant because it is the only method that is optimal (within a constant factor) in its use of both time and space—it is guaranteed to use ~2NlogN compares and constant extra space in the worst case. When space is very tight (for example, in an embedded system or on a low-cost mobile device) it is popular because it can be implemented with just a few dozen lines (even in machine code) while still providing optimal performance. However, it is rarely used in typical applications on modern systems because it has poor *cache* (processor cache) performance: array entries are rarely compared with nearby array entries, so the number of cache misses is far higher than for quicksort, mergesort, and even shellsort, where most compares are with nearby entries.

12. Application of PriorityQueue
**TopN** by some particular order of prioritization. If you are looking for the top ten entries among a billion items, do you really want to sort a billion-entry array? With a priority queue, you can do it with a ten-entry priority queue.

13. 

{'fraction_non_alphanumeric': 0.049086521889003795, 'fraction_numerical': 0.010410203378145468, 'mean_word_length': 4.305779078273591, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2278308', 'n_tokens_mistral': 3713, 'n_tokens_neox': 3537, 'n_words': 2307}