1.9.4 Bitmaps

 A bitmap is a string of n binary disgits that can be used to represent the status of n items. For example, suppose we have several resources, and the avilability of each resource is indicated by the value of a binary digit:0 means that the resource is availlable, while 1 indicates that it is unavailable )or vice versa). The value of the i(th) position in the bitmap is associated with the i(th) reosurce. As an example,  consider the bitmap shown below:

001011101

Resource 2,4,5,6, and 8 unavailable; resource 0,1,3,and 7 are available.

The power of bitmaps becomes apparent when we consider their space efficiency. If we were to use an eight-bit Boolean value instead of a single bit, the resulting data structure would be eight times larger. Thus, bitmaps are commonly used when there is a need to represent the availability of a large number of resources. Disk direves provide a nice illustration. A medium-sized disk drive might be divided into several thousand individual units, called disk blocks. A bitmap can be used to indicate the availability of each disk block. 

In summary, data strures are prevasive in operating system implementations. Thus, we will see the structures discussed here, along with others, throughout this text as we explore kernel algorithms and their implementation.

1.9.3 Hash Functions and Maps

 A hash function takes data as its input, peforms a numeric operation on the data, and returns a n umberic value. This numeric value can then be used as an index into a table (typically an array) to quickly retrieve the data. Whereas searching for a data item through a list of size n can require up to O(n) compareisons, using a hash function for retrieving data from a table can be as good as O(1), depending on implementation details. Because of this performance, hash function are used extensively in operating systems.

On potential difficulty with hash functions is that two unique inputs can result in the same output value-that is, they can link to the same table location. We can accommodate this hash collision by hav ing a linked list at the table location that contains all of the items with the same hash value. Of course, the more collisions there are, the less efficient the hash functions is.

One use of hash function is to implement a hash map, which associates (or maps)[key:value] pairs using a hash function. Once the mapping is established, we can apply the ahsh function to the key to obtain the value from the hash map(Figure 1.2.1). For example, suppose that a use name is mapped to a password. Password authentication then processds as follows: a user enters which is then used to retrieve the password. The retrieved password is then compared with the password entered by the user for authentication.

1.9.2 Trees

 A tree is a data structure that can be used to represent data hierarchically. Data values in a tree structure are linked through parent-child relationships. In a general tree, a parent may have an umlimited number of children. In a binary tree, a parent may have at most two children, which we term the left child and the right child, A binary search tree additionally requires an ordering between the parent's two children in which left_child <= right_child. Figure 1.20 provides an example of a binary search tree. When we search for an item in a binary search tree, the worst0case performance is O(n)(consider how this can occur). To remedy this situations, we can use an algorithm to create a balanced binary search tree. Here, a tree containing n items has at most lg n levels, thus ensuring worst-case performance of O(lg n). We shall see in Section 5.7.1 that Linux uses a balanced binary search tree (known as a red-black tree) as part its CPU-scheduling algorithm.

2. Outline and Perspective

 What we've done so far

- In-depth look at convolution

- CNN architecture

- Use structure of images

- Training + Inference

What we'll do now

- Now that we know the basic pattern, what are some novel architectures that do not follow the basic pattern?(ResNet)

1) We'll also look at VGG and Inception

Transfer Learning

- We've seen that even 3-5 layer nets can take a very long time to train

1) But now we'll be looking at 50 layer nets!

- Researchers today (in machine learning) are committed to openness, and by  sharing their research it is easy for you to do the state-of-the-art at home

Random neural network => TRAINING(ImageNet)=> Neural network <<pre-trained>> on ImageNet =>FINE TUNNG(Your data)=>Trained neural network

1) No other field can archive this:biology, medicine, physics, ... Try building a particle accelerator in your bedroom!

- We can make use of pre-trained weights using transfer learning-significantly reduces training time since we now only need to do fine-tuning

1) Works for completely new/unseen problems, e.g. take inception trained on ImageNet and use it on totally new data

Systems of CNNs

- We tuched on this in Deep Learning pt 8: GANs & Variational Autoencoders

1) System of 2 CNNs -- not real people ->

Object Detection

- SSD

- Both faster and more accurate than previous state-of-the-art

- A prerequisite for any self-driving vehicle

1. Introduction

 Advanced Convolutional Neural Networks

- This field has progressed so far!

- I never thought i'd make two CNN courses

- This course is not only way different from CNN pt 1, it is also WAY more massive

Newer, Better Architecures

Object Detection

A CNN is just a part of this system!

Transfer Learning

Random neural network =>(TRAINING:ImageNet)=>Neural network<<pre-trained>> on ImageNet =>FINE TUNING:Your data)=> Trained neural network

SSD

Image(224*224) => Base Network(13*13*512) => Additional Feature Layers

=>

Feature map(Ex1_2 6*6*512) => Feature map (Ex2_2 3*3*256) => Feature map (Ex3_3 2*2*128) => Feature map (GAP 1*1*128) 

=>

Detections Layers => Non-Maximum Suppression => Detection Results

1.9.1 Lists, Stacks, and Queues

 An array is a simple data structure in which each element can be accessed directly. For example, main memory is constructed as an array. If the data item being tstored is larger than one byte, then multiple bytes can be allocated to the item, and the item is addressed as "item number x item size." But what about storing an item whose size may vary? And what about removing an item if the relative positions of the remaining items must be preserved? In such situations, arrays give way to other data structures.

After arrays. list are perhaps the most fundamental data structures in computer science. Whereas each item in an array can be accessed directly, the items in a list must be accessed in a particular order. That is, a list represents a collection of data values as a sequence. The most common method for implementing thsi structure is a linked list, in which items are linked to one another. Linked lists are of several types:

- In a singly linked list, each item points to its successor, as illustrated in Figure 1.17.

- In a doubly linked list, a given item can refer either to its predecessor or to its successor, as illustrated in Figure 1.18.

- In a circularly linked list, the last element in the list refers to the first delement, rather than to null, as illustrated in Figure 1.19.

Linked lists accommodate items of varying sizes and allow easy insertion and deletion of items. One potential disadvantage of using a list is that performance for retrieving a specified item in a list of size n is linear-O(n), as it requires potentially traversing all n elements in the worst case. Lists are some-times used directly by kernel algorithms. Frequently, though, they areused for constructing more powerful data structures, such as stacks and queues.

A stack is a sequentially ordered data structure that uses the last in, first out(LIFO) principle ofr adding and removing items, meaning that last item placed onto a stack is the first item removed. The operations for inserting and removing items from a stack are known as push and pop, respectively. An operating system often uses a stack when invoking function calls. Parameters, local variables, and the reuturn address are pushed onto the stack when a function is called; returing from the function call pops those items off the stack.

A queue, in contrast, is a sequentially ordered data structure that uses the first in, first out(FIFO) principle; items are removced from a queue in the order in which they wwere inserted. There are many everyday exasmples of queues, including shoppers waitting in a checkout line at a store and casrs waiting in line that are sent to a printer are typically printed in the order in which they were submitted, for example. As we shall see in Chapter 5. tasks that are waiting to be run on an available CPU are often organized in queues.

1.9 Kernel Data Structures

 We turn next to a topic central to operating-system implementation: they way data are structured in the system. In this section, we briefly describe several fundamental data structures used extensively in opoerating systems. Readers who require further details on the structures, as well as others, should consult the bibliography at the end of the chapter.